具体 Java 代码在 github 中。先说一下,这个东西还是得靠理解,不要抄袭哟~
主要是构建一个 9 * 9 * 9 的数组,总共 81 个数字格子,每个格子下有 9 个可能性用 boolean 变量来表示。
一开始根据给出的题目先标注已经确定的格子并更新数组,把每个格子不可能的数字都 false 掉,然后遍历数组,将只剩下一个可能性的格子先确定填掉,并更新数组。
然后这个时候的话一些简单的题目就可以做出来了。
但是对于一些中等或者难的数独会有一些空格子还没法直接确定,会有很多可能性需要去推。
这个时候又需要另外一个东西了,那就是动态规划,动态规划我没有系统地学过,基本不列公式,这里就不列了,讲下思路。
动态规划的回溯函数的参数就用空格子的坐标和目前规划到的数组(用全局变量),当数组中存在无填数可能的空格子时就判定回溯,这个题解状态失效,回到上一步把填入的数字可能性 false 掉,选取下一个可能数字再进入新状态搜索。
这样子去求的话就算一个空题都能解出来了(虽然没啥意义哈哈哈)。