推箱子（"warehouse keeper"）是1980年代的一个谜题：将每个箱子推到目标上。在这个变种中，守卫还必须在目标上结束。棋盘：AI速度：移动次数：0 最优：– 守卫（你） 箱子 目标 箱子在目标上 墙壁 玩的方式与规则 仓库是一个网格。每一步，守卫可以向上、向下、向左或向右移动一个方格。守卫不能走进墙壁或箱子。如果箱子前面的方格（在推的方向上）是空地或目标，守卫可以推一个箱子。每一步只能移动一个箱子，并且可以将箱子从目标上推出来以腾出空间。 控制：箭头键或 W A S D，或屏幕上的控制板。撤销步骤返回。重置恢复棋盘。 目标：当每个可移动的实体——每个箱子和守卫——都坐在一个目标上时，谜题就赢了。因此，每个棋盘都有比箱子多一个目标：最后一个目标是给守卫的。 目标：在尽可能少的移动中达到该状态。对于几个棋盘，已知并显示最优移动次数。 AI（使用可接受的启发式算法）在可以进行穷举搜索的棋盘上返回最优解。 AI 求解器的工作原理 推箱子是一个 A* 搜索问题，但一个天真的版本在拥挤的棋盘上每次只探索一个守卫的步骤时会爆炸。这里运行的是我编写的本地 C++ 最优求解器的 JavaScript 端口。它返回可证明的最少移动次数的解，而不仅仅是某种解：移动最优宏推 A*。每个搜索边都是一个整个箱子的推移，成本为（守卫到推点的最短行走）+ 1，因此总成本是真正的最小守卫移动次数，而搜索跳过个体步伐。紧凑的位掩码状态。箱子被封装到一个 32 位整数中，涵盖棋盘的可达“活动”单元，而守卫则被封装到另一个数字中，因此整个状态是一个约8字节的键，而不是约1 KB 的对象。数以百万计的状态适合十几 MB。拨号桶队列 + 开放寻址哈希。 A* 前沿是一个按成本键控的桶队列，访问集合（带有解决方案的父链接）存在于扁平的类型数组哈希中。无分配和缓存友好。死锁修剪。一个静态死方块表（从目标的反向可达性）加上冻结检查丢弃可证明无法解决的位置，导向一个对墙敏感的推距离下限，使 A* 保持可接受性（因此最优）。 针对棋盘 1–14 的问题，在毫秒级别内实时解决到被证明的最优（上述显示的“最优”的移动次数正是该求解器返回的结果）。棋盘 15，8 箱子迷宫，例外：它的最优搜索探索了约 4900 万个状态，并且需要超过 1 GB，这在浏览器标签中运行会花费太长时间。因此其最优解（184 移动）是通过该算法的本地 C++ 构建离线计算的（一个并行 A* 搜索，在24个核心中约5秒）并通过重放验证，页面简单地播放该预计算的解决方案。这就是为什么棋盘 15 的答案是硬编码的，而不是在这里搜索的原因。基于我的推箱子求解器构建。关于推箱子 →