数独的问题

（1）从第一个空格开始。依次尝试1到9的数字，如果数字与盘面冲突就换成下一个数字，如果不冲突就去往第二个空格。

（2）在第二个空格，同样依次尝试1到9的数字，如果与盘面冲突就换成下一个数字，如果不冲突就去往第三个空格，以此类推。

（3）如果当前空格1到9的数字都填不了，就返回到上一个空格，再依次尝试没有试过的数字，如果与盘面冲突就换成下一个数字，如果不冲突就去往下一个空格。

（4）当最后一个空格被成功填上数字时，将答案加入答案列表。

（5）如果第一个空格填1到9都不成立，那么问题肯定没有解，在这种情况下返回的结果列表为空。

数独和N皇后十分相似，也是一个“前进—后退—前进—后退”的过程，只不过N皇后是一行一行地尝试，而数独是一个空格一个空格地尝试

需要记录当前空格的坐标，用于改变盘面中的数字。所以用一个数字变量表示。如图所示，第1格的index是0，第2格的index是1，第80格的index是79，第81格的index是80。如果给定一个坐标，比如55，通过除以9并取余数，商为6，余数为1，就能得知55代表的是第7行的第2个数.

代码

import copy


# 输出board所有的答案
def sudoku(board):
    # 检查当前数字在盘面中是否成立
    # i是当前行，j是当前列，num是当前数字
    def checkBoard(i, j, num):
        for t in range(9):
            if t != j and board[i][t] == num:  # 检查行
                return False
            if t != i and board[t][j] == num:  # 检查列
                return False

        for t in range(i - i % 3, 3 + i - i % 3):  # 检查3×3区域
            for s in range(j - j % 3, 3 + j - j % 3):
                if t != i and s != j and board[t][s] == num:
                    return False
        return True

    # 填满盘面中第index格到最后一个格
    def helper(index):
        if index == 81:  # 边界条件
            solution = copy.deepcopy(board)  # 深度复制当前盘面，放到res列表里
            res.append(solution)
            return  # 返回到上一次被调用的地方（第80个空格）
        i = index // 9  # 当前行
        j = index % 9  # 当前列
        if board[i][j] == 0:  # 如果当前格没有已知数字
            for num in range(1, 10):  # 依次尝试1～9
                board[i][j] = num
                if checkBoard(i, j, num):
                    helper(index + 1)  # 去往下一个空格
                board[i][j] = 0  # 将空格重新变空
        else:  # 如果当前格是盘面自带的数字
            helper(index + 1)

    res = []
    helper(0)  # 从第一个空格开始
    return res

注意1：如果直接res.append(board)的话，被复制的是指向board的指针，而不是当前board的数值。

注意2：当1～9都不可行时，这时当前格里的数字是9。接着会退回到上一格尝试下一个数字。这时checkBoard会返回False，但当前格的9没有被清除。这并不是期望看到的，因此需要加上board[i]​[j]=0。

输入：

matrix = [[5, 3, 0, 0, 7, 0, 0, 0, 0],
          [6, 0, 0, 1, 9, 5, 0, 0, 0],
          [0, 9, 8, 0, 0, 0, 0, 6, 0],
          [8, 0, 0, 0, 6, 0, 0, 0, 3],
          [4, 0, 0, 8, 0, 3, 0, 0, 1],
          [7, 0, 0, 0, 2, 0, 0, 0, 6],
          [0, 6, 0, 0, 0, 0, 2, 8, 0],
          [0, 0, 0, 4, 1, 9, 0, 0, 5],
          [0, 0, 0, 0, 8, 0, 0, 7, 9]]
result = sudoku(matrix)

输出：