华容道求解算法：状态压缩与BFS/A*搜索实现指南

简介：华容道算法的Java与Android实现源码包，面向算法爱好者、移动开发初学者及高校学生，以经典滑块谜题为载体，演示深度优先搜索（DFS）与A*搜索两种求解思路的工程落地。压缩包大小约14.4MB，内含完整的Gradle工程配置、Java源码、Android布局与交互文件，构建脚本与属性文件可帮助还原开发环境，便于直接导入Android Studio运行调试。已有576人学习下载。源码对棋盘状态表示、合法移动规则、启发函数设计、回溯处理以及解路径逆推等关键模块均有清晰实现，界面虽简洁，核心求解逻辑完整，适合用来理解搜索算法在实际应用中的取舍，也可作为课程设计或算法实验的参考项目。通过研读工程结构，还能熟悉Android项目模块划分与构建流程。

1. 华容道的算法实现：值钱的不在移动规则，在状态空间压缩

拿到一份华容道的 Java/Android 源码包，先别急着点运行。华容道这个游戏看起来只是挪棋子，真正让很多实现当场翻车的，是它的状态空间：20 个格子、12 个棋子（1 个 2x2 曹操、5 个横将竖将、4 个 1x1 小兵），全部可行局面的数量级在千万以上。搜索算法写得不讲究，在一部普通手机上解一道经典开局，能把内存吃到几百兆还转半天。这篇想讲清楚的是：华容道的算法实现里，什么才是值钱的部分——状态如何压缩、判重怎么做、BFS 和 A* 怎么选参数，以及从桌面 Java 代码到 Android 应用落地，中间有哪些环节会反复踩坑。适合谁看？要做滑块谜题求解器、要把求解功能嵌进游戏 App、或者想把 BFS/A* 当模板改造成其他谜题的人。纯玩 UI 的可以关掉，这篇不聊皮肤。

2. 状态建模与判重选型：把 4x5 棋盘压成一个 long key

先说结论：BFS 和 A* 人人都能照模板写出来，源码包与源码包之间的水平差距，九成出在状态表示和判重上。同一个局面，用 String 当 key 和用 long 当 key，搜索耗时能差出一个量级；同一套棋子坐标，不排序直接拼字符串，还会出现同一个局面算出两个 key 的灵异现场。这一章把地基打牢，后面才走得稳。

2.1 数据结构：20 格数组 + 棋子坐标表，为什么不用纯坐标

华容道棋盘是 4 行 5 列，共 20 格，出口在最底行的中间两列。我常用的建模是双份结构：一个byte[20]的 grid 存每个格子上的棋子 id，另外维护一个棋子对象数组存每个棋子的宽、高、当前行列。grid 是唯一事实源，移动时同步更新两处。

