简介：面向学习八数码问题与搜索算法的C语言读者，这份文档围绕滑动拼图的状态表示、空格移动规则和宽度优先搜索思路展开，适合作为算法课程实验、课程设计或自学搜索策略时的参考。压缩包内仅含1个doc文件，大小约40KB，篇幅集中，便于快速查阅核心代码与解析。文档涉及Node结构体、目标状态判断、上下左右移动函数、搜索步数上限以及结果打印等实现要点，并特别讨论示例程序与宽度优先搜索在队列使用上的差异，帮助读者理解为何BFS通常能保证最短解、如何用数组模拟队列改造搜索流程。已有779人学习，适合需要对照代码理解八数码状态扩展与搜索策略差异的初学者和算法爱好者。

1. 八数码问题宽度优先搜索：最短步数背后那笔 18 万状态的内存账

三行三列、八个数字块加一个空格，每次把空格上下左右相邻的块挪进来，问从当前局面到123456780最少几步——这就是八数码问题，而宽度优先搜索是绝大多数人写下的第一版解法。它有一个很硬的保证：第一次撞到目标状态时，走的就是最短步数，不需要任何启发式设计，也不用担心像 A* 那样因为估价函数不可采纳而丢掉最优解。

很多人卡在同一个地方：代码逻辑看着没问题，跑到第 18 层附近队列里堆着两万多个待扩展状态，内存一点点涨上去，屏幕上什么都不打印，既不知道是在算还是已经死了。这篇讲的是能真正跑完、能自检、也能横向对比的那一版：状态怎么编码、有解性怎么在入口判掉、判重写在哪一行、路径怎么回溯、跑不动时下一个算法该换什么。适合正在写求解器或课程作业的人，也适合已经写过一版 BFS 但没跑通过的人。

2. 状态编码与有解性判断：先砍掉一半跑不出来的输入

八数码的状态空间是 9 个位置的排列，最直白的写法就是一个长度为 9 的序列加一个"空格在下标几"的标记。麻烦在于，解法一旦开始跑，这个序列就会以每秒几万个的速度生成、哈希、塞进字典——表示方式选错，后面所有的优化都白搭。

2.1 tuple、字符串还是整数打包：由字典里躺多少条决定

三种常见表示各有各的道理，选型的判断依据其实只有一个：同时存活的状态有多少个。

9 元 tuple(1,2,3,4,5,6,7,8,0)最直观，每个元素指向 CPython 缓存好的小整数对象，不额外分配；但一个 9 元 tuple 对象本身就有 56 字节，加上字典槽位、哈希缓存、扩容冗余，一条记录轻松过百字节。9 字符字符串"123456780"在 CPython 下走的是紧凑 ASCII 表示，对象头 49 字节加 9 字节数据，接近 60 字节，比 tuple 略大一点，但哈希更快——字符串的哈希值算一次就缓存在对象里，tuple 每次都要重新遍历元素。真正省的是整数打包：0 到 8 各占 4 bit，9 个位置拼成 36 bit，Python 的 int 用两个 30-bit digit 就装下了，对象 32 字节出头。

我的做法是主实现用字符串，调试方便、打印出来一眼能看懂棋盘；只有在需要反复跑全量 18 万状态做对照实验时，才切到整数编码。整数打包的代码如下，注意这里用的是"每个数字 4 bit、从高位往低位拼"，解包时顺序要跟打包完全一致，否则拿到的棋盘是镜像的：

def pack(state: str) -> int: """9 个 0~8 的数字各占 4 bit，拼成一个 36 bit 整数""" x = 0 for ch in state: x = (x << 4) | (ord(ch) - 48) return x def unpack(x: int) -> str: """必须从低位往高位取，才能还原成从左到右的顺序""" buf = ['0'] * 9 for i in range(8, -1, -1): buf[i] = chr((x & 0xF) + 48) x >>= 4 return ''.join(buf) # 自检：pack/unpack 必须严格互逆，这条断言建议常驻 assert unpack(pack("123456780")) == "123456780"

pack的循环里x << 4相当于给已有内容整体左移四位腾位置，| (ord(ch) - 48)把字符'0'~'8'转成数值 0~8 再填进去。unpack反过来，先取最低四位还原最后一个字符，所以循环变量必须从 8 递减到 0。如果写成从 0 到 8，得到的字符串是反的——而且反过来的字符串依然能通过"长度等于 9"这种粗糙检查，只是棋盘完全对不上，排查起来非常费劲。那句assert别省，它挡掉的是后面几个小时的无头苍蝇。

2.2 逆序数判有解：别让程序白跑 18 万个状态

九宫格的 9! = 362880 种排列里，只有一半能通过合法移动到达目标状态。也就是说随便打乱一个局面，有一半的概率根本无解，而 BFS 对无解输入的表现是：把 181440 个可达状态全跑完，然后返回空。在纯 Python 里这是几十秒的等待，很多人在这一步以为代码死循环了，开始乱改判重逻辑。

