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

foxiangzun

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

#coding=utf-8

#初始化数独的二维数组
sudoku = [
        [0, 0, 0, 0, 0, 4, 0, 1, 8],
        [0, 0, 0, 0, 0, 0, 0, 6, 0],
        [0, 9, 8, 0, 7, 5, 0, 0, 0],
        [1, 0, 0, 3, 0, 0, 0, 0, 0],
        [0, 5, 0, 0, 0, 0, 0, 2, 0],
        [0, 0, 0, 0, 0, 2, 0, 0, 6],
        [0, 0, 0, 4, 1, 0, 6, 3, 0],
        [0, 2, 0, 0, 0, 0, 0, 0, 0],
        [8, 6, 0, 7, 0, 0, 0, 0, 0]]

matrix = sudoku[:]

#验证算法，判断数独内部是否有不合规填充
def suCheck(row, line, value) :
        #行与列的验证
        for i in range(9) :
                if (matrix[row][i] == value) or (matrix[i][line] == value) :
                        return False
        #小九宫格验证
        tempRow = row // 3
        tempLine = line // 3
        for i in range(3) :
                for j in range(3) :
                        if (matrix[tempRow * 3 + i][tempLine * 3 + j] == 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[i][j] == 0 :
                for each in range(1, 10) :
                        if suCheck(i, j, each) :
                                matrix[i][j] = each
                                backTrace(i, j + 1)
                                matrix[i][j] = 0
        else :
                backTrace(i, j + 1)

def printSudoku() :
        for i in range(9) :
                for j in range(9) :
                        print(matrix[i][j], end='  ')
                print()
        print()

backTrace()

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

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

罗同学

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

血色的救赎

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