折腾记录 · 3 分钟

我写的魔方求解器,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,逐阶段判定「到底走到第几步就停了」。然后跑三次失败样本:

第几次未达成的阶段停在哪
11十字, 3中层, 4黄十字, 5顶棱归位, 6顶角归位, 7顶角翻色第 1 步(白色十字)
24黄十字, …第 4 步
36顶角归位, 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 步的中层插入公式,在我这套引擎里根本不生效——很可能是方向或面序跟我的转动定义对不上。

下次直接做这个

不再整体跑一遍了。把四条中层公式单独拎出来做单元测试:造一个只有中层棱块错位的局面,喂公式,看局面变成什么样。先确认公式本身动的是什么,再谈策略。