Python解数独（回溯算法，代码少于 60 行）

foxiangzun

前些日子折腾起数独游戏，有几关愣是打不过去，算了好久都没结果（智商看来不够。。），于是就考虑要不要开个挂。。（原谅水货的困扰。。），之前学 Java 的时候，不知道从哪里整来了一份代码，正好是针对数独解法的，但是年代久远，已不知出处。。在此先谢过那位贡献原创的大神，于是依葫芦画瓢，用 Python 翻了一版，不多说，代码如下：

1. 
   
2. #coding=utf-8
   
3. 
   
4. #初始化数独的二维数组
   
5. sudoku = [
   
6.         [0, 0, 0, 0, 0, 4, 0, 1, 8],
   
7.         [0, 0, 0, 0, 0, 0, 0, 6, 0],
   
8.         [0, 9, 8, 0, 7, 5, 0, 0, 0],
   
9.         [1, 0, 0, 3, 0, 0, 0, 0, 0],
   
10.         [0, 5, 0, 0, 0, 0, 0, 2, 0],
    
11.         [0, 0, 0, 0, 0, 2, 0, 0, 6],
    
12.         [0, 0, 0, 4, 1, 0, 6, 3, 0],
    
13.         [0, 2, 0, 0, 0, 0, 0, 0, 0],
    
14.         [8, 6, 0, 7, 0, 0, 0, 0, 0]]
    
15. 
    
16. matrix = sudoku[:]
    
17. 
    
18. #验证算法，判断数独内部是否有不合规填充
    
19. def suCheck(row, line, value) :
    
20.         #行与列的验证
    
21.         for i in range(9) :
    
22.                 if (matrix[row][i] == value) or (matrix[i][line] == value) :
    
23.                         return False
    
24.         #小九宫格验证
    
25.         tempRow = row // 3
    
26.         tempLine = line // 3
    
27.         for i in range(3) :
    
28.                 for j in range(3) :
    
29.                         if (matrix[tempRow * 3 + i][tempLine * 3 + j] == value) :
    
30.                                 return False
    
31.         return True
    
32. 
    
33. #递归算法，填充数独
    
34. def backTrace(i = 0, j = 0) :
    
35.         if (i == 8) and (j == 9) :
    
36.                 print('数独填充完毕：')
    
37.                 printSudoku()
    
38.                 return
    
39.         if j == 9 :
    
40.                 i += 1
    
41.                 j = 0
    
42.         if matrix[i][j] == 0 :
    
43.                 for each in range(1, 10) :
    
44.                         if suCheck(i, j, each) :
    
45.                                 matrix[i][j] = each
    
46.                                 backTrace(i, j + 1)
    
47.                                 matrix[i][j] = 0
    
48.         else :
    
49.                 backTrace(i, j + 1)
    
50. 
    
51. def printSudoku() :
    
52.         for i in range(9) :
    
53.                 for j in range(9) :
    
54.                         print(matrix[i][j], end='  ')
    
55.                 print()
    
56.         print()
    
57. 
    
58. backTrace()
    

复制代码

用回溯算法写数独的解法，这里肯定不是第一例了（毕竟很多年前就已经有用 Java 解出来的），但是用 Python 写的回溯，看了很久一直没看懂，不明白中间为何用到那么多的字符串下的 pop() 方法，所以这里把个人觉得最好理解的一套算法展示出来（其实就是借过来用用。。再次声明，非原创。。原创的大神真的找不着了。。）。

好像这里注释写的不“丰满”，如果有疑问可以一起讨论。

罗同学

试了一下，学习了。
发现如果是非唯一解的话，会输出多个解法，这个是怎么实现的属实没看懂

血色的救赎

因为回溯算法，是深度遍历优先，pop函数主要是在存在代码中的递归下面，用来剪枝的。