AI 工具 · 01

华容道求解器

摆出任意局面,AI 给出最短解法

支持 3×3 八数码和 4×4 十五数码。先用逆序数判断有没有解,再用 IDA* 搜索找最少步数;个别特别难的 4×4 局面超出搜索预算时,会改用加权搜索给出一个较短的解,并明确标注。全部在你的浏览器里计算,不上传任何数据。

f(n) = g(n) + h(n)h = 0 · inv(σ) = 0 · 可解性 –

原理

它是怎么算的

  1. 先判断有没有解所有摆法里恰好一半无解。数一数逆序数(前面的数比后面大的对数)的奇偶就能判断,不用搜索。n 为奇数:inv(σ) ≡ 0;n 为偶数:inv(σ) + r0 ≡ 0 (mod 2)
  2. 估计还差多远每块数字到自己位置的横竖距离之和,是真实步数的下界:它永远不会高估。h(n) = Σ |xi − x̂i| + |yi − ŷi|
  3. 迭代加深搜索只走 f 不超过当前上限的分支,走不通就把上限抬到刚才见过的最小超限值。因为 h 不高估,第一个找到的解就是最短解。f(n) = g(n) + h(n)