public class Piece { public int id; // 1=曹操, 2~6=五虎将, 7~10=小兵, 0 保留给空格 public String name; public int w, h; // 曹操 2x2, 横将 2x1, 竖将 1x2, 小兵 1x1 public int row, col; }

为什么不用纯坐标表？纯坐标表省内存，但每次判断两个棋子是否重叠都要做矩形相交，12 个棋子两两比对是 O(n²) 的活，搜索里每个状态要跑几十次，累积起来很可观。grid 方案的移动直接改数组，判断目标区域是否为空只需逐格查值：

// 判断棋子 p 能否平移到 (nr, nc), dir 由 nr/nc 推导 private static boolean canMove(byte[] grid, Piece p, int nr, int nc) { // 边界: 棋盘 4 行 5 列, 棋子右下角不能越界 if (nr < 0 || nc < 0 || nr + p.h > 4 || nc + p.w > 5) return false; // 目标区域不能撞到其它棋子 for (int r = 0; r < p.h; r++) { for (int c = 0; c < p.w; c++) { int cell = grid[(nr + r) * 5 + (nc + c)]; if (cell != 0 && cell != p.id) return false; } } return true; }

逻辑说明：先把棋子平移到新位置，逐格检查新占用的矩形区域。cell != 0 && cell != p.id这个判断是关键——移动前旧位置还没清空，目标区域如果包含自己原来的格子（比如原地判断），要放行；目标区域撞到别的棋子，直接否决。参数说明：nr + p.h > 4是新手最容易写错的地方，4 行棋盘的合法行号是 0~3，一个高 2 的竖将最大能到 row=2（占据 2、3 两行），此时nr + p.h = 4，不越界，所以边界条件是> 4而不是> 3。宽 5 列同理，nc + p.w > 5才是正确上限。

移动的落地操作如下，先清旧位再写新位，顺序不能反：

private static void applyMove(byte[] grid, Piece p, int nr, int nc) { for (int r = p.row; r < p.row + p.h; r++) { for (int c = p.col; c < p.col + p.w; c++) { grid[r * 5 + c] = 0; } } p.row = nr; p.col = nc; for (int r = nr; r < nr + p.h; r++) { for (int c = nc; c < nc + p.w; c++) { grid[r * 5 + c] = (byte) p.id; } } }

这里r * 5 + c是一维化索引，把二维坐标压平。逻辑说明：先擦掉旧区域的棋子 id，再更新棋子坐标，最后把 id 写进新区域。参数说明里有个小习惯：id 用 byte 存，20 格的 grid 数组总共 20 字节，后续做哈希和序列化都轻。别用 int 数组存 20 格，内存翻四倍，在 Android 上没必要。

2.2 三种判重方案：String、long 位压缩、康托展开怎么选

搜索算法每一步都会生成新状态，不去重，BFS 很快就会被同一个棋盘局面反复入队撑爆。判重方案我见过三类，各有适用场景。

String 方案最简单：String key = new String(grid)，byte[20] 直接转，20 个字节当 key。缺点也明显，每个状态都 new 一个 String，BFS 展开几十万节点，GC 能把低端机卡出 ANR。

long 位压缩是我主力方案。20 个格子按格子编码需要 80 bit，long 装不下，但换一个角度：按棋子坐标编码，12 个棋子每个需要行号（4 行，2 bit）+ 列号（5 列，3 bit），共 5 bit，12 个棋子正好 60 bit，一个 long 轻松装下。

// 棋子顺序固定按 id 从小到大, 每个棋子 5 bit: 行 2bit + 列 3bit public static long encode(List<Piece> pieces) { long key = 0; // pieces 必须按 id 排序, 否则同局面不同 key for (Piece p : pieces) { key = (key << 5) | (p.row << 3) | p.col; } return key; }

逻辑说明：每轮循环把已有 key 左移 5 位腾出空间，p.row << 3把行号放到高 2 位，| p.col把列号填进低 3 位。解码时反过来每次取低 5 位即可。参数说明里有两条硬规矩：一，pieces 集合必须按 id 排好序，否则同一个局面因为遍历顺序不同会算出不同的 key，判重直接失效；二，行号占 2 bit 只够表示 0~3，列号 3 bit 表示 0~4，棋盘尺寸变了要重新分配位数。

康托展开是算法竞赛里的经典做法，把全排列映射成一个唯一排名。华容道用它有一层麻烦：棋盘里有 4 个长得一样的小兵，重复元素必须走可重集康托展开，预处理和查询都更复杂。工程里除非对 key 长度有极端要求，否则 long 位压缩已经完全够用，康托更多是教科书价值。

2.3 对称剪枝与固定棋子顺序：两个细节让搜索量直接减半

华容道棋盘左右对称。经典开局里曹操在中轴附近，左右镜像的两个局面如果都入队，等于同一段搜索做两遍。对称剪枝的做法：每次生成新状态后，把棋盘做一次水平镜像，两个局面取 key 较小的那个进 visited。镜像公式：棋子的新列号nc = 4 - (col + w - 1)，行号不变。

// 对状态做水平镜像, 返回镜像后的 key public static long mirrorKey(List<Piece> pieces) { long key = 0; for (Piece p : pieces) { int mirCol = 4 - (p.col + p.w - 1); key = (key << 5) | (p.row << 3) | mirCol; } return key; }

逻辑说明：棋子占的列区间是[col, col + w - 1]，镜像后新区间是[4 - (col + w - 1), 4 - col]，所以新左上角列号就是4 - (col + w - 1)。横向镜像不改变行号，直接复用p.row。参数说明：这个剪枝只在「只求最少步数、不校验具体走法」时开，因为镜像解路径和原路径不完全等价。如果产品要求展示曹操从左上角到右下角的完整动画，镜像剪枝会让动画路径变得不可预期。

另一个细节是固定棋子顺序。上面 encode 里强调按 id 排序，本质是让状态表示唯一。如果 pieces 是 HashMap 或无序 List，同一个局面在 BFS 的父节点和子节点里顺序可能不同，key 就跟着变，visited 里查不到，状态空间直接翻倍。这个坑隐蔽，表现是搜索变慢、结果步数比已知最优步数多，排查时根本想不到是顺序问题。

把状态表示和判重定下来，BFS 才有资格谈提速。下一步就是搜索主循环本身。

3. BFS 求最优解：队列、回溯与双端搜索的提速

BFS 是华容道求解器里最稳妥的底线方案。华容道最优解一般在 15~30 步之间，搜索深度可控，单端 BFS 展开的节点数在数万到数十万之间；配合第 2 章的位压缩判重，桌面 Java 上基本秒出。这一章先把标准 BFS 写对，再讲双端 BFS 怎么把时间和内存一起砍半。

3.1 移动规则与边界条件：一次 move 到底改哪些格子

生成下一步的本质是：枚举每个棋子，尝试 4 个方向，把合法的移动变成一个子状态。方向用 0 上、1 下、2 左、3 右编码，查表取增量。

private static final int[] DR = {-1, 1, 0, 0}; private static final int[] DC = {0, 0, -1, 1}; private static final int[] DIRS = {0, 1, 2, 3}; // 在当前状态 state 上枚举所有合法移动 public static List<Move> expand(byte[] grid, List<Piece> pieces) { List<Move> moves = new ArrayList<>(); for (Piece p : pieces) { for (int dir : DIRS) { int nr = p.row + DR[dir]; int nc = p.col + DC[dir]; if (canMove(grid, p, nr, nc)) { moves.add(new Move(p.id, dir)); } } } return moves; }

逻辑说明：DR和DC是方向和行列增量的映射表，dir 只取 0~3。对每个棋子尝试四个方向，能不能走交给 canMove 判断。这里没有实际修改棋盘，只是记录「哪个棋子往哪个方向走」，真正改棋盘是回溯时逐步 applyMove。参数说明：枚举顺序会影响解路径的偏好，按「上、下、左、右」的固定顺序，解出来的是同一步数下偏向上的路径；产品想要灵活动画，可以在生成后按自定义优先级排序。

边界条件的坑集中在 canMove 里。前面写过的nr + p.h > 4和nc + p.w > 5是尺寸相关的动态边界：宽 2 的横将最右能到 col=3（占据 3、4 列），此时nc + p.w = 5刚好合法。如果有人在代码里写死成nc + p.w > 4，横将永远到不了最右列，最优解直接搜不出来。这类 bug 的特点是：搜索不报错，只是步数比标准答案多 1~2 步。

3.2 标准 BFS 主循环、父指针与路径回溯

BFS 的核心是队列 + visited。每从队列头取出一个状态，判断是否终局，不是就展开所有合法移动入队。visited 用 HashSet 存 long key，因为 BFS 天然保证第一次到达某状态就是最少步数，不需要记录每个状态的步数表。

public static List<Move> bfs(byte[] startGrid, List<Piece> startPieces) { Queue<State> queue = new ArrayDeque<>(); Set<Long> visited = new HashSet<>(); State start = new State(startGrid, startPieces, null, null); queue.offer(start); visited.add(encode(startPieces)); while (!queue.isEmpty()) { State cur = queue.poll(); if (isSolved(cur)) return backtrace(cur); for (Move m : expand(cur.grid, cur.pieces)) { // 深拷贝后应用移动, 生成子状态 State next = applyMoveCopy(cur, m); long key = encode(next.pieces); if (!visited.add(key)) continue; // 已访问, 跳过 next.parent = cur; // 记父指针 next.move = m; queue.offer(next); } } return Collections.emptyList(); // 无解, 正常不会发生 }

逻辑说明：visited.add(key)放在入队前，返回 false 说明这个局面已经见过，直接剪掉。State里带parent和move两个字段，分别指向上一个状态和到达本状态的那一步移动，回溯时从终局沿 parent 链一路走回起点。参数说明：队列用ArrayDeque而不是LinkedList，前者的内存占用和出入队速度都更优；startPieces传入后要在applyMoveCopy里做深拷贝，千万别直接改原对象。

回溯代码是路径输出的关键：

public static List<Move> backtrace(State end) { LinkedList<Move> path = new LinkedList<>(); State cur = end; while (cur.parent != null) { path.addFirst(cur.move); // 头插, 保证从开局到终局的顺序 cur = cur.parent; } return path; }

逻辑说明：addFirst头插是关键，递归到终局后沿 parent 链往回走时，最早的一步在链尾，头插后正好把顺序倒回正向。移动序列里的 Move 只记录棋子 id 和方向，展示层拿到后逐个 applyMove 就能重放棋局。参数说明：这段回溯在双端 BFS 里要做改版——两端各回溯一半再拼接，方向记录里反向段的 dir 需要取反（上变下、左变右），否则拼出来的路径是断的。

3.3 双端 BFS：从出口反向搜，内存和时间一起省

标准 BFS 的瓶颈是 visited 集合随搜索深度指数增长。双端 BFS 的思路：正向从开局搜，反向从所有可能的终局搜，两边各扩展一层，两个 visited 集合一碰撞就找到了解。华容道的反向状态可以宽松定义：曹操占据(2, 1)位置（即最底行中间两列），其他棋子任意摆放，这些局面作为反向搜索的起点集合。

public static List<Move> bidirectionalBfs(byte[] startGrid, List<Piece> startPieces) { Set<Long> forwardVisited = new HashSet<>(); Set<Long> backwardVisited = new HashSet<>(); Queue<State> forwardQueue = new ArrayDeque<>(); Queue<State> backwardQueue = new ArrayDeque<>(); State start = new State(startGrid, startPieces, null, null); forwardQueue.offer(start); forwardVisited.add(encode(startPieces)); // 反向起点: 曹操在 (2,1) 的任一合法布局, 用乱数生成若干开局 for (State s : generateReverseStarts()) { backwardQueue.offer(s); backwardVisited.add(encode(s.pieces)); } while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) { // 每轮各扩展一层, 先扩展队列小的一侧 Set<Long> hit = expandLevel(forwardQueue, forwardVisited, backwardVisited, true); if (hit != null) return mergePath(range(hit), ...); // 反向同理 } return Collections.emptyList(); }

逻辑说明：正反向交替扩展，每次选队列短的一侧先走，碰撞检测是看新状态的 key 是否出现在另一侧的 visited 里。反向搜索的移动规则和正向完全一致——移动是可逆的，从曹操在出口的布局反向走出来的每个状态，都能从对应正向状态一步步推回出口。参数说明：反向起点不宜只放一个终局，因为曹操占出口时其他棋子的排列有多种合法形态，一般随机生成十几个起点覆盖主要分支；expandLevel一次只扩展一层，保证相遇时两边深度之和就是最优步数。

双端 BFS 的实际收益很可观。单端 BFS 展开到第 15 层可能要访问几十万节点，双端两端各扩到七八层就能相遇，内存占用降到三分之一以下。在 Android 低端机上，这个差距是「能跑」和「跑得动」的分界线。代价是代码复杂度上去了——路径合并时要处理反向段的 dir 取反，这个逻辑写错，步数对但动画会鬼畜。

4. A* 启发式搜索：从「能出解」到「秒出解」的调参经验

BFS 是底线方案，但产品经理给的诉求往往是「点一下立刻出结果」。华容道最优解 15~30 步，BFS 的展开量虽说不至于崩，但在低端机上仍有明显延迟。A* 用启发函数指导搜索方向，展开量能降一个数量级。这一章的调参经验是我自己踩出来的，权重的坑尤其隐蔽。

4.1 启发函数 h(n) 的两层设计：曼哈顿距离与阻塞加分

A* 的代价公式f(n) = g(n) + h(n)，g(n) 是已走步数，h(n) 是到目标的预估剩余步数。h 估得越准，搜索越有方向。华容道里 h 有两层常见设计。

第一层是曼哈顿距离：曹操左上角到目标位置的横向加纵向距离。曹操目标在(2, 1)（最底行中间两列），启发式为h1 = (2 - cao.row) + |1 - cao.col|。这个值最大也就 3~4，信息量不够，但它是可采纳的（admissible），不会让 A* 丢掉最优解。

第二层是阻塞加分：曹操出关的正上方路径上有没有棋子压着。具体做法是统计曹操上边界紧邻的那一行里，与曹操列区间重叠的棋子数。竖将、横将一个算 1 分，小兵算 0.5 分。这个加分显著提升搜索效率，但不再保证可采纳，所以它应该作为「加速项」和「最优项」分开控制。

// 启发函数: h1 保证最优性, h2 只做加速 public static int heuristic(List<Piece> pieces, Piece cao, boolean useBlocker) { int h1 = (2 - cao.row) + Math.abs(1 - cao.col); if (!useBlocker) return h1; int blocker = 0; int topRow = cao.row - 1; // 曹操上一行 if (topRow >= 0) { for (Piece p : pieces) { if (p.id == cao.id) continue; // 棋子和曹操列区间有重叠, 且紧贴曹操上方 if (p.row + p.h - 1 == topRow && p.col < cao.col + cao.w && p.col + p.w > cao.col) { blocker += (p.w == 1 && p.h == 1) ? 0 : 1; } } } return h1 + blocker; }

逻辑说明：h1只算曹操左上角到出口的移动距离。blocker统计曹操正上方一行里压在曹操列区间内的棋子，小兵体型小只计 0，将和曹操记 1。参数说明：useBlocker要设计成开关，关掉时 A* 等价于可采纳版本，保证步数最优；打开时搜索提速，但步数可能多 1~2 步。这里p.row + p.h - 1 == topRow判断棋子底边紧贴着曹操上边界，而不是棋子任意位置都算阻塞——只堵在出口正上方才有实际妨碍。

4.2 权重 w 的取值：要最优步数还是要秒出答案

工程实现里通常写成f(n) = g(n) + w * h(n)，w 是调参的重头。这个参数很玄学，我踩过的结论是：w 不是越大越好，它有一个甜点区。

参数说明：w=1 时 h 的可采纳性保证最优，这是兜底配置；w 一旦大于 1，h 被放大，搜索会更快冲向目标，但可能跳过真正的最优路径。我的习惯是：求解器提供两个入口，「标准解」固定 w=1，给玩家看的「参考解」用 w=1.3。注意一个细节：blocker 加分和 w 是叠加关系，blocker 本身已经放大 h 了，w 再放大容易过冲。所以我一般 blocker 开启时把 w 压回 1.0~1.2，避免两个放大因素叠在一起。

A* 的主循环和 BFS 很像，区别在队列换成优先级队列：

// f = g + w * h, 优先扩展 f 最小的状态 PriorityQueue<State> open = new PriorityQueue<>( Comparator.comparingInt((State s) -> s.g + (int) (w * s.h)) );

逻辑说明：每次从 open 里取 f 最小的状态扩展，而不是先进先出。参数说明：Java 的 PriorityQueue 不是线程安全的，算法跑在子线程时没有并发问题；但如果要在搜索过程中实时刷新 UI 进度，需要把当前前沿的 f 最小值通过 Handler 抛回主线程，不要在取元素时直接操作队列。

4.3 内存不够怎么办：用 IDA* 把 open 表换成递归深度

Android 低端机型上，A* 的 PriorityQueue 加 HashMap 可能吃掉 200MB 内存，直接 OOM。这时候该换 IDA*（迭代加深 A*）：不维护 open 表，每轮设定一个 f 阈限，做深度优先搜索，超阈限就剪枝，没搜到就提高阈限重来。

// IDA*: 每轮递归, 用阈限控制搜索范围 public static boolean dfs(State s, int depth, int limit, int w) { int f = s.g + (int) (w * s.h); if (f > limit) return false; // 超过阈限, 剪枝 if (isSolved(s)) return true; for (Move m : expand(s.grid, s.pieces)) { State next = applyMoveCopy(s, m); if (dfs(next, depth + 1, limit, w)) return true; } return false; }

逻辑说明：limit 从初始状态的 f 值开始，每轮加 1。递归深度超过当前阈限就剪掉，直到某轮完整搜出解。内存占用只有递归栈加当前路径，几十 MB 以内。参数说明：depth参数在递归里更多用于调试和统计，实际剪枝依据是 f 和 limit 的比较；w 同样适用，w 越大每轮能搜的深度越浅，但解的步数可能变差。IDA* 的代价是重复计算——每轮加深都会重搜上一轮的节点，华容道深度小，重复成本可以接受。

IDA* 在真机上的表现：解一道 30 步以内的经典开局，通常在几轮之内收敛，单轮展开量也远小于 BFS 的同深度节点数。它的缺点是路径不再保证字典序或某种偏好，如果产品要求动画路径稳定，需要在 DFS 的方向枚举顺序上下功夫。

5. Android 端落地与避坑：别让求解器死在主线程和横竖屏里

算法层跑通了，Android 端是另一片翻车区。求解器本身再快，UI 线程卡一下、转屏丢状态、动画残影，产品体验直接归零。这一章讲透落地时的线程模型、绘制方式和四个高频踩坑点。

5.1 搜索线程与 UI 回调：ExecutorService + Handler 的最小组合

Android 的主线程不允许做耗时操作，华容道搜索虽然在桌面 Java 上秒出，但在低端机上仍有几百毫秒的卡顿风险。标准做法是把搜索扔进线程池，结果通过 Handler 切回主线程。

ExecutorService pool = Executors.newFixedThreadPool(2); Handler mainHandler = new Handler(Looper.getMainLooper()); button.setOnClickListener(v -> { pool.execute(() -> { List<Move> path = solver.solve(startState); mainHandler.post(() -> { stepText.setText("最少 " + path.size() + " 步"); startAnim(path); }); }); });

逻辑说明：pool.execute把搜索任务丢到后台线程，mainHandler.post把结果送回主线程更新 UI。线程池大小 2 足够，搜索任务是 CPU 密集型的，开更多线程反而增加上下文切换。参数说明：搜索期间要禁止用户重复点击按钮，否则会起多个搜索线程互相挤占 CPU；简单做法是点击后先button.setEnabled(false)，回调里再恢复。

5.2 棋盘绘制与移动动画：自定义 View 的全量重绘习惯

棋盘绘制我一般用自定义 View，onDraw 里直接按 grid 逐格画矩形。全量重绘是避免残影的最稳姿势——不要在 onDraw 里做增量绘制或只刷新局部，每次完整画 20 格。

@Override protected void onDraw(Canvas canvas) { super.onDraw(canvas); float cell = Math.min(getWidth() / 5f, getHeight() / 4f); for (int r = 0; r < 4; r++) { for (int c = 0; c < 5; c++) { int id = grid[r * 5 + c]; if (id == 0) continue; // 空格不画 paint.setColor(colorOf(id)); canvas.drawRect( c * cell, r * cell, (c + 1) * cell, (r + 1) * cell, paint ); } } }

逻辑说明：cell取 View 宽高和棋盘行列的比值最小值，保证 4x5 比例不拉伸变形。每个非空格子画一个矩形，颜色按棋子 id 区分：曹操红色、横将竖将蓝色、小兵灰色。参数说明：grid是搜索线程和 UI 线程共享的状态，动画过程中更新 grid 必须放在主线程，否则画到一半看到半移位的棋子；colorOf(id)建议用静态数组存颜色，不要在每帧里做 switch 分配对象。

移动动画用 ValueAnimator 逐帧插值，从旧坐标平移到新坐标。动画结束回调里才真正更新棋子的 row 和 col，动画期间 grid 保持旧值：

ValueAnimator anim = ValueAnimator.ofFloat(0f, 1f); anim.setDuration(300); anim.addUpdateListener(a -> { float t = a.getAnimatedFraction(); float drawRow = oldRow + (newRow - oldRow) * t; float drawCol = oldCol + (newCol - oldCol) * t; // 用 drawRow/drawCol 画移动中的棋子 invalidate(); }); anim.addListener(new AnimatorListenerAdapter() { @Override public void onAnimationEnd(Animator animation) { // 落盘: 把 grid 更新为新位置, 再全量重绘一次 } });

逻辑说明：动画期间棋子用插值坐标绘制，invalidate触发下一次 onDraw；动画结束后才把 grid 真正更新，防止动画过程中搜索线程读到中间态。参数说明：setDuration(300)是滑动谜题的舒适节奏，100ms 内太快看着像闪烁，500ms 以上又拖沓。连续播放多步动画时，要把动画串成队列，不要每步启动一个新动画实例，否则快速点按会动画重叠。

5.3 四个高频翻车点：ANR、内存爆、转屏丢状态、动画残影

这一节是血泪经验的集中区，每条都是「现象 → 原因 → 解决」的排查路径。

第一条：点击求解后界面卡死，几秒后弹出 ANR 对话框。原因九成是 BFS 直接跑在主线程，状态展开几十万次把 UI 线程堵死。解决：搜索全部移到 ExecutorService，回调切主线程；同时给搜索加一个「展开节点数」上限（比如 50 万），防止某些极端关卡把线程池占死。

第二条：搜索过程中内存涨到 200MB 以上，低端机直接 OOM。原因是 visited 里存了完整的 State 对象而不是 long key。解决：visited 只存Long，State 对象用完即弃；队列里只保留待展开节点。如果这样仍爆内存，换 IDA*，它在内存上的优势是结构性的。

第三条：横竖屏切换后棋盘回到初始布局，之前的解步数也没了。原因是 Activity 重建时没有保存搜索状态。解决：在onSaveInstanceState里把 grid 数组和棋子坐标序列化成字符串存起来，onCreate里恢复：

@Override protected void onSaveInstanceState(Bundle outState) { super.onSaveInstanceState(outState); outState.putString("board", boardToString(grid, pieces)); }

逻辑说明：boardToString把 20 格 id 和 12 个棋子的坐标拼成一个固定分隔符的字符串，恢复时按分隔符解析回数组。参数说明：不要直接把 List 对象塞进 Bundle，Android 的 Binder 传输对对象类型有限制，字符串最稳。

第四条：动画播放后棋子残留在错误位置，甚至两个棋子叠在一起。原因是动画结束回调没有把 grid 落盘，或者落盘后没有强制全量重绘。解决：动画结束时先调用applyMove更新 grid，再invalidate()触发完整重绘；绘制逻辑里绝对不要做「只画变化的矩形」这种增量优化，残影九成来自这里。

6. 关卡生成与解轨迹可视化校验：算出来的步数先别急着信

求解器写完了，最容易被忽略的是验证环节。这一章讲三个可以马上用的技巧：怎么生成天然有解的关卡、怎么用文本帧人工核对解路径、怎么用正反向回放做一致性检查。这些都是我交付求解器前必做的流程，少一步都有可能带着隐性 bug 上线。

6.1 从终局反向随机走：生成天然有解的关卡

做游戏关卡时最怕生成一个无解局。最稳的做法是从终局开始反向随机走：曹操先放到出口位置，然后随机做几十步合法移动，由于移动可逆，得到的每个局面都天然有解，且反向走的步数就是该关卡的参考步数。

// 从终局反向随机走 n 步, 生成新开局 public static State generateLevel(int n) { State cur = terminalState(); Random rand = new Random(); for (int i = 0; i < n; i++) { List<Move> moves = expandReversible(cur.grid, cur.pieces); Move m = moves.get(rand.nextInt(moves.size())); cur = applyMoveCopy(cur, m); } return cur; }

逻辑说明：expandReversible和普通 expand 共用同一套 canMove，唯一区别是生成后要过滤掉「上一步的逆操作」，否则随机走容易来回原地打转，实际步数远小于 n。参数说明：n 一般取 20~40，步数太少关卡太简单，太多可能走出绕远路的别扭布局；随机种子固定后同一关卡每次生成相同，方便做关卡编号。

6.2 把解轨迹打印成文本帧：人工核对每一步

解路径能跑通不代表路径正确。最笨也最有效的验证方式是把每一步的棋盘打成文本帧，肉眼逐帧看移动是否连续。

public static void traceFrame(byte[] grid, String tag) { StringBuilder sb = new StringBuilder(tag).append('\n'); for (int r = 0; r < 4; r++) { for (int c = 0; c < 5; c++) { sb.append(grid[r * 5 + c]); } sb.append('\n'); } System.out.println(sb); }

逻辑说明：每帧 4 行 5 列，每个格子打印棋子 id，空格打印 0。逐帧对比时只看相邻两帧：只有一个棋子发生了位移，其他 11 个棋子位置完全不变，这一步就是合法的；如果有两个棋子同时动了，说明 applyMove 期间 grid 被其他逻辑污染了。参数说明：tag用来标注帧序号，比如「step 5 / 21」；id 单字符打印，19 个字符一行刚好能在一屏内看全，不要用中文名打印，会乱。

6.3 正反向回放一致性：求解器交付前的最后一道检查

最后一关是一致性回放。做法很简单：取一条解路径，从开局逐帧回放到终局，再用回溯的逆序从终局返回开局，每一帧的两个哈希必须相等。这一步能同时暴露三件事：路径断裂、方向取反错误、以及 applyMoveCopy 的深拷贝是否干净。

我在交付前会跑一组回归：随机生成 20 个关卡，分别用 BFS（w=1 的 A*）和加权 A* 求解，统计步数差。BFS 的结果作为基准，加权 A* 的步数差全部落在预期范围内才算过。这个习惯救过我很多次，尤其是改过移动枚举顺序之后，明明单局看起来正常，回归一跑就发现某类布局的步数整体偏大。

希望帮到你。

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