芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏
写在前面
今天来点干货，结合深度优先搜索算法，对数独进行求解。以下代码纯属手工编写，每个步骤都附加详细说明。
python版本： 3.6.0
第一步：导入相关的python包
<code># encoding:utf-8
import copy/<code>
copy： 主要用于数组（矩阵）的深拷贝，有深拷贝就有浅拷贝。可以这么理解，深拷贝就是新开辟一个内存，修改原数据，拷贝后的数据不会被影响。而浅拷贝只是给数组取了个别名，实际上是同一个内容的数据，修改原数据，拷贝后的数据会跟着修改。
如果不特别声明，数组的拷贝一般是浅拷贝，例如函数传参。后面递归的参数数组，用的是浅拷贝，所以同一个数组共用一块内存。
第二步：判断矩阵是否填满
<code>"""判断矩阵是否填满了"""
def is_full(in_sd_matrix):
for i in range(len(in_sd_matrix)):
for j in range(len(in_sd_matrix[i])):
if in_sd_matrix[i][j] == 0:
return False
return True/<code>
这里作了个前提，如果矩阵中数值为0，说明该位置还未填入数字。
第三步：数独的规则
<code>"""判断当前位置能否填指定数字"""
def can_fit(in_sd_matrix, row_index:int, col_index:int, num):
# 判断当前行是否出现重复的非零数字
for k in range(len(in_sd_matrix[row_index])):
if k != col_index and in_sd_matrix[row_index][k] == num:
return False
# 判断当前列是否出现重复的非零数字
for k in range(len(in_sd_matrix)):
if k != row_index and in_sd_matrix[k][col_index] == num:
return False
# 判断当前矩阵是否出现重复的非零数字
cube_i, cube_j = int(row_index / 3), int(col_index / 3)
for k in range(cube_i * 3, (cube_i + 1) * 3):
for p in range(cube_j * 3, (cube_j + 1) * 3):
if k != row_index and p != col_index and in_sd_matrix[k][p] == num:
return False
return Tru/<code>
利用了数独的规则，每个数字满足三个条件：
1. 该数字所在的当前行不会重复，
2. 该数字所在的当前列不会重复，
3. 该数字所在的小九宫格数字不会重复。
第四步：递归-深度优先搜索
<code>"""递归填数字"""
def depth_fit_num(in_sd_matrix):
# 递归结束条件， 已经填满了
if is_full(in_sd_matrix):
return True
for i in range(0, 9):
for j in range(0, 9):
if in_sd_matrix[i][j] != 0:
continue
# 尝试填 1 ~ 9 数字
fail_cnt = 0
for t_num in range(1, 10):
# 判断当前位置是否可以填数字num
if can_fit(in_sd_matrix, i, j, t_num):
in_sd_matrix[i][j] = t_num # 尝试填数字
flag = depth_fit_num(in_sd_matrix) # 递归
if flag is False:
fail_cnt += 1 # 这里也代表不能填数字
else:
fail_cnt += 1 # 不能填的数字个数
# 如果该空格 1~ 9都不能填，说明该路径行不通
if 9 == fail_cnt:
in_sd_matrix[i][j] = 0 # 回溯
return False
return True/<code>
depth_fit_num() 递归填数字，参数 in_sd_matrix 是一个数组（浅拷贝），也就是说，每一次递归，都是在原数组上进行操作。这是一个非常典型的递归的函数。我们假设输入的数独一定存在一个或多个解。该递归满足五个步骤：
1. 递归结束条件。在开头 is_full() 函数，一旦数组填满，就结束递归；
2. 递归主体1，双重for循环对9X9宫格进行遍历，对每个空格进行1~9的数字填入
3. 递归主体2，depth_fit_num(), 对矩阵进行深度优先搜索
4. 递归主体3，回溯，如果发现当层递归中，该空格1~9都不能填入，说明上层递归尝试的的数字不对，则当前位置数字回溯重置为0，并 return False 结束当层递归；
5. 递归结束条件，当前层递归循环体全部完成，return True, 结束当层递归。
（ps: 可以使用单步调试，查看每次递归，in_sd_matrix 矩阵的数值变化）
换一种方式说，就是该递归函数，在这个9X9的宫格中，不断去尝试每个位置1~9数字的逐个逐个填入，并判断是否满足数独要求。一旦发现某个位置不满足，就不会继续尝试下去，而是倒回前一个位置尝试其他数字。如此反复。
第五步：规则打印
<code>"""打印矩阵"""
def print_sd(in_sd_matrix, out_sd_matrix, question_type, answer_type):
"""
打印矩阵
:param in_sd_matrix: 输入矩阵
:param out_sd_matrix: 输出矩阵
:param question_type: 问题颜色
:param answer_type: 答案颜色
:return:
"""
head_line = ("+" + "+=====" * 3) * 3 + "++"
mid_line = ("+" + "+-----" * 3) * 3 + "++"
for i in range(len(in_sd_matrix)):
new_line = ''
for j in range(len(in_sd_matrix[i])):
if j == 0: new_line += "||"
if in_sd_matrix[i][j] != 0:
new_line += " %s " % (question_type % str(in_sd_matrix[i][j]))
else:
new_line += " %s " % (answer_type % (str(out_sd_matrix[i][j]) if out_sd_matrix[i][j] != 0 else ' '))
if (j + 1) % 3 != 0: new_line += "|"
elif (j + 1) % 3 == 0: new_line += "||"
if i == 0: print(head_line)
print(new_line)
if (i + 1) % 3 != 0: print(mid_line)
elif (i + 1) % 3 == 0: print(head_line)/<code>
设计好了基础算法，还需要设计输出展示“UI”。这里只是对输出的矩阵进行美化，使得更加可观。同时区分数独题目，和数独求解后的答案。题目是红色标注，填的答案用绿色标注。
第六步：主函数
<code>if __name__ == '__main__':
sd_matrix = [[8, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 6, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 9, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 7, 0, 0, 0],
[0, 0, 0, 8, 4, 5, 7, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 3, 0],
[0, 0, 1, 0, 0, 0, 0, 6, 8],
[0, 0, 8, 5, 0, 0, 0, 1, 0],
[0, 9, 0, 0, 0, 0, 4, 0, 0]]
red_type = "\\033[031m%s\\033[0m"
green_type = "\\033[036m%s\\033[0m"
out_sd_matrix = copy.deepcopy(sd_matrix) # 深复制
print_sd(sd_matrix, out_sd_matrix, red_type, green_type)
depth_fit_num(out_sd_matrix)
print_sd(sd_matrix, out_sd_matrix, red_type, green_type)
print(/<code>
主函数，对输入的矩阵进行深拷贝（主要用于对比题目和答案）。调用之前写好的数独求解的算法。
输入输出：
最后，给一点点学习建议，不懂的时候，先弄明白它的功能以及会使用它，让代码先运行起来。等有时间就一个一个细节去攻破它，编程和写文章一样，需要慢慢积累，加油。
如果有疑问想获取源码，可以关注后，在后台私信我，回复：python数独。 我把源码发你。最后，感谢大家的阅读，祝大家工作生活愉快！
閱讀更多 IT可達鴨 的文章
