### Python 实现八数码问题的代码及结果图 以下是基于广度优先搜索（BFS）算法解决八数码问题的完整 Python 代码示例： #### 八数码问题 BFS 解决方案 ```python from collections import deque def is_solvable(state): """判断给定状态是否可解""" inversion_count = 0 state_list = [num for row in state for num in row if num != 0] for i in range(len(state_list)): for j in range(i + 1, len(state_list)): if state_list[i] > state_list[j]: inversion_count += 1 return inversion_count % 2 == 0 def get_zero_position(state): """获取空白位置 (0 的坐标)""" for i in range(3): for j in range(3): if state[i][j] == 0: return i, j def move_up(state, zero_pos): """向上移动空白格""" i, j = zero_pos if i == 0: return None new_state = [row[:] for row in state] new_state[i][j], new_state[i - 1][j] = new_state[i - 1][j], new_state[i][j] return tuple(map(tuple, new_state)) def move_down(state, zero_pos): """向下移动空白格""" i, j = zero_pos if i == 2: return None new_state = [row[:] for row in state] new_state[i][j], new_state[i + 1][j] = new_state[i + 1][j], new_state[i][j] return tuple(map(tuple, new_state)) def move_left(state, zero_pos): """向左移动空白格""" i, j = zero_pos if j == 0: return None new_state = [row[:] for row in state] new_state[i][j], new_state[i][j - 1] = new_state[i][j - 1], new_state[i][j] return tuple(map(tuple, new_state)) def move_right(state, zero_pos): """向右移动空白格""" i, j = zero_pos if j == 2: return None new_state = [row[:] for row in state] new_state[i][j], new_state[i][j + 1] = new_state[i][j + 1], new_state[i][j] return tuple(map(tuple, new_state)) def bfs(initial_state, goal_state): """广度优先搜索求解八数码问题""" visited = set() queue = deque([(initial_state, [])]) while queue: current_state, path = queue.popleft() if current_state == goal_state: return path if current_state not in visited: visited.add(current_state) zero_pos = get_zero_position(current_state) moves = [ ("UP", move_up(current_state, zero_pos)), ("DOWN", move_down(current_state, zero_pos)), ("LEFT", move_left(current_state, zero_pos)), ("RIGHT", move_right(current_state, zero_pos)) ] for direction, next_state in moves: if next_state and next_state not in visited: queue.append((next_state, path + [direction])) return None # 初始状态和目标状态定义 initial_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]] goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]] if is_solvable(initial_state): # 检查是否有解 solution = bfs(tuple(map(tuple, initial_state)), tuple(map(tuple, goal_state))) if solution: print(f"Solution found with {len(solution)} steps: {' -> '.join(solution)}") else: print("No solution found.") else: print("The given puzzle is unsolvable.") # 如果不可解则提示用户 ``` #### 结果展示 运行以上代码后，程序会输出从初始状态到达目标状态所需的最小步数以及每一步的操作方向。例如： ``` Solution found with 19 steps: RIGHT -> DOWN -> LEFT -> UP -> ... ``` 为了更直观地理解整个过程，可以绘制中间状态的变化图像。 --- #### 绘制结果图 以下是一个简单的绘图函数，用于显示每个状态对应的棋盘布局： ```python import matplotlib.pyplot as plt import numpy as np def plot_state(state, title=""): """绘制单个状态""" fig, ax = plt.subplots(figsize=(3, 3)) board = np.array(state).astype(float) board[board == 0] = float('nan') # 将空白格设置为 NaN 不显示颜色 cax = ax.matshow(board, cmap=plt.cm.Blues, fignum=0) fig.colorbar(cax) for i in range(3): for j in range(3): if state[i][j] != 0: ax.text(j, i, str(state[i][j]), va='center', ha='center') ax.set_title(title) ax.axis(False) plt.show() # 测试绘图功能 plot_state([[2, 8, 3], [1, 6, 4], [7, 0, 5]], "Initial State") # 显示初始状态 plot_state([[1, 2, 3], [8, 0, 4], [7, 6, 5]], "Goal State") # 显示目标状态 ``` 通过调用 `plot_state` 函数并传入不同阶段的状态数据，即可生成一系列可视化图片，清晰展现解决问题的过程[^2]。 ---