八数码难题

GitHub跳转原题关系图返回列表

把九宫格编码为 bytes 状态，从起点 BFS 到固定目标得到最少移动次数。

OJ: luogu

题目 ID: P1379

难度:普及+/提高

标签:BFS状态搜索八数码python

日期: 2026-07-16 20:10

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

每次把空格与上下左右棋子交换，求给定八数码到固定目标的最少步数。

思路

每个棋盘是图上的一个节点，每次合法交换是一条单位边，因此 BFS 第一次到达目标的距离就是最短步数。九个字符直接作为不可变 bytes，可放入字典判重。

预先为九个空格位置计算可交换下标。扩展时转成 bytearray 原地交换，再转回 bytes 作为新状态。

Python 知识

  • collections.deque 提供 O(1)O(1) 队首弹出。
  • distance = {state: 0} 同时承担判重与距离记录。
  • 赋值表达式在邻居推导式中复用行列坐标。

代码

python
import sys
from collections import deque


start = b"".join(sys.stdin.buffer.read().split())
target = b"123804765"
neighbors = [tuple(nr * 3 + nc for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1))
                   if 0 <= (nr := i // 3 + dr) < 3 and 0 <= (nc := i % 3 + dc) < 3)
             for i in range(9)]
queue = deque([start])
distance = {start: 0}

while queue:
    state = queue.popleft()
    if state == target:
        print(distance[state])
        break
    blank = state.index(48)
    for other in neighbors[blank]:
        next_state = bytearray(state)
        next_state[blank], next_state[other] = next_state[other], next_state[blank]
        next_state = bytes(next_state)
        if next_state not in distance:
            distance[next_state] = distance[state] + 1
            queue.append(next_state)

复杂度

可达状态不超过 9!/29!/2，时间和空间均为状态数的线性量级。

总结

状态数量可控且每步代价相同，BFS 是最稳妥的最短路算法。