偶然看到数独的问题，因为自己也玩过数独，就产生了用代码来破解数独的这么一个想法。
想法
数独就是个大的九宫格，每个九宫格又是一个小的九宫格，这个小的九宫格里面是1-9这九个数字，唯一且不重复。数独的目的就是根据给定的几个已知格子内的数字去填充大量的其他格子中的未知数字(1-9)，且要保证，最外层的大九宫格的每一行、每一列都是1-9这9个数字，且大九宫格内的每个小九宫格也都是1-9这9个数字。都是唯一、不重复。
以下这个数独是网友在知乎上的一个数独，格子中中间部分大的数字，就是已有确定的格子中的数字，左上角的数字，是所在格子内按照数独规则可以填充的数字（图中的标注应该是有错误的比如第一行第三个格子，可填的数字应该是1、5、9，作者这个可能的数字集合可能是他优化过后的，对于计算机来说，你懂得）：
数独.png
思路一：穷举法
我们要从每个格子中可能被填充的数中都分别选出一个，以达到所有格子最终都被填充完毕且符合数独正确性，直观的解法就是去把所有不确定的组合进行穷举，去试验，看看哪一个组合最终能填充使得最终数独是正确的。
看似可行，但是实际操作起来，这个组合数会让人大跌眼镜。
最多穷举的次数：3(第一行第一个格子的可能取值) × 1(第一行第二个格子的可能取值) × 2 (第一行第三个格子的可能取值) … × 1(第9行第9个格子的可能取值) = 150459195064320000000 次，这个就有点恐怖了，所以这个策略就先排除吧。
思路二：改进穷举法
穷举肯定是可行的，但是如果可以优化一下穷举，可能效果会更好，解出数独的时间会更快。
数独有个特性，就是每一行、每一列、每个小的九宫格内都是不重复的1-9，这三个条件是同时满足的。也就是当我们进行可能性穷举的时候，每次试探性的填充值进入一个尚未填充值的格子的时候，是会减少其它格子填充数字的可能性的。
也就是说，当我们向第一个格子中填入1之后，那么同行、同列、同九宫格中的所有未填充数字的格子就不可以再填入1，这样，就大大降低了最终穷举的可能性。我们递归的，每次填入之后都进行可能性的重置，然后再次填入，再重置，这样，就会大大降低迭代的轮数。
直接上代码(核心函数)：
def solve(grid):
canuse_array = [[[] for n in range(9)] for n in range(9)]
for row in range(9):
for column in range(9):
if grid[row][column] == 0: # 如果单元格内的数字为0，也就是尚未填充数字，就对其可能填充的数字集合进行试探性填充
existed_set = {0}
for index in range(9): # 查看所在行列
existed_set.add(grid[row][index]) # 将待填充单元格的所在行的所有已经填充的数字加入集合
existed_set.add(grid[index][column]) # 将待填充单元格所在列的所有已填充的数字加入集合
for i in range(3): # 查看所在九宫格
for j in range(3):
existed_set.add(grid[row // 3 * 3 + i][column // 3 * 3 + j]) # 将单元格所在九宫格中的数字都写进已填写集合
if len(existed_set) != 10: # 如果该单元格所在的行列以及九宫格内的已填充数字包含10个(0-9)，证明不需要填充
for canUse in range(1, 10): # 查漏补缺，如果1-9这9个数字中有可以填充入单元格的，就进行填充去试
if canUse not in existed_set:
canuse_array[row][column].append(canUse)
else:
canuse_array[row][column].append(grid[row][column])
for row in range(9):
for colunm in range(9):
# 找到canuse_array中的第一个可能性不为1个的位置
if grid[row][colunm] == 0:
for case in canuse_array[row][colunm]:
grid[row][colunm] = case
if solve(grid):
return True
grid[row][colunm] = 0
return False
return True
最终的结果：
大概的耗时是0.2秒.png
网友评论