使用Python编写一个简单的数独求解程序

数独是一种数学谜题，目标是通过填充9x9方格区域中的空白位置，使得每一行、每一列以及每一个3x3的小方格内都包含数字1到9，且每个数字只出现一次。

下面是一个使用Python编写的简单数独求解程序：

def solve_sudoku(board):
    # 检查数独是否已被完全填充
    if is_complete(board):
        return True

    # 查找第一个未填充的位置
    row, col = find_empty(board)

    # 尝试填充数字1到9
    for num in range(1, 10):
        if valid_position(board, num, row, col):
            board[row][col] = num

            # 递归调用函数继续填充下一个位置
            if solve_sudoku(board):
                return True

            # 填充不成功时，回溯到上一个位置
            board[row][col] = 0

    # 所有数字都尝试过仍然无法填充，数独无解
    return False

def is_complete(board):
    # 检查数独是否已被完全填充
    for row in board:
        if 0 in row:
            return False
    return True

def find_empty(board):
    # 查找第一个未填充的位置
    for row in range(len(board)):
        for col in range(len(board[0])):
            if board[row][col] == 0:
                return row, col
    return None

def valid_position(board, num, row, col):
    # 检查对于给定数字，是否在该位置上是有效的
    # 检查所在行是否已包含该数字
    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 = (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

def print_board(board):
    # 打印数独
    for i in range(len(board)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - ")
        for j in range(len(board[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")
            if j == 8:
                print(board[i][j])
            else:
                print(str(board[i][j]) + " ", end="")

# 数独示例
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)
print_board(board)

程序中的solve_sudoku函数使用回溯算法递归地尝试填充空白位置，直到找到合法的解决方案或者确定问题无解。函数is_complete用于检查数独是否已被完全填充，find_empty用于查找第一个未填充的位置，valid_position用于检查给定数字在指定位置是否有效。

在程序示例中，我们使用一个9x9的数独示例进行求解。数独示例中的空白位置用0表示。程序将输出解决方案，如果数独无解则输出空白数独。运行程序后的输出如下所示：

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

可以看到程序正确地解决了数独谜题并输出了解决方案。