用回溯算法八数码问题python代码

回溯算法是一种用于解决约束搜索问题的通用技术，特别是在排列、组合和棋盘游戏等问题中。对于经典的八数码（数独）问题，我们可以编写Python代码如下：

# 八数码问题核心函数，利用递归实现回溯
def solve_sudoku(board):
    if not find_empty_cell(board):  # 检查是否有空格
        return True  # 解决成功，返回True

    row, col = find_next_empty_cell(board)  # 获取下一个空格的位置
    for num in range(1, 10):  # 尝试填充1到9的所有数字
        if is_valid(board, row, col, num):  # 如果该位置填num有效
            board[row][col] = num  # 填入数字
            if solve_sudoku(board):  # 继续寻找剩余解
                return True
            else:  # 回溯，尝试其他数字
                board[row][col] = 0  # 清除并继续

    return False  # 所有数字都试过无效，回溯


# 辅助函数：检查某个位置是否可以填入num
def is_valid(board, row, col, num):
    # 检查行、列和小宫格
    return (
        (row >= 0 and row < 9)
        and (col >= 0 and col < 9)
        and (board[row][col] == 0 or board[row//3*3+row%3][col//3*3+col%3] != num)
    )


# 辅助函数：查找下一个空格
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, None  # 如果无空格则返回None


# 示例用法
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("Sudoku solved!")
else:
    print("No solution exists.")