我写的魔方求解器,30 次随机打乱复原 0 次
先说实话:这个魔方求解器现在是坏的。
node verify.js 30 的结果是「30 次随机打乱、0 次复原」,平均 396 步、433 毫秒一次。不是慢,是根本没做对。
但转动引擎那部分是验证过的,所以坏的地方能圈得很小。这篇记录的是怎么圈的。
先说哪些是好的
cube.js 里 26 个小方块模型、六面转动、逆转动、打乱、局面规范键、迭代加深搜索都写了。转动的正确性有证据:
- 每面转 4 次复原;
f + f'等于复原;f2等于ff - 恒等式成立:
(R U R' U')^6= 复原、(R' D' R D)^6= 复原、(U R U' L' U R' U' L)^3= 复原 - 方向正确性:
U之后「前顶块 → 左顶」、R之后「前右块 → 上右」——这条最要紧,它保证了动画演的跟真实魔方是同一个东西 - 求解过程里没有空转步,不存在「偷偷重置状态」的作弊
恒等式能全部成立,基本说明转动群是对的。那问题就一定在「分阶段策略」里,不在转动里。
怎么把 bug 圈出来
我给求解器加了个 stageStatus,逐阶段判定「到底走到第几步就停了」。然后跑三次失败样本:
| 第几次 | 未达成的阶段 | 停在哪 |
|---|---|---|
| 1 | 1十字, 3中层, 4黄十字, 5顶棱归位, 6顶角归位, 7顶角翻色 | 第 1 步(白色十字) |
| 2 | 4黄十字, … | 第 4 步 |
| 3 | 6顶角归位, 7顶角翻色 | 第 6 步 |
这一步很关键:失败位置是散的,说明不是某一个公式写错了,而是每一阶段各自都有问题。这跟「一个 typo 导致全盘失败」是两种不同的病。
修掉的两个真 bug
bug 1:约束自相矛盾
- 现象:第 1 阶段只走 6 步就放弃
- 根因:要求「插第 4 个十字棱块时不许破坏前 3 个」。但前 3 个就位以后,唯一不碰底层的移动只剩 U 系列,而 U 永远碰不到棱块——可行移动集里根本没有解,搜索必然返回 null,然后循环空转
- 修法:改成两段式。先把 4 个白色棱块全部送上顶层(这时候底面还没开始做,不需要保护),再逐个插入(此时插入 = 转 U 对齐 + 该面 180°,而 180° 只动该面自己的底面槽,天然不破坏别的棱块)
- 结果:第 1 步(白色十字)18 步完成 ✅
这个 bug 有意思的地方在于:它不是我写错了某一行,是我给的约束把解空间掐空了。程序没错,我的要求错了。
bug 2:完成判据太松
- 现象:第 3 阶段宣布「完成」,但后面所有顶层公式全部失败
- 根因:
midOk只检查中层棱块的颜色在不在这格,没检查朝向。棱块「位置对但翻着」也被判为完成 → 前两层其实是假的 → 顶层公式不可能成功 - 修法:同时检查该槽位两个外露面的颜色(
c.f[col] === col) - 结果:判据变可信了,开始诚实报告「没做成」,不再假完成;第 2 步(底层角块)33 步做对 ✅
这个 bug 更阴险:它让程序骗自己。表面看进度在往前走,实际上地基是假的。修完之后失败率反而"变高"了——因为不再假装成功了。
顺带还修了一个:第 2 阶段用 bringToTop 搬角块会把已经做好的十字转坏(第 19 步一个 L 就毁了)。改成「搜一条既不破坏十字、又能把角块送上顶层的路线」。
现在卡在哪
严格判据下,第 3 步(中层棱块)做不成,试了 91 步在空转。已经排除的可能:
- 不是「保护约束」的问题(现在允许临时破坏了)
- 不是「猜错槽位映射」——改成「四个公式挨个试 + 转 U 对齐」,仍然放不进去
所以当前判断是:那四条 8 步的中层插入公式,在我这套引擎里根本不生效——很可能是方向或面序跟我的转动定义对不上。
下次直接做这个
不再整体跑一遍了。把四条中层公式单独拎出来做单元测试:造一个只有中层棱块错位的局面,喂公式,看局面变成什么样。先确认公式本身动的是什么,再谈策略。