python实现数独求解

Python实现数独求解通常会使用回溯法（Backtracking），这是一种递归的算法，下面是一个简化的例子：

def solve_sudoku(board):
    def is_valid(row, col, num):
        # 检查行、列和宫格中是否已经有相同的数
        for i in range(9):
            if board[row][i] == num or board[i][col] == num:
                return False
        box_x = (row // 3) * 3
        box_y = (col // 3) * 3
        for i in range(box_x, box_x + 3):
            for j in range(box_y, box_y + 3):
                if board[i][j] == num:
                    return False
        return True

    def fill_cell(row, col):
        nonlocal empty_cells
        if col >= 9:
            row += 1
            col = 0
        if row < 9 and board[row][col] == 0:
            for num in range(1, 10):
                if is_valid(row, col, num):
                    board[row][col] = num
                    empty_cells.remove((row, col))
                    if fill_cell(row, col + 1):  # 递归处理下一行
                        return True
                    board[row][col] = 0  # 如果返回False，恢复该位置并继续尝试下一个数字
            return False  # 无解，回溯
        else:
            return True  # 已经填充完毕，结束递归

    empty_cells = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]
    if not empty_cells:
        return True  # 解已经完成
    fill_cell(0, 0)  # 开始填充第一个空格
    return False  # 未找到解，表示原数独有误

# 使用示例
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("Solution:")
    for row in board:
        print(row)
else:
    print("No solution exists.")

这个例子首先检查每一行、每一列以及每个3x3宫格是否合法，然后递归地填写空格，如果遇到无解的情况就回溯。这是一个基础版的实现，实际项目中可能会添加更多的优化，如剪枝等。