简介：这是一份面向Java初学者与算法学习者的八数码问题宽度优先搜索实现资源，聚焦经典AI搜索问题——3×3滑动拼图的最短路径求解。资源以Java语言编写，借助队列存储待扩展状态、哈希表去重，完整呈现从状态表示、邻居生成到路径回溯的BFS核心流程，适合用于算法课程实验、数据结构练习及面试准备。压缩包共19个文件，约29KB，包含3个java源码文件、3个class编译文件、4个xml与4个properties配置项，以及jar包、manifest清单和说明文档，覆盖源码、构建配置与可执行产物，便于直接运行与二次修改。目前已有2037人学习下载，读者可从中掌握BFS求解八数码的完整思路、状态去重技巧与Java工程组织方式，并借助现成代码快速验证与调试自己的搜索算法实现。
1. 八数码问题宽度优先搜索：从状态空间到 Java 落地的完整拆解
八数码问题（8-Puzzle）是很多算法课和笔试里绕不开的经典搜索题：3×3 棋盘上放着 1 到 8 八个数字和一个空格，每次只能把空格上下左右相邻的数字滑进来，问从初始局面到目标局面最少要走多少步。它看起来简单，但状态空间有 9!/2 = 181440 个可达状态，手推几步就乱，靠人脑枚举基本是玄学。宽度优先搜索（BFS）恰好是这类「每步代价相同、求最短路径」问题的标准解法，而 Java 实现又能把队列、哈希去重、状态编码这些工程细节一次性讲透。这份资源就是围绕八数码的 BFS 求解展开的 Java 实现，适合正在刷算法题、准备机试，或者想搞懂「搜索算法怎么从伪代码变成能跑的程序」的开发者。下面我按自己拆项目的顺序，把状态表示、判重、扩展、路径还原和性能边界一层层说清楚。
2. 状态表示与判重：BFS 能不能跑起来的关键
八数码的 BFS 写不出来，十有八九不是搜索逻辑错，而是状态表示和判重没设计好。棋盘状态怎么存、怎么快速判断「这个局面我见过没有」，直接决定程序是秒出结果还是跑到内存爆掉。
2.1 用一维数组还是字符串表示状态
最直观的表示是二维数组int[3][3]，但它在入队、比较、哈希时都很别扭。常见做法是压成一维：用长度为 9 的数组或字符串，空格用 0 表示。比如目标状态1 2 3 4 5 6 7 8 0就存成"123456780"。
// 用字符串表示状态，空格记为 '0' // 目标状态固定为 "123456780" static final String TARGET = "123456780"; // 一维下标转二维坐标：idx / 3 是行，idx % 3 是列 static int rowOf(int idx) { return idx / 3; } static int colOf(int idx) { return idx % 3; }用字符串的好处是equals和hashCode都是现成的，直接丢进HashSet就能判重，不用自己写比较逻辑。代价是每次扩展状态都要做字符串拼接，状态多的时候会有一定开销。如果追求性能，可以改用int编码：把 9 个数字按位压进一个整数，判重时用boolean[]或位图，速度会快不少。但对入门和大多数机试场景，字符串版本足够清晰，也够快。
2.2 判重为什么必须做，不做会怎样
BFS 是按层扩展的，如果不判重，同一个局面会被从不同路径反复入队。八数码的状态图里有大量环，比如空格左右横跳就能无限产生新节点，队列会指数级膨胀，程序要么卡死要么 OOM。所以判重不是优化，是正确性的一部分。
判重的核心数据结构是「已访问集合」。每从队列取出一个状态，先看它是否在集合里；扩展出的新状态，如果没访问过才入队并标记。这里有个容易翻车的点：标记时机。正确做法是入队时就标记，而不是出队时才标记。否则同一层里多个父节点可能扩展出同一个子状态，导致重复入队。
Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer(start); visited.add(start); // 入队即标记，别等到出队 while (!queue.isEmpty()) { String cur = queue.poll(); if (cur.equals(TARGET)) { // 找到目标，后续做路径还原 break; } for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } }expand负责把当前状态里空格上下左右能换的位置都换一遍，生成合法的新状态。注意边界：空格在第一行就不能再往上，在最后一列就不能往右，越界判断漏一个就会数组越界或者生成非法状态。
2.3 状态扩展的边界处理
扩展逻辑本身不复杂，但边界条件是 bug 高发区。空格的位置决定了它能往哪几个方向走，四个方向都要单独判断。
static List<String> expand(String state) { List<String> result = new ArrayList<>(); int zero = state.indexOf('0'); int r = rowOf(zero), c = colOf(zero); // 上下左右四个方向，用偏移量表示 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] d : dirs) { int nr = r + d[0], nc = c + d[1]; if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue; // 越界跳过 char[] arr = state.toCharArray(); int nIdx = nr * 3 + nc; // 交换空格和目标位置 arr[zero] = arr[nIdx]; arr[nIdx] = '0'; result.add(new String(arr)); } return result; }dirs数组把四个方向的坐标偏移写在一起，比写四段 if 清爽。nr、nc是空格移动后的新坐标，越界就continue。交换时先转char[]，改完再转回字符串，避免频繁创建中间对象。这段代码看着简单，但zero的重新计算、nIdx的换算，任何一个写错都会导致状态错乱，建议写完先拿几个手工能推的局面验证。
3. 路径还原与步数统计：从「能不能解」到「怎么解」
BFS 找到目标状态只完成了一半，实际使用中我们往往还需要知道「最短步数是多少」以及「具体怎么走」。这就需要在搜索过程中记录父节点和移动方向，最后回溯出完整路径。
3.1 用父节点映射还原移动序列
只统计步数的话，可以在队列里存「状态 + 步数」的二元组，或者按层计数。但要还原路径，就得记录每个状态是从哪个状态、朝哪个方向走过来的。常见做法是用两个Map：一个存父状态，一个存移动方向。
Map<String, String> parent = new HashMap<>(); // 子状态 -> 父状态 Map<String, Character> move = new HashMap<>(); // 子状态 -> 移动方向 // 扩展时记录来源 for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); parent.put(next, cur); move.put(next, dirChar); // 'U' 'D' 'L' 'R' queue.offer(next); } }dirChar根据方向偏移生成，比如{-1,0}对应'U'。找到目标后，从TARGET开始沿parent往回走，把move里的方向收集起来再反转，就是完整的移动序列。
List<Character> path = new ArrayList<>(); String node = TARGET; while (parent.containsKey(node)) { path.add(move.get(node)); node = parent.get(node); } Collections.reverse(path); System.out.println("最短步数: " + path.size()); System.out.println("移动序列: " + path);这里有个细节：parent里不包含起始状态，所以循环条件用parent.containsKey(node)正好在回到起点时停止。反转后得到的序列是从起点到目标的顺序，步数就是序列长度。
3.2 步数统计的两种写法与取舍
如果只关心最短步数，不关心路径，可以省掉parent和move，改用按层扩展。每处理完一层，步数加一。
int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); // 当前层的节点数 for (int i = 0; i < size; i++) { String cur = queue.poll(); if (cur.equals(TARGET)) { System.out.println("最短步数: " + steps); return; } for (String next : expand(cur)) { if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } } steps++; // 一层处理完，步数加一 }size在循环开始前固定住，保证只处理当前层的节点，新入队的属于下一层。这种写法内存占用更小，但拿不到具体路径。实际做题时，如果题目只问步数就用这种，问路径就用父节点映射，别为了省事两种混着写，容易把层数算错。
3.3 无解情况的判断
八数码不是所有初始局面都能到达目标。判断有无解用逆序数：把状态按一维展开，忽略空格，数前面比后面大的数字对个数。逆序数为偶数则有解，奇数则无解。BFS 本身也能「判断」——队列空了还没找到就是无解，但那样要遍历完整个状态空间，浪费时间。常见做法是入口先算一次逆序数，无解直接返回。
static boolean solvable(String state) { int inv = 0; char[] arr = state.replace("0", "").toCharArray(); for (int i = 0; i < arr.length; i++) for (int j = i + 1; j < arr.length; j++) if (arr[i] > arr[j]) inv++; return inv % 2 == 0; }目标状态123456780的逆序数是 0（偶数），所以初始状态逆序数为偶数才有解。这个判断在 BFS 之前做一次，能挡掉一批注定跑不出结果的输入。
4. 避坑与排查：八数码 BFS 最容易翻车的五个地方
这段是我自己踩过、也看别人踩过的坑，按「现象 → 原因 → 解决」整理，照着排查基本能覆盖九成问题。
4.1 程序跑很久不出结果
现象：小规模输入秒出，稍微复杂一点的局面跑几分钟没反应，内存持续上涨。原因：判重没生效，或者标记时机错了，导致同一状态反复入队，队列爆炸。解决：检查visited.add是否在queue.offer之前执行；确认expand生成的状态确实被visited.contains拦住了。可以在循环里打印队列大小，正常应该稳定在几万以内，如果一直涨就是判重漏了。
4.2 结果步数比正确答案多
现象：能跑出结果，但步数比标准答案大。原因：按层计数时steps++的位置放错，或者把起始状态也算成了一步。解决：确认steps初始为 0，每处理完一整层再加一；起始状态在steps=0时检查，如果起点就是目标，答案应该是 0 而不是 1。
4.3 数组越界或状态里出现重复数字
现象：抛ArrayIndexOutOfBoundsException，或者生成的状态里数字重复、空格消失。原因：expand里坐标换算写错，交换时把两个位置搞混，或者越界判断漏了某个方向。解决：把rowOf、colOf和nIdx = nr * 3 + nc单独拿出来单元测试，用几个已知坐标验证；交换逻辑写成「先存临时变量再赋值」，别用一行异或交换，容易看花眼。
4.4 无解输入把程序拖死
现象：某些输入永远跑不出结果，也不报错。原因：初始局面本身无解，BFS 遍历完整个状态空间才停。解决：入口先算逆序数，奇数直接返回「无解」，别让 BFS 白跑。这一步能省掉大量无效计算。
4.5 字符串拼接导致性能差
现象：逻辑都对，但状态一多就慢，CPU 占用高。原因：expand里频繁toCharArray和new String，加上HashSet的哈希开销。解决：状态量大时改用int编码 +boolean[]判重；或者用StringBuilder复用缓冲区。机试场景一般不用优化到这步，但要知道瓶颈在哪。
5. 进阶技巧：双向 BFS 与状态编码优化
单问 BFS 能解决八数码，但状态空间大时它还是慢。真正让性能上一个台阶的，是双向 BFS 和整数编码这两个技巧，我在实际跑复杂局面时基本都会用上。
5.1 双向 BFS 把搜索空间砍一半
单向 BFS 从起点一层层往外扩，最坏情况要摸到 18 万状态。双向 BFS 同时从起点和终点扩展，两边在中间相遇就停。理论上搜索深度减半，实际状态数能降一个数量级。
// 双向 BFS 骨架：两个队列、两个 visited Queue<String> q1 = new LinkedList<>(), q2 = new LinkedList<>(); Set<String> v1 = new HashSet<>(), v2 = new HashSet<>(); q1.offer(start); v1.add(start); q2.offer(TARGET); v2.add(TARGET); while (!q1.isEmpty() && !q2.isEmpty()) { // 每轮选较小的队列扩展，平衡两边 if (q1.size() > q2.size()) { Queue<String> tq = q1; q1 = q2; q2 = tq; Set<String> tv = v1; v1 = v2; v2 = tv; } int size = q1.size(); for (int i = 0; i < size; i++) { String cur = q1.poll(); for (String next : expand(cur)) { if (v2.contains(next)) { // 两边相遇，合并步数即为最短 return; } if (!v1.contains(next)) { v1.add(next); q1.offer(next); } } } }关键点是每轮扩展前比较两个队列大小，优先扩小的那边，避免一边跑太远。相遇判断放在扩展新状态时，只要新状态出现在另一边的visited里，就说明找到了最短路径。步数统计要分别记录两边的层数，相遇时相加。
5.2 整数编码与位运算判重
字符串状态在双向 BFS 里开销更明显，因为要同时维护两个HashSet。把状态压成int能显著提速：每个数字占 4 位，9 个数字正好 36 位，塞进long或int（用int需要 4 位 × 9 = 36 位，超出 32 位，所以用long更稳）。
// 把 "123456780" 编码成 long，每个数字占 4 位 static long encode(String s) { long code = 0; for (int i = 0; i < 9; i++) { code = (code << 4) | (s.charAt(i) - '0'); } return code; }判重时用HashSet<Long>替代HashSet<String>，哈希和比较都快得多。如果状态范围可控，还能用boolean[]做位图，但八数码的编码空间是 9! 级别，位图太稀疏，还是HashSet更实际。解码时按 4 位一组取出来还原成字符串或数组，用于扩展。
5.3 一个验证习惯
我每次写完八数码 BFS，都会固定跑三组用例：一组起点即目标（答案 0），一组一步可达（答案 1），一组经典复杂局面（比如123456780反过来打乱几步）。三组都过，基本能确认判重、扩展、步数统计三条链路没问题。从那以后我每次写搜索类代码，都强制先跑「平凡用例 + 边界用例 + 复杂用例」这三板斧，比事后 debug 省太多时间。希望帮到你。
本文还有配套的精品资源，点击获取
