AI 工具 · 01
华容道求解器
摆出任意局面,AI 给出最短解法
支持 3×3 八数码和 4×4 十五数码。先用逆序数判断有没有解,再用 IDA* 搜索找最少步数;个别特别难的 4×4 局面超出搜索预算时,会改用加权搜索给出一个较短的解,并明确标注。全部在你的浏览器里计算,不上传任何数据。
f(n) = g(n) + h(n)h = 0 · inv(σ) = 0 · 可解性 –
- 步数
- 0
- 搜索节点
- 0
- 耗时
- 0
- 进度
- 0
解法(数字 = 要移动的方块,箭头 = 移动方向)
原理
它是怎么算的
- 先判断有没有解所有摆法里恰好一半无解。数一数逆序数(前面的数比后面大的对数)的奇偶就能判断,不用搜索。n 为奇数:inv(σ) ≡ 0;n 为偶数:inv(σ) + r0 ≡ 0 (mod 2)
- 估计还差多远每块数字到自己位置的横竖距离之和,是真实步数的下界:它永远不会高估。h(n) = Σ |xi − x̂i| + |yi − ŷi|
- 迭代加深搜索只走 f 不超过当前上限的分支,走不通就把上限抬到刚才见过的最小超限值。因为 h 不高估,第一个找到的解就是最短解。f(n) = g(n) + h(n)