Python数独回溯算法

以下是一个使用Python实现数独回溯算法的示例代码：

def solve_sudoku(board):
    if not find_empty(board):
        return True
    row, col = find_empty(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(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
    # 检查3x3小方格是否合法
    start_row = 3 * (row // 3)
    start_col = 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False
    return True

# 使用示例
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]
]

if solve_sudoku(board):
    print("解决方案：")
    for row in board:
        print(row)
else:
    print("无解")

这个示例代码使用了一个递归函数solve_sudoku()来解决数独问题。它首先检查是否还有空格需要填充，如果没有，则返回True表示数独已解决。如果还有空格需要填充，则找到一个空格，并尝试填入1到9的数字。然后递归调用solve_sudoku()函数来继续填充下一个空格。如果填入的数字导致数独无解，则回溯到上一个空格，尝试填入下一个数字。如果所有数字都尝试过了都无法解决数独，则返回False表示数独无解。

find_empty()函数用于找到数独中的一个空格，返回其行和列的索引。如果数独中没有空格，则返回None。

is_valid()函数用于检查填入的数字在当前位置是否合法。它分别检查当前行、当前列和当前3x3小方格，确保填入的数字在这三个方向上都没有重复。

最后，使用示例的数独问题调用solve_sudoku()函数来解决数独，并输出解决方案。如果数独无解，则输出“无解”。