python小练习（067）：回溯法（深度优先搜索）求解数独问题
数独的求解其实之前已经有分享过，但是目前正好讲解回溯法（深度优先搜索），就顺便拿过来再分享一下。求解数独问题的过程是非常典型的回溯法的应用。
原始数独：
输出：
源代码：
**** Hidden Message ***** 学习，受教了 谢谢，学习了 厉害 高端 学习 来学习思路 正想要找一些Python习题练习一下，不过这里面的看起来难度挺大 学习 global a
a = [,
,
,
,
,
,
,
,
]
def check(x, y):
global a
flag = 0
for i in range(9):
if a == a:
flag += 1
for j in range(9):
if a == a:
flag += 1
if flag > 2:
return False
else:
return True
def fillblank(x, y):
global a
if x == 9:
input('input a key to stop: ')
print(a)
exit()
if a == 0:
for i in range(1, 10):
a = i
if check(x, y):
if y < 8:
fillblank(x, y + 1)
else:
fillblank(x + 1, 0)
else:
continue
a = 0
else:
if y < 8:
fillblank(x, y + 1)
else:
fillblank(x + 1, 0)
fillblank(0, 0) WelanceLee 发表于 2017-4-25 13:32
有个疑问：如果我在fillblank函数判断终止那儿写 if x == 9：return，那么函数会运行很长时间（没有等到结果），这是为甚吗？ {:5_106:} 膜拜大佬
受教了 本帖最后由 jerryxjr1220 于 2017-4-27 21:58 编辑
WelanceLee 发表于 2017-4-25 13:40
有个疑问：如果我在fillblank函数判断终止那儿写 if x == 9：return，那么函数会运行很长时间（没有等到 ...
你的check函数好像不完整吧？
def check(x, y):
global a
flag = 0
for i in range(9):
if a == a:
flag += 1
for j in range(9):
if a == a:
flag += 1
if flag > 2:
return False
else:
return True
你只检查了横行和竖排不能重复，还有9格的呢？ 数独的规则是3x3的9格内也不允许有重复数字。
而且你这个算法哪怕写得正确也很难算出来，因为你几乎是在穷举每一个可能的值，那你算算81个格子内，每个格子有9个可能，一共有多少种不同的排列组合？ 一共是196627050475552913618075908526912116283103450944214766927315415537966391196809种， 就算每秒钟可以计算100万种，总共需要6e+63年才能算完{:10_256:} {:5_91:} 学习学习 jerryxjr1220 发表于 2017-4-27 21:48
你的check函数好像不完整吧？
你只检查了横行和竖排不能重复，还有9格的呢？ 数独的规则是3x3的9格 ...
原来我连玩法都没搞清楚啊，尴了个大尬~{:5_107:} 学习