始まり

息子はキューブが大好きです。8×8 のキューブも解き、世界で一番難しいと言われるキューブも解きました。私も 3×3 くらいは覚えようとしましたが、解法の8段階目でつまずき、原理もよく理解できませんでした。

そこで、キューブを画面に自分で作り、実物のキューブを写真で読み取って、一手ずつ解き方を見せるプログラムを作ることにしました。

3Dキューブ

  • Qt6 と OpenGL で描きます。マウスでドラッグするとキューブ全体が回り、マスを左クリックするとその列が左右に、右クリックすると上下に回ります。
  • 最初は同じマスを押しても、正しく回るときと逆に回るときがありました。キューブが斜めのとき、前面と側面を誤って判断していたのです。回転方向のシミュレーター(simulate_moves)ですべての方向をテストしてから直しました。
  • 照明と影のせいで白が灰色に、下の面が黒く見えたので、照明効果を外しました。

写真2枚で54マス

キューブを角の側から撮ると、1枚に面が三つ写ります。反対側の角からもう1枚撮れば、六つの面がすべて揃います。

  1. 写真1: 黄色を上にして、上・前・右
  2. 写真2: 白を上にひっくり返して、下・後ろ・左

面の中央のマスは回しても動きません。そこで中央の色でどの面かを決めます。配色は、上が黄、下が白、前が緑、右がオレンジ、左が赤、後ろが青です。

ルールの検査

写真を読み間違えると、実際には組み立てられないキューブができてしまいます。そこで展開図を受け取ったら、まずルールを確認します。

  • 中央の6マスは決まった色でなければなりません。
  • 角のピース8個は三つの面の色がすべて異なる必要があり、向かい合う色(黄・白、緑・青、赤・オレンジ)が一つのピースに一緒に来ることはありません。
  • 辺のピース12個も同じ方法で確認し、同じピースが2回出てもいけません。

引っかかったマスは赤い枠で示します。そのマスを押すと周りに六色が丸く浮かび、すぐに直せます。

韓国発売品のキューブの写真を読み取った初期画面です。赤い枠がルールに引っかかったマスです。

解き方

ルールを通過したら、Kociemba の2段階探索で解を求めます。人が覚える解法ではなく、あらかじめ作った表を使って短い解を見つけるアルゴリズムです。25手でシャッフルしたキューブ60個をすべて解き、平均20.7手、最長の解は22手でした。1回解くのにかかった時間は中央値で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 の代わりに色の分解で、性格の違う二つのキューブ」です。