python 数独算法

下面是一个基于回溯算法的 Python 数独求解程序：

def solveSudoku(board):
    """
    :type board: List[List[str]]
    :rtype: void
    """
    def isValid(row, col, val):
        for i in range(9):
            if board[row][i] == val or board[i][col] == val or \
               board[3*(row//3)+i//3][3*(col//3)+i%3] == val:
                return False
        return True

    def backtrack():
        nonlocal solved
        for i in range(9):
            for j in range(9):
                if board[i][j] == ".":
                    for k in range(1, 10):
                        if isValid(i, j, str(k)):
                            board[i][j] = str(k)
                            backtrack()
                            if solved:
                                return
                            board[i][j] = "."
                    return
        solved = True

    solved = False
    backtrack()

其中，`board` 是一个 9x9 的二维字符数组，代表数独的初始状态。算法的核心是 `backtrack` 函数，它通过暴力枚举每个空格的可能取值，递归地搜索解空间，并在找到第一个可行解后返回。`isValid` 函数用于判断当前位置填入的数字是否合法。

使用方法如下：

board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
solveSudoku(board)
print(board)

输出结果为：

[
    ["5","3","4","6","7","8","9","1","2"],
    ["6","7","2","1","9","5","3","4","8"],
    ["1","9","8","3","4","2","5","6","7"],
    ["8","5","9","7","6","1","4","2","3"],
    ["4","2","6","8","5","3","7","9","1"],
    ["7","1","3","9","2","4","8","5","6"],
    ["9","6","1","5","3","7","2","8","4"],
    ["2","8","7","4","1","9","6","3","5"],
    ["3","4","5","2","8","6","1","7","9"]
]