4.3　数独游戏

题目描述（第37题）

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法须遵循如下规则。

●　数字1～9在每一行只能出现一次。

●　数字1～9在每一列只能出现一次。

●　数字1～9在每一个以粗实线分隔的3×3宫格内只能出现一次。空格用 '.' 表示。

如下图所示为一个数独。

答案为下图阴影部分的数字。

注意事项：

●　给定的数独序列只包含数字1～9和字符'.'。

●　可以假设给定的数独只有唯一解。

●　给定数独永远是9×9形式的。

解法一　回溯解法

思路

读者对数独游戏应该不陌生，在纸质媒体发达的年代，很多报纸会提供一个专门的版面印上数独游戏供读者打发时间。规则简单易懂是其成为大众游戏的一大原因，解数独的要求用一句话即可概括：填空格使每行、每列和每个九宫格都恰好由1到9这9个数字组成。

在只有唯一解的限定条件下，空格越多数独越难解，用算法语言来讲就是求解的时间复杂度越高。假设不使用任何策略，对n个空格采用暴力法穷举求解，时间复杂度会接近9的n次方阶。这样的效率显然是不可接受的，但枚举思路基本正确，需要做的是利用规则并结合棋盘上已有的数字降低枚举值的数量级；盲目的尝试会产生很多无效的计算，利用回溯算法进行有规律的遍历是一种更可取的方法。

记录状态

首先定义row_state、column_state和box_state 存储当前每一行、每一列和九宫格中数字的使用状态，如row[0][3]表示第1行中数字3的使用情况。对于九宫格，用行号对3的整除乘以3加上列号对3的整除，即(i // 3)＊ 3+j // 3，其中 i 和j 分别表示行号和列号（从0开始）。将二维坐标的表示降为一维的，每一个九宫格的坐标分布如下图所示。

顺序遍历

完成3个状态的初始化后，解数独的遍历过程从board[0][0]开始，根据规则的限定选取数字放入空格，定义place_number方法执行此操作；每完成一格的填写或遇到已填有数字的格子时，遍历坐标向右移动，当列下标变为9时（第1个格子从0开始）意味着本行处理完毕，换行并从下一行的最左侧继续遍历；重复上面的过程，当填好最后一个格子，即右下角的board[8][8]后，将换行至第9行这一条件作为判定停止的标准。

回退重试

不妨把数独的盘面当作棋盘，假如棋盘布局设定比较简单，尤其是在空格较少的情况下，上述遍历方法是有可能一次性走到最后的，但在大多数情况下并不这样理想。在游戏过程中，一些格子在判定条件有限的情况下会有多个解，即存在多个可填的数字，而我们的遍历过程只能选取其中一个。当遇到某个格子没有任何数字可填时，说明前方某处选取的数字并不正确，这时应进行回退。将遍历坐标回退到上一个有其他解的格子，继续尝试其他解，当然不要忘记回退时将路径上已经填上的数字清除，定义方法undo_number_placement实现此操作。

完成数独

持续进行顺序遍历和失败重试的过程，最终完成所有格子的遍历意味着我们得到了数独的解，如果在此之前耗尽了所有可选数字，则说明此数独无解。当然，根据题目设定，这种情况不会出现。

跟随上述思路，我们可以一步一步实现下面的Python代码。

代码

复杂度分析

通常用大O表示法来展示算法的渐进时间复杂度（asymptotic time complexity），它衡量的是算法的执行时间随着输入规模增长而变化的趋势；因为格子数量有限，问题的规模不会一直变大，数独问题不满足求渐进时间复杂度的前提。

不过这样的结论应该不能满足你的期望，与了解并掌握算法相比，所谓的标准答案并没有那么重要。忽略规模增长的上限，我们的算法与空格数n相关的复杂度是多少呢？

●　时间复杂度：假设每个空格可能填入的数字个数都是m，算法的最差时间复杂度为O(mn)；在实际情况下，每个格子的m应介于1到9之间，且并不一定相同，具体的最长的执行时间为所有m值的乘积。

●　空间复杂度：解题过程中所使用的中间变量与棋盘的大小有关，在大小固定的棋盘上，算法的空间复杂度为O(1)。

解法二　回溯法优化

思路

基于上面对时间复杂度的分析，我们可以从m的值，即每个空格可填数字的个数入手优化我们的算法。

数独中格子之间有很强的关联，对于任意空格，随着同一行、同一列或同一个九宫格中某一格放入的数字被确认，空格可填的数字个数会随之减少。我们应当从把握最大的格子填起，即如果最坏的可能是一系列m值的乘积，应当从最小的m值乘起，使后续m值随之降低，理想状态下每个m值都是1，即一次回退也不会出现。把可能的回退次数降到最少，这样的解法与人们玩数独游戏时的思路十分相近。

定义函数get_max_possible_coordinate，让它根据当前棋盘的情况计算填数正确性最大的空格并返回其坐标。我们知道可以填入的数字个数越少意味着正确性越大，当可以填入的数字只有一个时正确率为100%，直接返回这个空格的坐标即可；若没有这样的理想候选项，则返回遍历过程中可填数字最少的那个空格的坐标。

使用get_max_possible_coordinate函数取代上一节解法中的顺序遍历法，我们实现了一个更优化的解法。

代码

复杂度分析

●　时间复杂度：假设每个空格可能填入的数字个数都是m，算法的最差时间复杂度为O(mn)；在实际情况下，每个格子的m应介于1到9之间，且并不一定相同，因此最差的情况需要执行所有m值的乘积次的操作。

●　空间复杂度：解题过程中所使用的中间变量与棋盘的大小有关，即与空格数无关，因此算法的空间复杂度为O(1)。

思考

解法二在寻找填数正确率最高空格的过程中，需再次遍历棋盘，与直接尝试下一格相比，似乎多执行了许多操作，它的解题效率真的比解法一强么？带着这样的疑问我们来做个实验，以力扣（LeetCode）题目中的默认测试用例为例，棋盘中有空格51个，超过半数。

定义变量undo_count记录两种解法对undo_number_placement方法的调用次数，这样我们就可以比较完成时两者分别进行的回退次数了。

执行后的结果显示：解法一回退了4157次，而解法二只回退了7次，即解法一最终尝试填数4208次才完成数独，而解法二只用了58次！这不得不让人感叹合理算法的神奇与美妙。

在大多数情况下，解法二效率更高，因为这样的遍历法会显著提高回退效率。前面分析过，随着越来越多的空格被正确地填上，问题的复杂度会随之降低。

首先它保证了存在唯一选项可选，即在存在正确答案的情况下不去做无谓的猜测。

其次参考前面做出的时间复杂度为O(mn)的分析，即便不得不进行猜测，这样的方法也能够非常有效地控制m值的大小。

解法二在回溯法的思路上做了优化。而在实际解题的过程中，还可以通过优化数据结构等方法进一步提高执行效率，你不妨自己动手试试看。