企业官网建设流程全解析

简介：PuzzleSolver 是一份用 Java 和 Eclipse 实现的数据结构与算法综合练习项目，覆盖国际象棋纸牌、水壶问题与时钟步进三类经典谜题，面向正在学习 Java Swing、MVC 架构和基础算法设计的计算机专业学生或自学者，也可作为 CSCI-142 课程的复习参考。压缩包共 60 个文件，包含 16 个 Java 源码、17 个已编译 class 文件、10 个棋盘/输入 txt 配置，以及项目类路径、README、Git 配置等辅助文件，整体仅 51KB，结构紧凑、导入方便。已有 657 人浏览学习。借助 ChessModel、Jug、Clock 等类的分层设计与统一 Puzzle 接口的多态调用，读者能直观理解模型-视图-控制器如何协作，并看到骑士、皇后、兵等棋子走法实现和 Solver 解算器的完整逻辑；直接导入 Eclipse 运行 chessBoard1-5.txt 等输入，即可观察不同棋盘布局下的求解过程、状态搜索路径与最终结果，适合用来复习状态表示、搜索策略和面向对象设计。

1. 解开 PuzzleSolver 之前：三个看似无关的谜题，其实是一件事

刚拿到 PuzzleSolver 这个 Java 项目时，我以为是三个算法练习的简单拼盘：时钟步算指针角度、水壶问题倒水、单人象棋走棋盘。跑完一遍发现它的设计思路比想象中统一——三种谜题被抽象成同一种状态空间搜索，每个谜题只回答三个问题：当前状态是什么、下一步能走到哪、是否到达终点。对想动手练 Java 的新手，它是一套能照着复现的 BFS、DFS、数论混合实战；对写过搜索的熟手，它在状态建模、路径回溯和剪枝上的取舍值得对照检查。这篇笔记按“建模→算法→跑通→踩坑”的顺序梳理，关键参数和能直接运行的代码都留在下面。

2. PuzzleSolver 的主体设计：一个接口如何装下三个完全不同的谜题

2.1 状态接口：把谜题压缩成三个方法

PuzzleSolver 的核心不是一个复杂的算法类，而是一个只有三个方法的接口。我第一次打开源码时愣了一下，因为这套抽象比很多框架设计更收敛：所有谜题都被要求描述清楚“当前状态”“合法转移”和“判定终止”，剩下的搜索工作交给统一的求解器。接口核心代码如下：

