简介：这是一份面向Java初学者与算法学习者的八数码问题（滑动拼图）宽度优先搜索实现资源，用于求解3x3面板上数字从初始布局到目标布局的最短移动路径。资源以Java语言编写，借助队列存储待扩展状态、哈希表去重，并记录前驱状态以反向追溯解路径，适合作为BFS入门与状态空间搜索的练手项目。压缩包共19个文件，约29KB，包含3个java源码、3个class编译文件、4个xml与4个properties构建配置，以及jar包、manifest清单和说明文档，覆盖源码、构建脚本与可执行产物，便于直接运行或二次修改。目前已有2037人学习下载。通过阅读源码，读者可掌握状态类设计、邻居状态生成、队列与哈希表配合、路径回溯等关键实现思路，理解BFS为何能保证最短解，并学习Java集合框架与NetBeans工程结构的实际用法。
1. 八数码问题宽度优先搜索：为什么它是最值得手写的状态空间入门题
如果你写过一点 Java，却始终对「状态空间搜索」这四个字没什么体感，八数码问题（8-Puzzle）几乎是最省事的入口。它规则简单到三岁小孩都能玩：3×3 棋盘上放着 1 到 8 八个数字和一个空格，每次只能把空格上下左右相邻的数字滑进来，问从某个乱序局面走到目标局面最少要几步。可就是这么个小玩具，背后藏着状态表示、去重、队列、路径还原这一整套搜索骨架，宽度优先搜索（BFS）把它串成一条线。
我见过太多人卡在「知道 BFS 是按层扩展，但真写起来队列里该存什么、怎么判重、怎么把路径吐出来」这三件事上。这篇就把八数码问题的 BFS 用 Java 从头写一遍，每一步都落到能跑的代码，参数怎么调、哪里容易翻车也一并说清。适合刚学完队列和哈希表、想找一个完整项目练手的同学，也适合想复习搜索模板的老手。
2. 把棋盘变成能进队列的东西：状态表示与判重选型
BFS 的第一道坎不是算法，是「一个棋盘怎么塞进队列」。队列里存的必须是可比较、可哈希、可还原路径的状态对象，而不是二维数组本身。这一章先把状态表示和判重方案定下来，后面所有代码都建立在这个基础上。
2.1 用一维数组还是字符串表示状态
最直觉的做法是用int[3][3]，但数组没有可靠的equals和hashCode，直接丢进HashSet会按引用比较，判重必然失效。常见做法有两种：一是压成一维int[9]，二是压成 9 个字符的字符串。字符串的好处是天然可哈希、打印直观、调试时一眼能看懂；一维数组的好处是移动空格时下标运算更快。
我一般会选字符串，因为八数码的瓶颈几乎永远在状态数量和判重，不在单次移动的常数上。用字符串表示时，空格用字符'0'占位，目标状态就是"123456780"。这样每个状态就是一个String，HashSet<String>直接能用，省掉自己写hashCode的麻烦。
// 目标状态：0 代表空格 public static final String GOAL = "123456780"; // 把二维棋盘压成字符串，方便入队和判重 public static String flatten(int[][] board) { StringBuilder sb = new StringBuilder(9); for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { sb.append(board[i][j]); } } return sb.toString(); }这段代码把任意 3×3 棋盘压成 9 位字符串，顺序是逐行拼接。参数上没什么可调的，唯一要注意的是空格必须统一用'0'，否则目标串对不上。压平之后，判重、入队、打印都围绕这个字符串做，逻辑会干净很多。
2.2 判重为什么必须做，以及用 HashSet 的代价
八数码的状态总数是 9! = 362880，但真正可达的只有一半，约 181440 个。听起来不多，可如果你不做判重，BFS 会在同一层里反复把已经访问过的状态重新入队，队列规模会指数级膨胀，几秒内就能把内存吃满。判重不是优化，是能不能跑完的前提。
判重结构用HashSet<String>就够了，插入和查询都是均摊 O(1)。有人会问要不要用boolean[]按康托展开（Cantor expansion）做完美哈希，把状态映射到 0 到 362879 的下标。那是进阶做法，能把内存压到最小，但代码复杂度上来了。对入门和大多数场景，HashSet完全够用，181440 个字符串的内存占用在现代机器上毫无压力。
// visited 记录已经入过队的局面，防止重复扩展 Set<String> visited = new HashSet<>(); visited.add(start);这里的关键是「入队时标记」而不是「出队时标记」。如果你等出队才visited.add，同一个状态可能在入队前被多个父状态重复发现，队列里会出现大量重复项。这个细节后面避坑章节还会展开。
2.3 空格位置怎么定位和移动
每次扩展一个状态，都要先找到空格在哪，再尝试上下左右四个方向。字符串里空格的下标是indexOf('0')，对应二维坐标就是row = idx / 3、col = idx % 3。移动的本质是交换空格和目标位置的字符。
// 尝试把空格向四个方向移动，返回所有合法的新状态 public static List<String> neighbors(String state) { List<String> result = new ArrayList<>(4); int idx = state.indexOf('0'); int row = idx / 3, col = idx % 3; int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int[] d : dirs) { int nr = row + d[0], nc = col + d[1]; if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue; // 越界跳过 int nIdx = nr * 3 + nc; char[] chars = state.toCharArray(); // 交换空格与相邻数字 chars[idx] = chars[nIdx]; chars[nIdx] = '0'; result.add(new String(chars)); } return result; }dirs数组定义了上下左右四个方向，越界判断保证不会跑到棋盘外。每次交换都新建一个char[]，避免修改原状态。这里返回的是所有一步可达的合法状态，BFS 主循环会拿它逐个判重、入队。参数上唯一能调的是方向顺序，它不影响最短步数，但会影响同层状态的扩展顺序，调试时想固定输出可以按固定顺序写。
3. 宽度优先搜索主循环：队列、层数与路径还原
状态表示定好之后，BFS 主循环就是水到渠成的事。但「最少步数」和「完整路径」是两个不同需求，前者只要层数，后者要记录每个状态从哪来。这一章把两种写法都给出，并说清什么时候用哪种。
3.1 用 Queue 做逐层扩展的最小骨架
BFS 的核心是先进先出队列。Java 里用ArrayDeque当队列比LinkedList更合适，因为它是数组实现，没有链表节点的额外开销，入队出队更快。
// 返回从 start 到 GOAL 的最少步数，无解返回 -1 public static int bfsSteps(String start) { if (GOAL.equals(start)) return 0; Queue<String> queue = new ArrayDeque<>(); Set<String> visited = new HashSet<>(); queue.offer(start); visited.add(start); int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); // 当前层的状态数 for (int i = 0; i < size; i++) { String cur = queue.poll(); for (String next : neighbors(cur)) { if (visited.contains(next)) continue; if (GOAL.equals(next)) return steps + 1; visited.add(next); queue.offer(next); } } steps++; } return -1; // 遍历完所有可达状态仍未到目标，说明无解 }这段代码用size把每一层圈出来，steps记录已经扩展完的层数。当某个邻居等于目标时，返回steps + 1，因为目标出现在下一层。visited在入队前就标记，保证每个状态只进队一次。参数上steps从 0 开始，目标就是起点时直接返回 0，这个边界别漏。
3.2 记录父状态，把最短路径打印出来
只要步数往往不够，面试或作业常要求输出完整移动序列。做法是加一个Map<String, String>记录每个状态的前驱，找到目标后从目标往回倒推，再反转。
// 返回从 start 到 GOAL 的完整状态路径，无解返回空列表 public static List<String> bfsPath(String start) { if (GOAL.equals(start)) return List.of(start); Queue<String> queue = new ArrayDeque<>(); Set<String> visited = new HashSet<>(); Map<String, String> parent = new HashMap<>(); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { String cur = queue.poll(); for (String next : neighbors(cur)) { if (visited.contains(next)) continue; visited.add(next); parent.put(next, cur); // 记录前驱 if (GOAL.equals(next)) return buildPath(parent, start, next); queue.offer(next); } } return Collections.emptyList(); } // 从目标沿 parent 回溯到起点，再反转 private static List<String> buildPath(Map<String, String> parent, String start, String end) { LinkedList<String> path = new LinkedList<>(); String cur = end; while (cur != null) { path.addFirst(cur); if (cur.equals(start)) break; cur = parent.get(cur); } return path; }parent的键是子状态，值是父状态。回溯时从目标一路get到起点，用addFirst插到链表头部，最后天然就是正序。注意parent只在状态第一次被发现时写入，这保证记录的是最短路径上的前驱，而不是某条绕远路的前驱。参数上buildPath的终止条件用cur.equals(start)，别写成parent.get(cur) == null，因为起点的前驱本来就是 null，两者容易混。
3.3 有解无解怎么判断：逆序数那点事
八数码不是所有局面都能走到目标。判断依据是逆序数：把状态去掉空格后按行读成一串，数一数前面比后面大的数对有多少个。如果起点和目标状态的逆序数奇偶性相同则有解，不同则无解。目标"123456780"去掉空格是12345678，逆序数为 0（偶数），所以起点逆序数为偶数才有解。
// 计算逆序数奇偶性，true 表示偶数 public static boolean isSolvable(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; }这个判断放在 BFS 之前，能直接挡掉一半无解输入，省得白跑一遍。参数上只处理去掉空格后的 8 个数字，replace("0", "")把空格剔除。注意这里比较的是字符，'1'到'8'的字符顺序和数字顺序一致，所以直接比大小没问题。
4. 八数码 BFS 的避坑与排查：五个我踩过的坑
代码能跑不代表跑对。八数码的 BFS 有几个特别隐蔽的坑，现象和原因往往对不上号，这一章按「现象 → 原因 → 解决」列五条，都是我实际调试时遇到的。
4.1 队列爆炸、内存溢出
现象：程序跑了几秒后OutOfMemoryError，或者队列长度涨到几百万。原因几乎都是判重没做，或者判重时机错了——在出队时才visited.add，导致同一状态被多个父状态重复入队。解决：把visited.add(next)放在queue.offer(next)之前，入队即标记。另外确认visited用的是HashSet<String>而不是HashSet<int[]>，后者按引用比较，等于没判重。
4.2 步数总是比正确答案多 1
现象：手动数出来 3 步能到，程序返回 4。原因通常是层数计数写错，比如在poll之后才steps++，或者找到目标时返回steps而不是steps + 1。解决：用size锁定当前层，扩展完一整层再steps++；目标在下一层被发现，所以返回steps + 1。起点等于目标这个边界单独返回 0。
4.3 路径打印出来是反的或者缺一段
现象：bfsPath输出的第一个状态是目标而不是起点。原因是回溯时用了add而不是addFirst，或者忘了反转。解决：用LinkedList的addFirst从目标往起点插，插完就是正序；如果用的是ArrayList，记得最后Collections.reverse。另外确认parent只在状态首次被发现时写入，否则可能记录到非最短路径的前驱。
4.4 无解输入让程序空转到天荒地老
现象：输入一个无解局面，BFS 把 18 万个状态全遍历完才返回 -1，体感像卡死。原因是没有提前做可解性判断。解决：在 BFS 之前调用isSolvable，逆序数奇偶性和目标不一致就直接返回无解。这一步能把无解输入的耗时从「遍历全部状态」降到「一次 O(n²) 扫描」。
4.5 字符串拼接用 + 导致性能骤降
现象：状态扩展逻辑没错，但跑大范围测试时明显偏慢。原因是在neighbors里用state.substring加+反复拼字符串，产生大量临时对象。解决：用state.toCharArray()改一个字符再new String(chars)，一次分配搞定。字符串表示本身没问题，问题出在拼接方式上。
5. 从能跑到好用：双向 BFS 与启发式搜索的取舍
单问「最少步数」，单向 BFS 已经够用，18 万个状态在 Java 里通常几百毫秒内出结果。但如果你想把它当成一个能反复调用的求解器，或者想往 A* 方向走，有几个进阶点值得花时间。
第一个是双向 BFS。从起点和终点同时扩展，两边各走一层，当某一状态同时出现在两个visited集合里就相遇了。理论上能把搜索空间从 b^d 降到 2·b^(d/2)，对八数码这种分支因子约 2 到 4 的问题，深一点的局面提速很明显。实现上要维护两个队列、两个parent表，相遇时把两段路径拼起来。代价是代码量翻倍，边界处理（谁先扩展、相遇判定时机）容易写错，建议先把单向版跑通再动。
第二个是 A*。把队列换成优先队列，估价函数用「已走步数 + 曼哈顿距离」。曼哈顿距离是每个数字当前位置到目标位置的横纵距离之和，它是可采纳的（不会高估），所以 A* 找到的仍是最短路径。八数码上 A* 通常比 BFS 少扩展一个数量级的节点。代价是要写比较器、处理优先队列里的重复状态，而且曼哈顿距离算错会直接导致结果非最优，调试成本比 BFS 高。
// 曼哈顿距离：A* 的启发函数，可采纳，不会高估 public static int manhattan(String state) { int sum = 0; for (int i = 0; i < 9; i++) { char c = state.charAt(i); if (c == '0') continue; int target = c - '1'; // 目标位置下标 sum += Math.abs(i / 3 - target / 3) + Math.abs(i % 3 - target % 3); } return sum; }这段代码里c - '1'把字符转成 0 到 7 的目标下标，因为目标串是123456780，数字 1 在下标 0，数字 8 在下标 7。横纵坐标分别用/3和%3算。参数上没什么可调的，但要注意空格跳过，否则会把空格也计入距离。
选型上我的习惯是：只求步数、状态不深，用单向 BFS；要反复求解、状态偏深，上双向 BFS；要最优且想少扩展节点，上 A*。三者不是替代关系，是同一套状态表示和判重逻辑上的三种调度策略，neighbors和isSolvable可以完全复用。
最后一个具体技巧：调试时别只打印步数，把visited.size()也打出来。同一个局面，BFS 扩展的节点数、A* 扩展的节点数、双向 BFS 扩展的节点数，这三个数字能直接告诉你选型对不对。我早期写搜索总盯着结果对不对，后来养成先看扩展节点数的习惯，很多性能问题在结果出错之前就先暴露了。希望帮到你。
本文还有配套的精品资源，点击获取
