Python数独算法

前段时间公司为程序猿们举办了技术周，技术周上有很多像数独，数字华容道等锻炼逻辑思维的小游戏，玩家需要在规定时间完成上面的逻辑挑战，就可获得相应奖品，当时在现场拿了几道数独的题目来做，刚开始还好，后面做着做着就发现走进了死胡同，只能一步步往前回溯，但有时候又忘记前几步在哪儿填的是什么数了，以致于最后还是没能做出来，后来不死心的把题目带回来，想着用Python脚本实现数独的填写，也锻炼一下自己的算法思维，自己琢磨了好几天，也总算是搞出来了，本文主要讲算法思路，具体代码详见文后链接，（代码均已注释）

数独规则：

玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复;

算法思路：

1.对于一个数独，每一个空格填入的候选值应该是确定的，首先计算每个空格可填入的候选值，并按照候选值的个数升序排列，（首先选择确定性较大的空格填入）;

2.在填入候选值后，刷新数独矩阵，并重新计算空格位置的可选值;

3.当空格位置的候选值个数为0且数独里仍有空格存在时，说明在前面某一步候选值填的有错，需要回溯，回溯到错误上一步时，如果候选值个数为1，说明错误还在前面，但需要将此处值重新置为0；

4.按照步骤3依次回溯，当回溯到候选值个数大于1时，（说明错误有可能是在此处发生），将指针指向此位置的下一个候选值填入，在重新刷新记录插入位置和值的字典，并重复进行步骤1,2；

5.当记录步骤1的字典（空格位置及所有候选值）为空时，说明所有空格均已填完，则跳出所有循环；

算法详解：

1.将整个数独看成一个9*9的矩阵，而根据游戏规则，对于任一个数独空格，在数独最初时候，每一个空格可填入的值应该是确定，例如下图这个数独，在00号位置，可填写的值[1,7,9]

遍历每一个空格，记录每个空格可填入的数字及位置，并按照可填入数字的个数升序排序，此时记为字典A（我们自己填写时候，肯定也是从确定性最大的空格开始填起，已缩短计算时间），

2.将排序后的第一个候选值填入相应位置，此时需要在生成记录一个填写位置及填入值的字典B，然后重新刷新数独矩阵以及字典A，在重新将字典A中的第一个值填入，并更新字典B，循环上述过程，直至字典A的长度为0（此时矩阵中已无空格），循环结束；

3.真正实现实现时，结果并不会像上述那样好运，当在某一步填写的可能值填写错误时，会导致后面某一步可填写的值为空，例如上面00号位置，从最终结果上看，此处应该填9，但是如果在最开始时候将此位置填1，那么在后面的某一步肯定会出现某一个位置可填写的值为空，这个时候，就需要我们就要利用字典B进行回溯了；

4.假如此时字典B（记录填写位置及填写值）如下，在51号位置上出现可选值为空，则往上一步回溯，上一步是在41号位置填写4，错误是不可能发生在此处的（为什么？）

[('01',[1,3]),('00',[9,7]),('31',[8]),('41',[4]),('51',[])]

需要将这个位置和候选值从字典B中删除，并将此位置的值重新置为0，此时字典B变成

[('01',[1,3]),('00',[9,7]),('31',[8])]

还需要进一步在往前回溯，那回溯到什么时候为止呢？回溯到错误最可能发生的地方为止，上图错误最有可能发生在00号位置，刚刚在00号位置填写的9，此时应该把9换成7填入，然后重新刷新数独矩阵及计算字典A（记录空格位置及所有可能值），当字典A的长度等于0时（表示所有空格都填完），整个循环结束；

数独规则：https://baike.baidu.com/item/%E6%95%B0%E7%8B%AC/74847?fr=aladdin

代码地址：https://github.com/maxiaoguai/sudoku