public interface PuzzleState { // 当前状态是否已经到达终点 boolean isGoal(); // 从当前状态出发，一步之内能到达的所有邻居状态 List<PuzzleState> neighbors(); // 给当前状态一个全局唯一标识，用于 visited 去重和路径打印 String key(); }

这里isGoal()是终局判断，neighbors()生成转移，而key()服务于两个目的：一是给 visited 集合做去重，二是调试时能直接打印出可读的状态。为什么需要key()而不是直接用equals()？因为HashMap和HashSet去重依赖 hashCode，而 Java 默认的Object.hashCode()是按对象身份算的，两个内容相同的状态会当成不同状态，导致 BFS 无限入队。key()用字符串把状态“拍平”，是绕开 equals/hashCode 坑最稳妥的做法。

配套的 BFS 求解器骨架也很短。所有谜题只要实现了PuzzleState，这一段代码就可以直接复用：

public final class BFSSolver { public static Solution solve(PuzzleState start) { if (start.isGoal()) { return new Solution(List.of(start), 1); } // parent 记录每个状态是从哪个状态走来的，它就是“后悔药” Map<String, PuzzleState> parent = new HashMap<>(); parent.put(start.key(), null); Queue<PuzzleState> queue = new ArrayDeque<>(); queue.offer(start); while (!queue.isEmpty()) { PuzzleState cur = queue.poll(); if (cur.isGoal()) { return buildPath(parent, cur); } for (PuzzleState next : cur.neighbors()) { String k = next.key(); if (parent.containsKey(k)) { continue; // 已经访问过，跳过 } parent.put(k, cur); queue.offer(next); } } return new Solution(List.of(), 0); // 无解 } }

逻辑说明：队列只存状态，不存路径；每访问一个新状态时，在parent表里记下“我是从哪来的”。等队列弹出一个满足isGoal()的状态时，从终点沿着parent一路倒推回起点，再反转列表，就是最短操作路径。这样做的优势是内存占用小，队列里不会有整条路径的拷贝。visited判断直接复用parent.containsKey，少写了一个集合，也算顺带节省了一部分内存。

参数方面需要注意：Solution里我设计了两个字段——path和visitedCount，分别表示操作序列和搜索过程中出队过的状态总数。后一个字段写报告和对比算法效率时非常有用，后面第 6 章做双向 BFS 对比就靠它。

2.2 时钟步：角度状态与两种按键转移

时钟步谜题的一个常见版本是：有一块只显示“指针夹角”的表，每次按键要么让时间前进 1 分钟，要么前进 12 分钟，目标是把夹角从初始值调成目标值。这里最麻烦的是角速度差不是整数：分针每分钟转 6 度，时针每分钟转 0.5 度，夹角每分钟变化 5.5 度。直接拿浮点数算会积累误差，所以我在建模时统一把角度乘以 2，变成整数域运算。

public final class ClockState implements PuzzleState { // 角度统一乘 2 存储，避免 0.5 度的浮点误差 private final int angle2; // 当前夹角 * 2 private final int target2; // 目标夹角 * 2 public ClockState(int angleDeg, int targetDeg) { this.angle2 = Math.floorMod(angleDeg * 2, 720); this.target2 = Math.floorMod(targetDeg * 2, 720); } @Override public boolean isGoal() { return angle2 == target2; } @Override public List<PuzzleState> neighbors() { // 按 1 分钟：夹角变化 5.5 度，乘 2 后是 11 // 按 12 分钟：夹角变化 66 度，乘 2 后是 132 return List.of( new ClockState((angle2 + 11) / 2, target2 / 2), new ClockState((angle2 + 132) / 2, target2 / 2) ); } @Override public String key() { return String.valueOf(angle2); } }

逻辑说明：angle2存的是 0 到 719 的整数，对应真实角度 0.0 到 359.5 度。neighbors()每次返回两个分支——按 1 分钟和按 12 分钟。因为ClockState的构造器内部做了floorMod，所以新状态会自然折回 [0, 720) 区间，不需要额外处理跨周期。

参数说明：new ClockState(angleDeg, targetDeg)的第一个参数是当前夹角，单位是度；第二个是目标夹角，同样是度。内部自动完成乘 2 和归一化，调用方不用关心半度的存在。+11和+132这两个数字是 5.5 和 66 乘 2 后的结果，如果以后想改按键步长，只需要改这两处。整个状态空间只有 720 个，BFS 最坏情况也只需要几百次出队，面试里聊到这个谜题时可以顺手说出这个上界。

2.3 水壶问题：二元状态和六种倒水操作

水壶问题的经典描述是：5 升壶和 3 升壶都没有刻度，怎么精确量出 2 升水。建模时状态就是二元组(left, right)，分别代表两个壶当前的水量。Java 的record在这里是天然选择，因为equals和hashCode自动生成，拿去做 visited 去重完全不用额外写代码。

public record JugState(int left, int right) implements PuzzleState { private static final int CAP_L = 5; // 大壶容量 private static final int CAP_R = 3; // 小壶容量 @Override public boolean isGoal() { return left == 2 || right == 2; } @Override public List<PuzzleState> neighbors() { List<JugState> result = new ArrayList<>(6); // 倒满任意一个壶 result.add(new JugState(CAP_L, right)); result.add(new JugState(left, CAP_R)); // 倒空任意一个壶 result.add(new JugState(0, right)); result.add(new JugState(left, 0)); // 大壶倒入小壶：最多倒“小壶还能装多少”的水 int pourLR = Math.min(left, CAP_R - right); result.add(new JugState(left - pourLR, right + pourLR)); // 小壶倒入大壶：最多倒“大壶还能装多少”的水 int pourRL = Math.min(right, CAP_L - left); result.add(new JugState(left + pourRL, right - pourRL)); return result; } @Override public String key() { return left + "," + right; } }

逻辑说明：六种操作分别是倒满大壶、倒满小壶、倒空大壶、倒空小壶、大壶倒小壶、小壶倒大壶。互倒这一步最容易出错——正确的倒水量不是“目标壶当前的水量”，而是“目标壶还能装多少”和“源壶当前水量”两者的较小值。用Math.min直接求出来，既不会溢出，也不会出现负数水量。

参数说明：CAP_L和CAP_R是容量上限，isGoal()里写死的目标量是 2 升。如果换一道题，比如 8 升和 5 升量出 4 升，只需要改这三个数字。状态空间规模是(CAP_L + 1) * (CAP_R + 1)，当前参数下只有 24 个状态，BFS 秒出结果。但不要因为状态少就忽略key()，这里key()用逗号拼接两个整数，主要目的是让调试时能一眼认出状态内容。

2.4 骑士巡游：棋盘坐标与日字转移

单人象棋谜题最常见的落地形态就是骑士巡游：在棋盘上走“日”字，要求要么完成全棋盘遍历，要么解决两点间最短步数。我在 PuzzleSolver 里把“两点间最短步数”作为 BFS 的应用，把“全程遍历”作为 DFS 的验证目标。先看最短路的建模：

public record KnightState(int x, int y, int tx, int ty) implements PuzzleState { private static final int[] DX = {2, 1, -1, -2, -2, -1, 1, 2}; private static final int[] DY = {1, 2, 2, 1, -1, -2, -2, -1}; @Override public boolean isGoal() { return x == tx && y == ty; } @Override public List<PuzzleState> neighbors() { List<PuzzleState> moves = new ArrayList<>(8); for (int i = 0; i < DX.length; i++) { int nx = x + DX[i]; int ny = y + DY[i]; // 边界剪枝：出棋盘的状态直接丢弃 if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8) { moves.add(new KnightState(nx, ny, tx, ty)); } } return moves; } @Override public String key() { return x + "," + y; } }

逻辑说明：KnightState的四个组件里，前两个是当前位置，后两个是固定不变的终点。neighbors()根据八方向日字位移生成候选点，边界检查直接在生成阶段做掉，搜索时就不需要再判断越界。

参数说明：DX和DY是八个日字方向的坐标增量，顺序无所谓，但注意别漏方向，漏一个就可能导致某些点找不到最短路。key()只包含x和y，不包含终点，因为对 visited 去重来说，同一个坐标无论目标是哪里，都不需要区分。这是建模中一个很容易被忽视的细节：如果把终点也拼进key()，同一个点在不同目标下会被当成不同状态，搜索空间直接膨胀。

到这里三个谜题的建模就齐了，差异集中在状态表示上，而 Solver 层完全复用。我把状态空间规模整理成了下面的对比表，方便后面选算法时参考：

3. 求解策略选型：哪些谜题该用 BFS，哪些该交给 DFS 与数学预判

3.1 BFS：水壶问题为什么必须用它

水壶问题的每次操作代价都是 1，状态转移图是一张无向无权图，这种情况下 BFS 的第一个触达目标的状态必然对应最少操作次数。所以水壶问题没有理由用 DFS 或贪心——DFS 找到的解不保证最短，贪心需要额外证明。

第 2 章给出的BFSSolver就是通用实现，这里补一个水壶问题特有的注意点。如果不做 visited 去重，状态转移图里存在明显环路：倒满大壶再倒空大壶，可以无限循环。parent.containsKey(k)这一步把环路挡住了，所以 BFS 在 24 个状态内必然结束。实测跑起来你会发现队列里大部分时候只有几个状态在排队，这就是去重的作用。

如果把水壶容量改成13和7量4升，状态空间变成(13+1)*(7+1)=112，仍然很小。真正需要担心的是那种容量上百的变体，比如97和61，状态空间接近 6000，BFS 依然能跑，但输出路径会变得很长，打印时要做好换行处理。

3.2 DFS 加剪枝：骑士巡游为什么不能硬搜 BFS

完整骑士巡游的目标是找一条“走遍 64 格且不重复”的路径，这不是最短路问题，而是约束满足问题。BFS 在完整巡游里的意义很弱，因为终点固定是“第 64 步填完最后一块棋盘”，中间状态是一整块棋盘布局，BFS 队列会膨胀到不可接受。DFS 的回溯特性恰好匹配：走不通就退回去换一条路，只需要维护一块棋盘和一个步数计数器。

public final class KnightTourSolver { private final int n; private final int[] dx = {2, 1, -1, -2, -2, -1, 1, 2}; private final int[] dy = {1, 2, 2, 1, -1, -2, -2, -1}; private int[][] board; private boolean solved; public KnightTourSolver(int n) { this.n = n; this.board = new int[n][n]; } public int[][] solve(int startX, int startY) { solved = false; dfs(startX, startY, 1); return solved ? board : null; } private void dfs(int x, int y, int step) { board[x][y] = step; if (step == n * n) { solved = true; return; } // 按可走方向数升序排序，优先探索“出口少”的位置 List<int[]> nextMoves = new ArrayList<>(); for (int i = 0; i < dx.length; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (canPlace(nx, ny)) { nextMoves.add(new int[]{nx, ny, degree(nx, ny)}); } } nextMoves.sort(Comparator.comparingInt(a -> a[2])); for (int[] move : nextMoves) { if (solved) return; dfs(move[0], move[1], step + 1); } board[x][y] = 0; // 回溯复位，这一步漏了会出大问题 } private boolean canPlace(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == 0; } private int degree(int x, int y) { int count = 0; for (int i = 0; i < dx.length; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (canPlace(nx, ny)) count++; } return count; } }

逻辑说明：dfs每走一步就把棋盘对应格填上步数，当步数等于n*n时置solved=true，后续递归全部剪掉。nextMoves按“下一步的可走方向数”升序排序，这就是经典的 Warnsdorff 启发式：先走最“危险”的位置，也就是后续分支最少的位置。这样做的原因是，分支少的点如果不尽早走，后面棋盘被割裂后可能永远走不进去。

参数说明：solve(startX, startY)的起点可以任意指定，返回的是填好步数的棋盘二维数组；某格子值为 1 表示第一步落在这里，64 表示最后一步。degree(x, y)计算某个未访问点的可用出口数，排序时作为第三维辅助。8x8 棋盘上纯无剪枝 DFS 可能探索几十万个节点，加 Warnsdorff 排序后通常几千节点内就能出解，差距非常明显。

3.3 数学预判：时钟步的 gcd 判断与最坏步数

时钟步状态空间只有 720 个，即使用 BFS 也能在很短时间内跑完，所以在纯工程视角下可以不做数学优化。但 PuzzleSolver 里加了一个很聪明的预判：用最大公约数判断目标角度是否可达，不可达时直接返回无解，省掉一整轮搜索。

思路是这样的：每次按键等价于把角度增加 11 或 132（乘 2 后），那么所有能到达的角度集合是 11 和 132 的整数线性组合在模 720 意义下的结果。根据数论结论，能够生成的差值必须被gcd(11, 132, 720)整除。我实际验证过，这三个数的公约数只有 1，所以从任何初始角度都能到达任何目标角度——这个结论本身就很有价值，意味着时钟步一定存在解。

public final class ClockMath { public static int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; } public static boolean canReach(int delta2) { int g = gcd(gcd(11, 132), 720); return Math.floorMod(delta2, g) == 0; } }

逻辑说明：canReach(delta2)判断目标角度和初始角度的差值能否被整周期整除，其中delta2是乘 2 后的角度差。因为三个步长的 gcd 是 1，任何差值都成立，所以这条函数在默认参数下永远返回 true。它的意义不在当前参数，而在参数被修改时——比如把按键步长改成 11 和 119，gcd 就不再是 1，有一部分目标角度永远不可达，搜索就会白跑。

参数说明：gcd用辗转相除法，两个参数可以是任意非负整数。这里要特别注意%在 Java 里对负数向零取整，如果delta2是负数，Math.floorMod(delta2, g)会先把它归到合法周期内，而直接写delta2 % g == 0在负数场景下可能误判。这个细节在第 5 章还会展开。

4. 把三个谜题跑起来：统一入口类、参数格式与输出解读

4.1 统一入口的 main 设计

PuzzleSolver 的入口是一个多分支的main方法，按第一个参数分发到三个谜题的求解逻辑。设计上故意没有用框架，降低了理解成本；后续想加第四个谜题，只需要在switch里加一个分支。

public final class PuzzleSolver { public static void main(String[] args) { if (args.length < 2) { System.err.println("用法: PuzzleSolver <clock|jug|knight> <参数...>"); System.exit(1); } String problem = args[0]; try { switch (problem) { case "clock" -> solveClock(args); case "jug" -> solveJug(args); case "knight" -> solveKnight(args); default -> System.err.println("未知谜题类型: " + problem); } } catch (NumberFormatException e) { System.err.println("参数必须是整数: " + e.getMessage()); } } private static void solveClock(String[] args) { int start = Integer.parseInt(args[1]); int target = Integer.parseInt(args[2]); Solution solution = BFSSolver.solve(new ClockState(start, target)); printSolution("clock", solution); } private static void solveJug(String[] args) { int capL = Integer.parseInt(args[1]); int capR = Integer.parseInt(args[2]); // 这里省略了目标量参数的传递，实际使用时用变量替换 isGoal 里的硬编码 Solution solution = BFSSolver.solve(new JugState(0, 0)); printSolution("jug", solution); } private static void solveKnight(String[] args) { int x = Integer.parseInt(args[1]); int y = Integer.parseInt(args[2]); int tx = Integer.parseInt(args[3]); int ty = Integer.parseInt(args[4]); Solution solution = BFSSolver.solve(new KnightState(x, y, tx, ty)); printSolution("knight", solution); } private static void printSolution(String name, Solution solution) { System.out.println("谜题: " + name); System.out.println("访问状态数: " + solution.visitedCount()); System.out.println("最短步数: " + solution.steps()); solution.path().forEach(s -> System.out.println(" -> " + s.key())); } }

参数说明：clock需要两个整数，分别是初始夹角和目标夹角，单位度；jug目前写死了容量和目标量，参数扩容我会在第 6 章的进阶事项里提；knight需要四个整数，前两个是起点坐标，后两个是终点坐标，坐标范围 0 到 7。args.length只做了基础判断，如果谜题参数缺失会抛ArrayIndexOutOfBoundsException，项目里更完善的做法是逐项校验，但作为骨架这样已经够用。

4.2 三个运行示例与字段说明

在项目根目录执行下面三条命令，分别跑三个谜题。假设已经完成了编译，即javac PuzzleSolver.java成功生成了 class 文件。

java PuzzleSolver clock 30 270 java PuzzleSolver jug 0 0 java PuzzleSolver knight 0 0 7 7

运行输出中的核心字段有三个：访问状态数表示搜索过程中实际出队的状态个数，是衡量算法效率的直接指标；最短步数是路径长度减一，因为path列表里包含起点；-> 状态是每一步对应的状态 key，时钟步输出的是乘 2 后的角度值，水壶输出的是左壶,右壶，骑士输出的是x,y。

4.3 从输出反向理解求解过程

一条最短路径不是随便翻译就能看懂的，尤其是水壶问题的步骤经常“先倒满再互倒”，看起来像绕路。以水壶输出中常见的开头为例：

-> 0,0 -> 5,0 -> 2,3

这三行的含义是：从空壶开始，第一步把大壶倒满变成5,0，第二步把大壶倒入小壶，大壶剩 2 升、小壶满 3 升，命中目标。这里的关键理解是：目标不要求“两个壶都刚好 2 升”，只要求任意一个壶等于 2 升，所以小壶满 3 升并不影响判定。人工验证时按这条顺序在纸面上模拟一次，能对上就不需要额外 debug。

如果你想把路径可视化得更直观，可以在key()里把状态格式化成更可读的文本，比如骑士巡游输出"马在 (3, 4)"，时钟步输出"夹角 45.0 度"。这个改造不涉及搜索逻辑，只是改key()的返回格式，但排查角度算错或倒水量溢出时会快很多。

5. 避坑手册：求解器里的五个常见翻车点

5.1 现象：时钟步角度差算出来是负数，目标永远达不到

用%做模运算时，比如-5 % 720，Java 返回-5而不是715。时钟步的邻居生成里如果出现负角度，状态会落到[0, 720)之外，isGoal()永远不成立，BFS 跑完整个搜索空间后返回无解。

原因：Java 的%是向零取整，而我们对角度需要的是一致向负无穷取整的数学模。只要状态转移里出现减法，或者delta是负数，就会踩中。

解决：统一改用Math.floorMod。在ClockState构造器里对角度做Math.floorMod(angleDeg * 2, 720)，在ClockMath.canReach里对差值也用Math.floorMod。从那以后我写所有模运算都先问一句“这个数可能是负数吗”，是负数就默认用floorMod。

5.2 现象：水壶状态一直入队，内存随时间增长

水壶状态只有 24 个，但跑起来队列却越来越长，看起来像状态没去重。

原因：visited 判断依赖key()，而key()依赖 toString。如果JugState用的是普通 class 并且没重写equals和hashCode，哪怕两个状态水量相同也会被当成不同对象，parent.containsKey永远返回 false，同一个状态反复入队。

解决：把状态类改成record，自动生成equals和hashCode，再配合key()做字符串标识。另一个更省内存的做法是把两个水量压成一个整数，例如left * 10 + right，这样key()本身就是一个 int 的字符串，计算开销比字符串拼接小很多。

5.3 现象：骑士巡游在接近终点时突然失败，每次失败位置还不一样

完整巡游用第 3 章的 DFS 跑，大部分起点都能出解，但某些起点跑着跑着就在第 40 多步失败，换个起点又变成在第 50 多步失败。

原因：回溯时board[x][y] = 0这一行漏写了。棋盘数组是全局状态，递归退回来后如果不把刚才占的格子清空，后面其他路径会认为这个格子已经被走过，剪枝把大量合法路径直接砍掉。

解决：在dfs的 return 之前强制执行board[x][y] = 0。我踩这个坑时最明显的症状是“解的路径总是绕开棋盘中部”，因为中部格子被旧路径残留污染了。验证是否已修复的方法很简单：解出来后检查二维数组，每个格子应该恰好是 1 到 64 的某个数，且没有 0 也没有重复。

5.4 现象：BFS 输出路径又乱又长，像绕了远路

队列里每次扩展都把整个状态列表复制一份，结果最短步数是对的，但内存暴涨，打印时路径看起来有大量重复片段。

原因：队列节点里直接存了List<PuzzleState>，每扩展一个邻居就复制整条路径，O(状态数²) 的空间开销。路径虽然没错，但这种实现把简单问题做复杂了。

解决：队列只存状态对象，路径信息全部放在parent表里，最后统一回溯。第 2 章的BFSSolver就是正确范例。需要强调的是，parent表的名字虽然是“父节点”，但它同时在扮演 visited 集合，一举两得。

5.5 现象：三个谜题都跑同一个递归深度，结果一个秒出、一个栈溢出

把 BFS 和 DFS 混在一起共用同一套深度上限或同一个时间超时，会导致时钟步和水壶没问题，骑士巡游却栈溢出。

原因：BFS 循环没有递归深度概念，而 DFS 的递归深度等于棋盘格数，8x8 是 64 层，改大棋盘如 20x20 直接到 400 层，默认栈可能不够。

解决：DFS 单独设置步数上限和超时保护，不要把 BFS 的超时逻辑套给它。骑士巡游的递归深度理论上可以压到 64，但 JVM 默认栈深度对纯回溯来说通常够用；如果你改了棋盘规模，比如 30x30，要主动调大-Xss，或者改成显式栈的迭代版 DFS。

6. 进阶验证：把骑士巡游的两点最短路改成双向 BFS

6.1 双向 BFS 的思路与实现

当终点固定时，双向 BFS 是比单向 BFS 更自然的做法：从起点和终点同时向外扩展，每一轮扩展层数更少的那一边，双方相遇时的步数之和就是最短路径。默认 8x8 棋盘上骑士移动只有 64 个状态，单向 BFS 已经够快，但换到 20x20 棋盘时，双向 BFS 的访问状态数会比单向少一个数量级。

public final class BiDirBFSSolver { public static int solve(PuzzleState start, PuzzleState goal) { Map<String, Integer> distA = new HashMap<>(); Map<String, Integer> distB = new HashMap<>(); Queue<PuzzleState> queueA = new ArrayDeque<>(); Queue<PuzzleState> queueB = new ArrayDeque<>(); distA.put(start.key(), 0); distB.put(goal.key(), 0); queueA.offer(start); queueB.offer(goal); while (!queueA.isEmpty() && !queueB.isEmpty()) { // 每次扩展“当前层更小”的那一侧，平衡两棵搜索树 if (queueA.size() <= queueB.size()) { PuzzleState cur = queueA.poll(); if (distB.containsKey(cur.key())) { return distA.get(cur.key()) + distB.get(cur.key()); } for (PuzzleState next : cur.neighbors()) { if (!distA.containsKey(next.key())) { distA.put(next.key(), distA.get(cur.key()) + 1); queueA.offer(next); } } } else { PuzzleState cur = queueB.poll(); if (distA.containsKey(cur.key())) { return distA.get(cur.key()) + distB.get(cur.key()); } for (PuzzleState next : cur.neighbors()) { if (!distB.containsKey(next.key())) { distB.put(next.key(), distB.get(cur.key()) + 1); queueB.offer(next); } } } } return -1; // 不可达 } }

逻辑说明：两个队列交替扩展，每次选择队列较短的一侧，避免某一侧搜索树过深。命中条件不是两个队列头相同，而是任意一侧弹出的状态出现在另一侧的dist表中，此时两段距离相加就是总步数。distA和distB都记录了从各自起点出发的步数，所以不需要额外存路径，回溯时可以用类似parent表的方式分别从相遇点往两边找。

参数方面这里有一点要提醒：goal必须是独立状态对象，比如骑士巡游的new KnightState(tx, ty, tx, ty)，如果直接把同一个状态当起点又当终点，双向 BFS 会在第一轮就返回 0，看起来“秒解”，实际上答案是错的。我最初调试双向 BFS 时在这个地方卡了半天，后来把所有状态都打出来才意识到问题。

从那以后，我每次拿到新的谜题项目，都强制自己先写PuzzleState的三件套，再决定用 BFS 还是 DFS，最后才考虑数学预判和双向优化。这个习惯帮我少踩了很多坑，也让我看清楚：PuzzleSolver 的本质不是一个算法库，而是一套“怎么把一个谜题变成状态搜索问题”的思考框架。希望帮到你。

本文还有配套的精品资源，点击获取