逐步解决数独的Python程序

下面是一个用Python编写的逐步解决数独的程序示例：

def find_empty_cell(board):
    # 寻找数独中的空单元格，返回其行和列位置
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                return row, col
    return None
def is_valid(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 solve_sudoku(board):
    # 逐步解决数独
    empty_cell = find_empty_cell(board)
    if not empty_cell:
        return True  # 数独已解决
    row, col = empty_cell
    for num in range(1, 10):
        if is_valid(board, num, row, col):
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0  # 回溯
    return False  # 数独无解
# 数独示例
board = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
if solve_sudoku(board):
    print("解决的数独：")
    for row in board:
        print(row)
else:
    print("无解")
这个程序使用回溯算法来逐步解决数独。它首先查找数独中的空单元格，然后尝试在该位置插入数字1到9，并检查插入是否有效。如果插入有效，程序将继续递归地解决下一个空单元格，直到数独被解决或找不到有效的插入位置。如果找不到有效的插入位置，程序将进行回溯，将之前插入的数字重置为0，并尝试下一个数字。最终，如果数独被解决，程序将打印解决方案。