用python使用广度优先搜索求解八数码问题

在Python中使用广度优先搜索(Breadth First Search, BFS)解决八数码问题（也称为数独游戏），你需要遵循以下步骤：

1. **初始化**：创建一个九宫格二维数组表示数独盘面，初始状态下有部分数字填入，其余位置用0代表待填充的空位。

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]
]

2. **定义BFS函数**：遍历每一层，尝试将1到9的数字填入空位，并检查每一步是否合法（不在行、列或3x3宫格内重复）。

def bfs(board):
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    
    def is_valid(x, y, num):
        # 检查行、列和小宫格
        for dx, dy in directions:
            nx, ny = x + dx * 3, y + dy * 3
            if board[nx][ny] == num:
                return False
        
        row = x // 3
        col = y // 3
        for i in range(3):
            for j in range(3):
                if board[row + i][col + j] == num:
                    return False
        return True
    
    queue = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]
    while queue:
        row, col = queue.pop(0)
        for num in range(1, 10):
            if is_valid(row, col, num):
                board[row][col] = num
                if all(num != 0 for row in board for num in row) and \
                   all(board[i][j] != board[k][l] for i, j, k, l in itertools.permutations(range(9))):
                    return board
                else:
                    board[row][col] = 0
                    queue.extend([(row + dx, col + dy) for dx, dy in directions])

3. **解决问题并返回结果**：调用`bfs(board)`，如果找到解决方案则返回，否则返回空数组表示无法完成数独。

solution = bfs(board)
if solution:
    print("Solved Sudoku:")
    for row in solution:
        print(row)
else:
    print("No solution exists.")