判据是逆序数的奇偶性。把空格拿掉，剩下 8 个数字按从左到右、从上到下的顺序排成一列，数这个序列里有多少对"前面的数大于后面的数"，这个计数叫逆序对数。空格左右移动不改变数字的相对顺序；空格上下移动等价于让某个数字在序列里跨过两个位置，逆序对数改变 ±2 或 0。所以逆序对数的奇偶性在整个移动过程中守恒。目标状态123456780去掉空格后是12345678，逆序对数为 0，是偶数，因此起点也必须是偶数才有解。

def is_solvable(state: str) -> bool: """仅适用于 3x3：去掉空格后逆序对数为偶数则有解""" digits = [int(c) for c in state if c != '0'] inv = 0 for i in range(len(digits)): for j in range(i + 1, len(digits)): if digits[i] > digits[j]: inv += 1 return inv % 2 == 0 # 经典无解例子：只交换了最后两个数字，逆序对数为奇数 assert is_solvable("123456780") is True assert is_solvable("123456708") is False

这个函数只有 8 个元素，双重循环最多 28 次比较，成本可以忽略。它应该出现在求解器的第一行：if not is_solvable(start): return None。这里有个边界要提醒——上面这套判据只对奇数宽度的棋盘成立，4×4 之类偶数宽度的滑块拼图，还要额外把空格所在行号加进去，规则不一样，别直接抄。

2.3 用邻居表代替 divmod：扩展函数里最该先改的一行

扩展一个状态要做两件事：找到空格的六个（实际是 2 到 4 个）合法方向、交换后得到新状态。新手版本通常写r, c = divmod(i, 3)然后对四个方向做0 <= nr < 3 and 0 <= nc < 3的边界检查。这段逻辑本身没错，但它在 18 万次扩展、每次扩展 2 到 4 个分支的循环里被执行上百万次，每次都要做除法和四个比较。

棋盘只有 9 个格子，邻居关系是固定的，完全可以预计算成一张表：

# 下标 0~8 对应棋盘从左到右、从上到下；表里是每个格子的合法邻居 NEIGHBORS = ( (1, 3), # 0 左上角 (0, 2, 4), # 1 上边 (1, 5), # 2 右上角 (0, 4, 6), # 3 左边 (1, 3, 5, 7), # 4 中心 (2, 4, 8), # 5 右边 (3, 7), # 6 左下角 (4, 6, 8), # 7 下边 (5, 7), # 8 右下角 ) def move_char(i: int, j: int) -> str: """约定：方向指的是【空格】的移动方向，不是数字块的滑动方向""" if j == i - 3: return 'U' if j == i + 3: return 'D' if j == i - 1: return 'L' return 'R' def expand(state: str): """产出 (新状态, 空格移动方向)，方向约定与 move_char 一致""" i = state.index('0') for j in NEIGHBORS[i]: buf = list(state) buf[i], buf[j] = buf[j], buf[i] yield ''.join(buf), move_char(i, j)

NEIGHBORS把边界判断挪到了模块加载时一次做完，运行时只剩一次列表下标。expand做成生成器是有意的：BFS 主循环经常在找到目标时提前返回，生成器能省掉剩下的分支计算。move_char里的方向约定必须写死在注释里，后面第 5 章会讲这条约定搞反之后会出现什么诡异现象——步数全对，但按序列走不到终点。

3. 宽度优先搜索的骨架：队列、判重时机与父指针回溯

骨架这一层是最容易"看起来对、跑起来不对"的地方。同样是 BFS，判重写在入队前还是出队后，队列用 list 还是 deque，路径存在节点里还是靠父指针回溯，三组选择组合起来，内存占用能差几十倍。

3.1 deque 与分层循环：先把 O(n²) 的坑填掉

队列的第一条铁律：不要用list.pop(0)。Python 的 list 是连续数组，从头部删除要把后面所有元素整体前移一位，单次 O(n)。BFS 的出队次数等于状态数，18 万次出队配上平均长度上万的队列，整体复杂度退化到 O(n²)，表现出来就是前几万次扩展飞快，后面肉眼可见地一卡一卡。collections.deque是双向链表加块状缓冲，popleft()是均摊 O(1)，换成它是一行代码的事。

第二条是关于"要不要分层"。如果只想要最短步数，完全不用显式分层，父指针回溯出来的路径长度天然就是最短的。但如果你要统计每一层有多宽、或者要调试 IDA* 的深度阈值，就需要按层循环：

from collections import deque def bfs_by_layer(start: str, goal: str = "123456780"): """只算最短步数，不还原路径；返回 (步数, 每层宽度列表)""" if start == goal: return 0, [1] seen = {start} q = deque([start]) depth = 0 widths = [1] while q: depth <p> <a href="https://download.csdn.net/download/miyir/1761463" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>