python数独求解

Python中求解数独问题通常可以使用回溯法（Backtracking）结合数组来实现。以下是一个简单的概述步骤：

1. **初始化**：创建一个9x9的二维数组表示数独盘面，其中0表示空格，其他数字1-9表示已知数值。

2. **递归函数**：定义一个名为`solve_sudoku`的递归函数，该函数接受一个9x9的数组作为输入，并尝试填充下一个空格。

a. 遍历未填空的单元格。
b. 对每个单元格，检查所有可能的数字(1-9)是否满足数独规则（在同一行、列和宫内不允许有相同的数字）。
c. 如果找到一个可行的数字，就将它填入并递归地处理下一个空格。
d. 如果所有可能的数字都不符合条件，则回溯到上一个位置，尝试下一个数字。

3. **主程序**：在一个9x9的初始空盘面上调用`solve_sudoku`函数，当所有空格都被填满时，数独求解完成。

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(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False
    return True

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:  # 找到空位
                for num in range(1, 10):  # 尝试填1-9
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):  # 成功则继续递归，否则回溯
                            return True
                        else:
                            board[row][col] = 0  # 回溯
                return False  # 无法找到合适数字，返回False
    return True  # 所有空位都填写完毕，返回True

# 主程序
board = [[0] * 9] * 9
if solve_sudoku(board):
    print("Sudoku solved:")
    print(board)
else:
    print("No solution exists.")