Python解数独（回溯算法，代码少于 60 行）
前些日子折腾起数独游戏，有几关愣是打不过去，算了好久都没结果（智商看来不够。。），于是就考虑要不要开个挂。。（原谅水货的困扰。。），之前学 Java 的时候，不知道从哪里整来了一份代码，正好是针对数独解法的，但是年代久远，已不知出处。。在此先谢过那位贡献原创的大神，于是依葫芦画瓢，用 Python 翻了一版，不多说，代码如下：#coding=utf-8
#初始化数独的二维数组
sudoku = [
,
,
,
,
,
,
,
,
]
matrix = sudoku[:]
#验证算法，判断数独内部是否有不合规填充
def suCheck(row, line, value) :
#行与列的验证
for i in range(9) :
if (matrix == value) or (matrix == value) :
return False
#小九宫格验证
tempRow = row // 3
tempLine = line // 3
for i in range(3) :
for j in range(3) :
if (matrix == value) :
return False
return True
#递归算法，填充数独
def backTrace(i = 0, j = 0) :
if (i == 8) and (j == 9) :
print('数独填充完毕：')
printSudoku()
return
if j == 9 :
i += 1
j = 0
if matrix == 0 :
for each in range(1, 10) :
if suCheck(i, j, each) :
matrix = each
backTrace(i, j + 1)
matrix = 0
else :
backTrace(i, j + 1)
def printSudoku() :
for i in range(9) :
for j in range(9) :
print(matrix, end='')
print()
print()
backTrace()
用回溯算法写数独的解法，这里肯定不是第一例了（毕竟很多年前就已经有用 Java 解出来的），但是用 Python 写的回溯，看了很久一直没看懂，不明白中间为何用到那么多的字符串下的 pop() 方法，所以这里把个人觉得最好理解的一套算法展示出来（其实就是借过来用用。。再次声明，非原创。。原创的大神真的找不着了。。）。
好像这里注释写的不“丰满”，如果有疑问可以一起讨论。
试了一下，学习了。
发现如果是非唯一解的话，会输出多个解法，这个是怎么实现的属实没看懂 因为回溯算法，是深度遍历优先，pop函数主要是在存在代码中的递归下面，用来剪枝的。
页:
[1]