python 回溯法 九宫格

回溯法在解决九宫格问题（即数独问题）时非常常见。九宫格问题是一个填充数独空白格子的问题，要求每一行、每一列和每一个九宫格内都没有重复的数字。

下面是一个使用回溯法解决九宫格问题的示例代码：

def solve_sudoku(board):
    if not find_empty_cell(board):
        return True

    row, col = find_empty_cell(board)

    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num

            if solve_sudoku(board):
                return True

            board[row][col] = 0

    return False

def find_empty_cell(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return i, j
    return None

def is_valid(board, row, col, num):
    # 检查行是否合法
    for i in range(9):
        if board[row][i] == num:
            return False

    # 检查列是否合法
    for i in range(9):
        if board[i][col] == num:
            return False

    # 检查小九宫格是否合法
    start_row = (row // 3) * 3  # 小九宫格的起始行索引
    start_col = (col // 3) * 3  # 小九宫格的起始列索引
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False

    return True

这段代码使用递归的方式进行回溯。`solve_sudoku` 函数会先找到一个空白格子，然后尝试填入数字并判断是否合法。如果合法，则继续递归地尝试下一个空白格子；如果不合法，则回溯到上一个空白格子，尝试其他数字。如果所有格子都填满且合法，就找到了一个解，返回 True。如果无法找到解，则返回 False。

你可以将九宫格问题的初始状态传递给 `solve_sudoku` 函数，它将会返回解决后的九宫格。示例调用代码如下：

board = [
    [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]
]

solve_sudoku(board)

for row in board:
    print(row)

这段代码会输出解决后的九宫格。空白格子用0表示。

希望这个例子对你有帮助！如果你还有其他问题，请随时问我。