起因

我儿子非常喜欢魔方。他能解 8×8 魔方，连号称世界上最难的魔方也解开过。我也想至少学会三阶魔方，但卡在了解法的第 8 步，原理也一直没怎么弄明白。

于是我决定做一个程序：在画面上直接做出魔方，用照片读取真实的魔方，再一步一步地展示解法。

3D 魔方

  • 用 Qt6 和 OpenGL 绘制。用鼠标拖动时整个魔方旋转；左键点击某一格，那一层就左右转动，右键点击则上下转动。
  • 起初，即使点同一格，有时转得对，有时却转反了。原因是魔方倾斜时，把正面和侧面判断错了。我们用旋转方向模拟器（simulate_moves）测试了所有方向之后才修好。
  • 由于光照和阴影，白色看起来像灰色，底面看起来发黑，所以去掉了光照效果。

两张照片就能得到 54 格

从角的方向拍魔方，一张照片能看到三个面。再从相对的角拍一张，六个面就全部出来了。

  1. 照片 1：黄色朝上放置，拍上、前、右
  2. 照片 2：翻转成白色朝上，拍下、后、左

每个面的中心格无论怎么转都不会移动，所以用中心颜色来确定是哪个面。配色是上黄、下白、前绿、右橙、左红、后蓝。

规则检查

如果照片读错，就会得到一个实际上根本拼不出来的魔方。所以收到展开图后，先检查规则。

  • 中心 6 格必须是规定的颜色。
  • 8 个角块的三个面颜色必须各不相同，相对的颜色（黄与白、绿与蓝、红与橙）不能出现在同一个块上。
  • 12 个棱块也按同样的方式检查，同一个块也不能出现两次。

不符合规则的格子用红色边框标出。点击那一格，周围会环形弹出六种颜色，可以马上修改。

这是读取韩国发售版魔方照片后的初始画面。红色边框就是不符合规则的格子。

求解

通过规则检查后，用 Kociemba 两阶段搜索求解。这不是人背的那种解法，而是利用预先生成的表来寻找短解的算法。用 25 步打乱的 60 个魔方全部解开了，平均 20.7 步，最长的解是 22 步。每次求解耗时的中位数是 6ms。用画面下方的“◀ 上一步 / 下一步 ▶”按钮可以一步一步地查看。

我们也做了一个更接近人类解法的初学者逐层求解器。但同样的 60 个中它只解开了 6 个（10%），解开的也要 203~311 步。所以应用先用 Kociemba，只有失败时才换用其他方法。

时间图表使用的是对数刻度。

这一阶段的实际代码

这是角块检查。三个面的颜色有重复时，三格都会被标出。

src/CubePhotoReconstructor.cppcpp · 25 行
// 2) 코너 (8개): 세 면 색은 모두 달라야 하고, 서로 다른 축 색이어야 함
for (int x : {-1, 1}) {
    for (int y : {-1, 1}) {
        for (int z : {-1, 1}) {
            const int fx = (x == 1) ? 0 : 1;
            const int fy = (y == 1) ? 2 : 3;
            const int fz = (z == 1) ? 4 : 5;
            const int cx = colorOnFace(faces, fx, x, y, z);
            const int cy = colorOnFace(faces, fy, x, y, z);
            const int cz = colorOnFace(faces, fz, x, y, z);
            if (cx < 0 || cy < 0 || cz < 0)
                continue;

            if (cx == cy || cy == cz || cx == cz) {
                v.ok = false;
                v.errors << QStringLiteral(
                                "· %1+%2+%3 모서리: 한 조각에 같은 색이 두 면 — "
                                "전개도에서 이 세 칸이 「왼|앞|오른」 접힘에 맞게 붙어 있는지 확인")
                                .arg(QString::fromUtf8(CubeModel::faceNameKo(fx)),
                                     QString::fromUtf8(CubeModel::faceNameKo(fy)),
                                     QString::fromUtf8(CubeModel::faceNameKo(fz)));
                markCell(v, fx, x, y, z);
                markCell(v, fy, x, y, z);
                markCell(v, fz, x, y, z);
            }

求解时先调用 Kociemba。

src/Oracle.cppcpp · 6 行
// 0) Kociemba two-phase — 임의 스크램블/사진 상태용 확실한 해법
if (!timedOut()) {
    auto koc = KociembaSolver::solve(start, 24, 8);
    if (!koc.empty())
        return compress(koc);
}

下一篇是“2. 用颜色分割代替 VLM，以及性格不同的两个魔方”。