华容道的「81 步」到底是怎么数出来的

做这个华容道游戏的时候，最花时间的不是画界面，是搞清楚一件事：「最少 81 步」这个公认数字，到底是怎么数的。

因为我一开始按「滑动一格算一步」写，求解器给出的最优解是 116 步，跟流传的 81 对不上。当时第一反应是自己写错了，查了半天才发现——两边都没错，是计步的口径不一样。

三种口径，三个答案

还是那个经典布局「横刀立马」。让求解器取最优解，然后按三种方式重新数一遍：

第三种才是文献里用的口径。依据是魏仲良、林順喜那篇《利用電腦探討中國古代益智遊戲─「華容道」之解法》，原文对计步方式的说明是：

若兩個空格相鄰，棋子得以連續移動兩格只算一步。

而且那篇论文表五给的盘面 H##H / H##H / H[]H / HOOH / O O，跟我项目里 横刀立马 的布局逐格一致——引擎独立算出来的也正好是 81 步。

这算是一次交叉验证：我没抄论文的数字，论文的数字也没被我硬凑，两边各自算完对上了。

求解器是怎么做到「随时给最优解」的

棋盘 4×5、10 枚棋子，如果把同类棋子互换视为同一局面，状态空间只有 25955 个，而且四个布局都落在同一个连通分量里。

所以事情就变得很朴素：

1. 从当前局面 BFS 出整个连通分量，收集所有胜利局面；
2. 走法是可逆的，图是无向的，所以从这些胜利局面做一次多源 BFS，就能得到「任意局面到通关的最少步数」；
3. 于是任何时候点「提示」，给的都是当前局面的最优下一步；界面上「还需 N 步」也是精确值，不是估算。

代价是：整张表在 Node 里算完约 0.2~0.8 秒，浏览器里点一次提示约 0.5 秒（算完会缓存）。

这个思路没什么技巧，就是「把状态空间整个吃下来」。25955 个局面小到可以这么干，再大一点就不行了。

自检

node verify.js

会逐个布局跑三种口径的最优解，并且：

• 逐步校验走法合法；
• 核对步数与起点读数；
• 实跑到出口，确认真能通关；
• 校验撤销、越界、撞子的走法确实被拒绝；
• 确认空格数守恒；
• 确认界面上标注的最少步数与实算一致。

端到端也测了：把最优解逐格喂给游戏，计步器正好停在 81 步通关。