简介：这份DOC文档面向数据结构与算法初学者及人工智能课程学习者，围绕经典八数码（滑动拼图）问题，结合C语言代码解析宽度优先搜索的实现思路。内容涉及用Node结构体保存九宫格状态、扩展标记、禁移方向与父节点下标，借助store数组管理已生成状态，并通过left、right、up、down等函数完成空格移动、目标状态判定和结果打印，同时设置TIME=50限制搜索步数，便于理解状态空间搜索、路径回溯及队列式扩展与深度优先策略的差异。资源包为1个doc文件，约40KB，体积轻便，适合课程实验对照与算法复盘。目前已有778人学习，可作为八数码问题入门、C语言搜索程序阅读和BFS/DFS思路比较的参考材料。
1. 没有队列的宽度优先搜索：C 语言八数码实现靠什么维持层序
宽度优先搜索在 C 语言里解八数码问题，教科书答案永远是「配一个环形队列加一份 visited 表」。可眼前这段代码里既找不到queue结构，也没有出队函数，只有一个store[200]数组和一个从 0 数到 49 的for循环，它却真的能在三层深的局面里打出解来。反直觉的点就在这里：BFS 的本质从来不是队列这个容器，而是「先生成的状态先被展开」这条不变量，数组的线性下标天然满足它，队列于是被省掉了。省掉的代价也很实在——原本该由visited承担的判重被降级成banOperate一个字符的方向标记，它只挡得住「一步回头」，挡不住「左-上-右-下绕一圈」。读下去会发现，这份实现把 BFS 最值钱的两样东西，最短性和完备性，都押在了两个char字段上。
2. Node 结构体：九个整数怎么被压成一张带边的图
八数码的搜索空间是一张图，节点是 9 个格子的排列，边是一次空格与相邻数字的交换。要把它塞进 C 语言，第一个决策不是选什么搜索算法，而是怎么表示一个「状态」。这份代码选了最朴素的方式：一个长度 9 的int数组，加三个元信息字段。朴素不等于简单，每个字段背后都对应搜索图上的一个概念，理解了这个映射，后面四个移动函数才读得懂。
2.1 num[9] 的线性布局与 j±1、j±3 的由来
把 3×3 棋盘按行优先拍平成一维，索引 j 与行列的换算就是固定公式：行r = j / 3，列c = j % 3。这一步换算决定了整个实现里所有移动操作的形态。空格左移意味着列减一，也就是j - 1；下移意味着行加一，也就是j + 3。四个方向因此退化成两种整数运算：±1 和 ±3。
typedef struct { int num[9]; /* 行优先拍平的 3x3 棋盘，0 表示空格 */ char expension; /* 'Y' 待展开, 'N' 已展开（出队标记） */ char banOperate; /* 禁止的方向：'L' 'R' 'U' 'D' 'C' 无限制 */ int father; /* 父节点在 store 中的下标，-1 表示根 */ } Node;num[9]这个布局的关键好处是状态复制可以退化成一次定长拷贝，四个移动函数里那句for(k=0;k<9;k++) store[n].num[k]=store[temp].num[k];就是干这个的。用二维数组int num[3][3]也不是不行，但那样每次都得双重循环，而且memcpy的语义不再直观。行优先拍平让「复制父状态 → 交换两个位置 → 得到子状态」变成三步确定性操作，没有中间态，这是后面所有移动函数能长得一模一样的前提。
代价在于越界判定不能再交给行列表达式。左移时j - 1在j = 3的情况下会跑到上一行的末尾去，因为一维数组没有行边界这个概念。所以四个函数必须在动手交换之前，先用索引本身把边界挡住：左边界是j == 0 || j == 3 || j == 6，右边界是j == 2 || j == 5 || j == 8，上边界是j < 3，下边界是j >= 6。这三组魔数看着粗糙，实际是j % 3 == 0、j % 3 == 2、j / 3 == 0、j / 3 == 2的展开形式，编译器会把它们优化成比较指令，比取模除法快。我一般会这么理解：这是用可读性换常数的一个典型取舍，在 1970 年代的计算资源下完全合理，放到今天则值得写个inline函数封装。
2.2 expension 与 banOperate：两个字符编码出的边方向
expension这个名字其实拼错了，本意是 expansion。它的语义是「这个节点还有没有待生成的子节点」，写'Y'表示待展开，写'N'表示已展开。放到标准 BFS 的语境里，它等价于「这个节点是否已经出队」。区别在于标准做法是在出队的那一刻标记，而这份实现是在生成子节点的那一刻顺手把父节点标成'N'，也就是提前标记。提前标记本身没毛病，问题在于它被查询的地方写成了if(store[i].expension='Y')，一个等号，赋值当比较用，表达式恒为真。这个 bug 会在第 5 章单独拆，这里先记住它的设计意图：用一个字符模拟出队标记。
banOperate更有意思，它编码的是「父节点到本节点这条边的反向」。空格左移生成的新状态，禁止右移；右移生成的新状态，禁止左移；上移生成的禁下移；下移生成的禁上移。根节点没有来路，所以标'C'表示四个方向随便走。这一招在搜索树里叫「禁止立即回退」，作用是把每个节点的分支因子从 4 降到 3 左右，减少的分支数量接近四分之一。
但要把话说透：banOperate只挡住了长度为 2 的环，也就是 A→B→A 这种原路返回。长度为 4 的环它挡不住，比如空格左、上、右、下，四个动作之后棋盘回到原样，这在新状态里会被当作一个全新节点生成出来。长度为 6、长度为 8 的环同理。八数码的状态图里环非常多，禁一步回头远远不够，这就是为什么必须有独立的判重机制，而banOperate不能替代判重。两者的职责分工是：banOperate减少无效分支，判重保证每个状态只展开一次。混为一谈，搜索规模就会指数级膨胀。
2.3 father 与路径还原的断裂
father存父节点下标，设计意图很清楚：找到目标之后沿着father一路回溯到-1，就得到一条从初始态到目标态的动作序列。这是链式存储还原路径的标准做法，代价只是每个节点多一个int。
问题出在使用端。printResult()干的事情是for(j=1;j<=n;j++)把store[1]到store[n]全部打出来，这是「生成序列」，不是「解路径」。搜索过程本身确实按层序生成节点，所以打出来的东西看起来像一条逐步变化的过程，但其中绝大多数节点和目标态没有半点关系。真正的路径还原应该是这样：
/* 从目标节点下标 goal 出发，沿 father 链回溯到根，再正序输出 */ void printPath(int goal) { int path[MAXSIZE]; int len = 0; int cur = goal; while (cur != -1) { /* father 为 -1 表示到达初始状态 */ path[len++] = cur; cur = store[cur].father; } for (int k = len - 1; k >= 0; k--) { /* 逆序打印得到正向路径 */ int *p = store[path[k]].num; printf("step %d:\n", len - 1 - k); printf("\t%d\t%d\t%d\n", p[0], p[1], p[2]); printf("\t%d\t%d\t%d\n", p[3], p[4], p[5]); printf("\t%d\t%d\t%d\n", p[6], p[7], p[8]); } }path[]是一个临时栈，长度上限就是搜索深度；len - 1 - k给出的是从初始态算起的步数，因为回溯得到的是逆序，第 0 个元素是目标态。father == -1作为终止条件是根节点的约定，和init()里start.father = -1严格对应。这段代码补上了原实现缺失的一环：father字段存了，但从来没有被读过，等于白占 4 字节。顺带说一句，原printResult从j = 1开始，把store[0]这个初始状态漏掉了，输出里第一步直接是搜索后生成的节点，读的人容易误以为初始态被跳过了。
3. 数组即队列：i 与 n 的双指针为什么等价于层序展开
把队列省掉，靠的是数组下标本身携带顺序信息。这是整份实现里最聪明的一处，也是最容易被误读的一处。很多人第一眼看到for(i=0;i<TIME;i++)加store[n++]，会误判成某种线性扫描，实际上它是一个没有封装的双指针队列，i是读指针，n是写指针，中间那段store[i..n-1]就是待展开的队列。
3.1 生成顺序等于层序的归纳证明
BFS 的正确性依赖一条不变量：深度为 d 的节点一定先于深度为 d+1 的节点被展开。用数组模拟时，这条不变量转化为「父节点下标严格小于子节点下标」，因为子节点只会被追加到当前写指针n的位置，而n单调递增。
归纳一下。初始时队列里只有store[0]，深度 0，成立。假设处理到下标i时，store[0..i-1]已经按深度非降序展开完毕，且store[i..n-1]里所有节点的深度要么等于store[i]的深度，要么比它大 1。展开store[i]时，新生成的子节点深度是store[i].depth + 1，被追加到n之后，仍然满足非降序。所以展开顺序天然是层序，队列的 FIFO 语义被下标序替代了。
这套推理有个隐含前提：搜索图是一棵树，或者说每个状态只被生成一次。一旦出现重复状态，某个深层节点可能生成一个浅层状态，把这个浅层状态重新追加到队尾，层序就破了。这时候最短性会丢，但因为该状态通常在更早的层已经被展开过（如果有判重的话），它的重复副本不会产生新分支，所以影响可控。没有判重的话，浅层状态的重复副本会再次展开，产生一整棵子树，规模失控就从这个点开始。
3.2 n 与 i 的双指针模型与容量语义
原实现里n的初始值是 1，store[0]放初始状态，所以n既表示「已生成节点数」，也表示「下一个空闲槽位的下标」。i从 0 开始，每次循环展开一个节点。用伪码把模型写清楚：
int head = 0; /* 读指针，对应代码里的 i */ int tail = 1; /* 写指针，对应代码里的 n */ store[0] = start_state; while (head < tail) { /* 队列非空的正确条件 */ Node cur = store[head++]; for (每个合法方向 d) { Node child = move(cur, d); if (is_goal(child)) { print_path(); return; } if (!visited(child)) { visited(child) = 1; store[tail++] = child; } } }head < tail是队列空的判据，tail的上界是MAXSIZE，越界之前必须停。原实现把这两个语义混成了一个TIME：既用它当循环上限i < TIME，又用它当容量检查n >= TIME。结果就是队列容量被硬编码成 50，而不是MAXSIZE的 200，宏定义MAXSIZE 200从头到尾没被引用过一次。这种「宏写了但没用」的情况在课程作业里很常见，它不会报错，只会让你以后想调容量的时候发现调了个寂寞。
3.3 循环终止条件的三处错位
原main的骨架值得单独拎出来看：
for (i = 0; i < TIME; i++) { if (store[i].expension = 'Y') { /* 赋值，恒真 */ /* 按 banOperate 分派到 left/right/up/down */ } if (n >= TIME) { /* 生成满 50 个节点就判无解 */ n--; printResult(); printf("Sorry，在所在搜索范围内没有搜索到结果！"); exit(1); } }三处错位叠在一起。第一处，i < TIME限的是展开次数，n >= TIME限的是生成次数，两个计数器不同步，实际能展开的节点数远小于 50，因为每个节点至少生成 2 个子节点，n涨得比i快得多。第二处，n >= TIME这个判据的语义是「生成的节点数到了 50」，和注释里写的「50 步以后仍然没搜到」完全不是一回事，后者应该数 BFS 的层数。第三处，exit(1)表示异常退出，可它同时被用来在找到解时退出（same()命中后也是exit(1)），正常结束和失败结束共用一个退出码，外部脚本没法区分。这三处不影响小规模输入的结果正确性，但决定了程序能不能被信任。
4. 四向移动函数：一次交换背后的边界表与反向边抑制
四个移动函数left、right、up、down加起来一百多行，结构完全一致，差异只在三处：边界判定的索引集合、参与交换的两个下标、写进子节点的banOperate字符。抓住这三处差异，剩下的都是复制粘贴。
4.1 边界判定表与交换下标的对应关系
把四个方向摊开成一张表，读代码时对着查，比逐行啃快得多。
| 函数 | 前置边界判定（命中则返回 0） | 参与交换的两个下标 | 子节点 banOperate | 语义 |
|---|---|---|---|---|
| left | j==0 || j==3 || j==6 | j-1与j | 'R' | 空格与左邻格交换，禁右移 |
| right | j==2 || j==5 || j==8 | j+1与j | 'L' | 空格与右邻格交换，禁左移 |
| up | j==0 || j==1 || j==2 | j-3与j | 'D' | 空格与上邻格交换，禁下移 |
| down | j==6 || j==7 || j==8 | j+3与j | 'U' | 空格与下邻格交换，禁上移 |
左边界那三个值是列 0，右边界是列 2，上边界是行 0，下边界是行 2，全部由j % 3和j / 3展开而来。交换逻辑本身极简：先把父状态整块拷到store[n]，再把空格位置置 0 之外的那个值挪回来。以left为例：
int left(int temp) { int j, k, tempNum; for (j = 0; j < 9; j++) if (store[temp].num[j] == 0) break; /* 定位空格 */ if (j == 0 || j == 3 || j == 6) return 0; /* 已在最左列，非法 */ for (k = 0; k < 9; k++) store[n].num[k] = store[temp].num[k]; /* 整块复制父状态 */ tempNum = store[n].num[j - 1]; /* 暂存左邻格数字 */ store[n].num[j - 1] = 0; /* 空格左移 */ store[n].num[j] = tempNum; /* 原空格位置填入旧左邻值 */ store[temp].expension = 'N'; /* 父节点标记为已展开 */ store[n].banOperate = 'R'; /* 子节点禁右移，防原路返回 */ store[n].expension = 'Y'; store[n].father = temp; if (same(n)) { printResult(); exit(1); } n++; return 1; }temp是父节点下标，返回值1表示成功生成了一个子节点、0表示该方向非法。三个临时变量里，j是空格坐标，k是复制循环变量，tempNum是交换用的中间值。store[temp].expension = 'N'写在生成成功之后而非之前，这样如果left因为越界提前返回，父节点的展开标记不会被误改——不过在这个具体实现里没什么实际意义，因为一个节点总有至少两个合法方向，标记迟早会被改。
4.2 父状态标记与子状态初始化的时序陷阱
仔细观察left里的赋值顺序：先store[temp].expension = 'N'，再store[n].banOperate = 'R'，再store[n].expension = 'Y'。三条语句里，第一条改父节点，后两条初始化子节点。顺序本身不敏感，但把父状态的修改混在子状态的初始化中间，读起来容易漏看。
真正的问题在于赋值的位置。父节点被标'N'，意味着它以后不该再被展开。可store[temp].expension = 'N'是在每个移动函数内部执行的，同一轮循环里四个方向挨个调，第一次left成功就把父标成'N'，后面up、right、down照跑不误——它们并不检查父节点的expension，只检查自己的边界。所以父标记实际起到了作用吗？在if(store[i].expension='Y')这个恒真表达式面前，答案是完全没有。即使把等号改成双等号，父标记也要等到下一轮i递增后才有机会被读到，而那时读到的已经是「这一轮开始时的状态」，检查和不检查没有区别。这是设计意图和实现之间的一道裂缝，不是 bug 本身，但它解释了为什么这个字段存在感这么低。
4.3 平铺调用不是递归，DFS 与 BFS 的分界线在容器
有说法认为这段代码「通过递归调用移动函数，实际上是一种深度优先搜索」。这个判断需要纠正。main里对left、up、right、down的调用是四条并列语句，前一条返回后接着执行下一条，没有任何一条在函数内部再调用自己或调用另一个移动函数去深入下一层。控制流是「展开一个节点，生成它的所有子节点，然后回到 for 循环取下一个节点」，这是标准的迭代式广度优先。
判断 DFS 还是 BFS，看的是待展开节点的取出顺序，不是函数调用长什么样。DFS 会用一个显式栈，或者写成expand(child); expand(child);这样的真递归，让控制流自己往下钻，钻到底再回头。这段代码的控制流始终停留在main的 for 循环那一层，每轮只处理一个节点，所以它是 BFS，只是把队列换成了数组下标。同一层之内子节点的生成顺序（这里是左、上、右、下）会决定解路径的字典序偏好，仅此而已，不影响搜索的层序性质。
5. 排查：五个让八数码 BFS 打出「无解」的真实故障
这段实现在小规模输入下能跑出结果，一旦换个初始局面就开始各种翻车。下面五条是从实际调试里攒下来的，每一条都能独立复现，按症状找原因最快。
5.1 现象：三步就能解的局面，打出一堆状态后报无解
现象很明确，输入一个离目标只差两三次交换的初始状态，程序刷出几十个棋盘，最后打印「在所在搜索范围内没有搜索到结果」。原因不是搜索逻辑错，是容量给错了。TIME被同时当成了循环上限和节点数上限，实际可用的队列槽位只有 50 个，而每个节点平均生成 2 到 3 个子节点，展开到第 15 个节点左右，n就撞到 50 了。八数码平均解长度在 22 步上下，50 个节点远远不够。
解决方式是把两个量拆开：容量用MAXSIZE单独给，按可解状态总数9! / 2 = 181440上取整；深度或者展开次数另设一个计数器，只在需要限制资源时使用。改完之后，如果还是搜不到，再看是不是判重缺失导致队列被重复状态挤爆。
5.2 现象：expension明明是'N'，节点还是被反复展开
if (store[i].expension = 'Y')里是单等号，'Y'的 ASCII 是非零值，整个表达式恒为真，而且副作用是把store[i].expension覆写成'Y'。后果有两层：本来应该跳过的已展开节点被重新展开，生成一整批重复子节点；同时expension字段被污染，'N'标记彻底失效。gcc 加-Wall会给出suggest parentheses around assignment used as truth value的警告，很多人不看警告就跑了。
解决就是改成==，然后把-Wall -Wextra加进编译命令，把这类警告当错误处理。血泪经验是：C 语言里所有if (x = 常量)形式的写法，一律当成 bug 处理，没有例外。
5.3 现象：输出里有一大串棋盘，但看不出哪几步通向目标
printResult()遍历的是store[1]到store[n]，也就是搜索过程中生成的全部节点，按生成顺序排列。这些节点里只有极少数落在真正的解路径上，其余都是旁支。读的人如果以为这是解法步骤，会得到一条根本不成立的移动序列。
解决要动father字段：目标节点命中时，从该下标出发沿father回溯到-1，把路径上的下标压进临时数组，再逆序输出。第 2.3 节给的printPath可以直接用。顺带记得把store[0]这个初始状态也纳进输出，否则第一步看起来像是凭空冒出来的。
5.4 现象：相同棋盘在输出里出现四五次，搜索步数暴涨
banOperate只禁了立即回退，挡不住四步环。空格执行「左-上-右-下」之后回到原位，这个状态会被当作新节点生成，father指向一个不同的父节点，但num[9]和目标状态一模一样。没有判重的话，每个这样的环都产生一整棵重复子树，规模呈指数上升。
解决是引入状态判重。八数码的状态可以用康托展开压成一个 0 到 362879 的整数下标，配一个char visited[362880]位图，占 354KB，查重是 O(1)。也可以用哈希表，但哈希冲突处理在小规模下反而更麻烦。判重的位置要放在入队之前，而不是展开之前，这样重复节点连生成都省了。
5.5 现象：逆序数为奇的初始局面，搜到底也搜不出解
八数码的可解性有严格的判据：忽略空格，把剩下的 8 个数字按顺序读出来，初始序列和目标序列的逆序数奇偶性相同才有解，不同则永远无解。这条判据来自置换群的奇偶性，空格左右移动不改变逆序数，上下移动跨越两个数字，逆序数变化量为偶数，所以奇偶性是搜索可达性的不变量。
拿这份代码里写死的目标态{1,2,3,8,0,4,7,6,5}算一下，去掉 0 得到1,2,3,8,4,7,6,5，逆序对是 (8,4)(8,7)(8,6)(8,5)(7,6)(7,5)(6,5)，共 7 个，奇数。所以任何逆序数为偶数的初始状态都对它无解，包括标准的1,2,3,4,5,6,7,8,0（逆序数 0）。这解释了为什么很多人拿最常见的初始局面去测，怎么都搜不出来，还以为是 BFS 写错了。
解决是在init()之后、搜索之前加一道预判，省掉整轮无效搜索：
/* 忽略 0，计算序列的逆序数。奇偶性不同则两状态不可互达 */ int inversion_parity(const int *a) { int cnt = 0; for (int i = 0; i < 9; i++) { if (a[i] == 0) continue; for (int j = i + 1; j < 9; j++) { if (a[j] == 0) continue; if (a[i] > a[j]) cnt++; } } return cnt & 1; /* 0 偶，1 奇 */ }a是长度 9 的棋盘数组，两层循环枚举所有二元组，cnt记录逆序对数，返回值只保留最低位。调用时比较初始态和目标态的返回值，不同就直接报「目标不可达」，不用进搜索循环。这个函数复杂度是 36 次比较，相对于后面几十万次的状态展开可以忽略不计。
6. 从 9! 到 9!/2：状态编码方案怎么选才不失控
搜索规模的上限由状态空间决定，编码方案决定你能不能在内存里把这张表摊开。九宫格的全排列是9! = 362880，剔除逆序数不匹配的那一半，可解状态是 181440 个。这个数量非常小，小到足以用稠密数组做判重——前提是你选对了编码。
康托展开是这里最契合的工具：给定一个排列，算出它在全排列字典序中的排名，值域正好是0到362879，一一对应，无冲突。算法是逐位统计右侧比当前位小的元素个数，乘以对应阶乘再累加，O(9²)常数极小。用它做下标访问char visited[362880]，只要 354KB，比任何哈希表都省，而且查重是确定的 O(1)，没有冲突处理，没有扩容，没有最坏退化。代价是编码和解码都要遍历数组，每次入队算一遍，几十万次调用下总开销仍然可忽略。
替代方案也值得知道各自的边界。全状态位图用 4 bit 编码每格（0 到 8 共 9 种值），9 格是 36 bit，可以塞进uint64_t，用哈希表存稀疏状态，适合只需要记录已访问而不需要反查的场合。双向 BFS 从初始态和目标态同时展开，把搜索深度从 d 降到 d/2，节点数从 b^d 降到 2·b^(d/2)，在八数码这种分支因子约 2.13、平均解长 22 的问题上收益极其明显，代价是要维护两张表并且判断交集。
| 方案 | 空间 | 单次查重 | 适用场景 |
|---|---|---|---|
| 康托展开 + 位图 | 354KB 固定 | O(9²) 计算 + O(1) 访问 | 状态空间封闭且可枚举，首选 |
| 哈希表 | 按实际节点数线性增长 | 期望 O(1)，有冲突 | 状态空间未知或极大 |
| 双向 BFS | 2 × 深度减半的边界 | 同 BFS | 已知目标态、只求最短路径长度 |
我踩过一次坑：早期图省事用「棋盘数组直接哈希」当 key，哈希函数写得随意，冲突率高，搜索到一万多个节点时性能断崖式下跌，profile 一看全耗在链地址法的遍历上。换成康托展开之后，同一批测试用例的总耗时从十几秒降到一两秒，代码还短了三十行。从那以后我每写一个状态空间封闭的搜索，都强制先算一遍状态总数、选好编码、再动手写展开逻辑，而不是先写搜索再补判重。顺序反过来，往往要推倒重来。希望帮到你。
本文还有配套的精品资源，点击获取
