ルービックキューブ描画アルゴリズムについて

最近考えていることをメモしておこうと思います．

## はじめに
趣味の一貫でルービックキューブのタイマーアプリを作成しています．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/d25e6567-eb7b-3421-b7e5-ddb37bc7cd54.png)

有名なcsTimerというタイマーの画面参考例です．
真ん中に直前のタイム，上にスクランブル(こう混ぜましょうという指示)，右下にスクランブル通りに混ぜた場合のルービックキューブの図という内容が一般的なタイマーアプリの機能として搭載されています．この記事ではこのスクランブル後の描画について書いていきたいと思います．

タイマーアプリは意外と多いのですが，この図を描画するアルゴリズムはなかなかネットを探しても見つかりませんでした．そこでどうやったら描画できるか考えようと思った次第です．

## スクランブルの回転記号について
先ほどルービックキューブにはスクランブルという，こう混ぜましょうという回転記号が存在すると書きました．これは手崩しではなくランダムな混ぜ方をすることで公平性を保っているわけです．手崩しだと十分に混ざっておらず，揃えやすい崩れ方になることもあり得ます．スピードキューバ―はこのスクランブルを毎日数100回というレベルで崩しては揃えてとしていくわけですが，二度と同じスクランブルに当たることはありません．そのため毎回スクランブル後に図を確認して正しくスクランブルできているかを見る必要があります．

では，回転記号について簡単に説明します．
詳しくは以下のサイトを参照してください．

https://tribox.com/3x3x3/solution/notation/

主に回転記号は6個です．
上面(U)，下面(D)，右面(R)，左面(L)，前面(F)，背面(B)です．もしスクランブルにRと書いてあると右面を90°上に回しましょうという世界基準の回転になります．またR'のようにダッシュが付いていると下に90°，R2のように2が付いていると倍の180°回すといった具合です．他にもRwで二層回しなどがあります．

## スクランブル後のパーツの移動とそのアルゴリズムについて
例えばスクランブル通りにRを回したとするとこのような動きになります．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/94758e7b-b027-1900-05ba-bc0e572d395a.png)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/bb053781-3ae9-b409-964a-454c71ea700d.png)

これをコードを書いて処理するにはどうすればいいかなと考えました．案として配列を用いた処理は思いつきました．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/d4dec241-258a-442b-91e2-91b2c1b9fbf8.png)

まず展開図を上のように用意します．1白,2オレンジ,3緑,4赤,5青,6黄色に当てはめます．
そしてこの展開図を配列に落とし込みます．
左上から順に
1,1,1
1,1,1
1,1,1
を以下のように当てはめます．
array1[0][0],array1[0][1],array1[0][2]
array1[1][0],array1[1][1],array1[1][2]
array1[2][0],array1[2][1],array1[2][2]
同様にarray2~array6まで当てはめます．

ここでスクランブルRを回したとき，それぞれの数字の移動先がこうなります．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/ab5604dd-ca9e-9cd7-1023-74f4d57f0a1e.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/0e0fa45e-7882-ec91-b05e-0cead51b91e8.png)

つまり，array1[0][2]にarray3[0][2]の値を代入する．その他の配列も同様に1つずつ処理すればokと考えました．ただしarrayの値をそのまま書き換えて処理するとループ終了直前の値が参照できなくなるので，あらかじめコピー配列に保存するという処理にしました．簡単なソースコードは以下の通りです．

```cpp
#include <iostream>

void printArrayRow(int array[3][3], int row) {
    // 指定された行の内容を表示
    for (int j = 0; j < 3; j++) {
        std::cout << array[row][j] << " ";
    }
}



int main() {
    // 1から6までの数字で埋めた6つの配列を定義
    int array1[3][3] = { {1, 1, 1}, {1, 1, 1}, {1, 1, 1} };
    int array2[3][3] = { {2, 2, 2}, {2, 2, 2}, {2, 2, 2} };
    int array3[3][3] = { {3, 3, 3}, {3, 3, 3}, {3, 3, 3} };
    int array4[3][3] = { {4, 4, 4}, {4, 4, 4}, {4, 4, 4} };
    int array5[3][3] = { {5, 5, 5}, {5, 5, 5}, {5, 5, 5} };
    int array6[3][3] = { {6, 6, 6}, {6, 6, 6}, {6, 6, 6} };

    int arraycopy1[3][3] = { {1, 1, 1}, {1, 1, 1}, {1, 1, 1} };
    int arraycopy2[3][3] = { {2, 2, 2}, {2, 2, 2}, {2, 2, 2} };
    int arraycopy3[3][3] = { {3, 3, 3}, {3, 3, 3}, {3, 3, 3} };
    int arraycopy4[3][3] = { {4, 4, 4}, {4, 4, 4}, {4, 4, 4} };
    int arraycopy5[3][3] = { {5, 5, 5}, {5, 5, 5}, {5, 5, 5} };
    int arraycopy6[3][3] = { {6, 6, 6}, {6, 6, 6}, {6, 6, 6} };

    // 配列1（上部）を表示
    std::cout << "        "; // 左のスペースを追加
    for (int i = 0; i < 3; i++) {
        printArrayRow(array1, i);
        std::cout << std::endl;
        if (i != 2) std::cout << "        "; // 次の行の左のスペースを揃える
    }
    std::cout << "\n";

    // 配列2, 3, 4, 5（中央）を表示
    for (int i = 0; i < 3; i++) {
        printArrayRow(array2, i);
        std::cout << "  "; // 配列間のスペース
        printArrayRow(array3, i);
        std::cout << "  "; // 配列間のスペース
        printArrayRow(array4, i);
        std::cout << "  "; // 配列間のスペース
        printArrayRow(array5, i);
        std::cout << std::endl;
    }
    std::cout << "\n";

    // 配列6（下部）を表示
    std::cout << "        "; // 左のスペースを追加
    for (int i = 0; i < 3; i++) {
        printArrayRow(array6, i);
        std::cout << std::endl;
        if (i != 2) std::cout << "        "; // 次の行の左のスペースを揃える
    }

    std::cout << "\n";
    //turnR
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            arraycopy1[i][j] = array1[i][j];
        }
    }
    //F→U
    array1[0][2] = arraycopy3[0][2];
    array1[1][2] = arraycopy3[1][2];
    array1[2][2] = arraycopy3[2][2];
    //D→F
    array3[0][2] = arraycopy6[0][2];
    array3[1][2] = arraycopy6[1][2];
    array3[2][2] = arraycopy6[2][2];
    //B→D
    array6[0][2] = arraycopy5[2][0];
    array6[1][2] = arraycopy5[1][0];
    array6[2][2] = arraycopy5[0][0];
    //U→B
    array5[2][0] = arraycopy1[0][2];
    array5[1][0] = arraycopy1[1][2];
    array5[0][0] = arraycopy1[2][2];
    //R→R
    array4[0][0] = arraycopy4[2][0];
    array4[1][0] = arraycopy4[2][1];
    array4[2][0] = arraycopy4[2][2];
    array4[0][1] = arraycopy4[1][0];
    array4[2][1] = arraycopy4[1][2];
    array4[0][2] = arraycopy4[0][0];
    array4[1][2] = arraycopy4[0][1];
    array4[2][2] = arraycopy4[0][2];

        // 配列1（上部）を表示
        std::cout << "        "; // 左のスペースを追加
    for (int i = 0; i < 3; i++) {
        printArrayRow(array1, i);
        std::cout << std::endl;
        if (i != 2) std::cout << "        "; // 次の行の左のスペースを揃える
    }
    std::cout << "\n";

    // 配列2, 3, 4, 5（中央）を表示
    for (int i = 0; i < 3; i++) {
        printArrayRow(array2, i);
        std::cout << "  "; // 配列間のスペース
        printArrayRow(array3, i);
        std::cout << "  "; // 配列間のスペース
        printArrayRow(array4, i);
        std::cout << "  "; // 配列間のスペース
        printArrayRow(array5, i);
        std::cout << std::endl;
    }
    std::cout << "\n";

    // 配列6（下部）を表示
    std::cout << "        "; // 左のスペースを追加
    for (int i = 0; i < 3; i++) {
        printArrayRow(array6, i);
        std::cout << std::endl;
        if (i != 2) std::cout << "        "; // 次の行の左のスペースを揃える
    }

    return 0;
}

```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/89e427a1-d245-86f2-b431-a1c15ca44757.png)

## 改善策
実際のスクランブルでは「U B2 U B2 R F2 B L U' L2 F D2 B' L2 F2 B' L2 U2 F2」程度の長さのスクランブルになります．ソースコードではRだけ書いてみましたが，R2やR'用に別のコードを追加するのは至って面倒だしバグのリスクや保守面でも好ましくないです．そこでR2はR Rと2回実行，R'はR R Rと3回実行(R'は-90°回転なので90°×3=270°と同じこと)すれば実質同じ処理をしていることになります．なのでU,D,R,L,F,Bの6つだけ実装すればあとはコード内で何とかすることができます．これでまずコードをシンプルにできそうです．

次に全てのパーツを配列化するのが望ましいのかについてです．これはルービックキューブの構造を考える必要があります．![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3888054/3e68d47b-474f-57af-dfa0-e0098adf3e5e.png)
そもそもルービックキューブは上のように大きく3つのパーツに分類できます．
センターは各面の真ん中のパーツで，中にはxyz軸のような回転軸が備わっています．軸であるためセンターパーツの色の位置関係が変わることは絶対ありません．白の反対は黄色，青の反対は緑，赤の反対はオレンジとなります．
次にコーナーについてです．コーナーは文字通り角で合計8個あります．
最後にエッジです．各コーナーの間にあり，合計12個あります．なんか高校化学の面心立方格子とか体心立方格子とかをイメージしてもらえればいいかと思います．

ではこれを踏まえて改めて考えると，先のコードでは9個×6面で54個の値を保持し，コピー配列の方も含めると倍の108個の値を操作し続けることになります．そしてその値代入をスクランブルの文字数分なので30回近く繰り返すことになります．別にそれくらいなら平気そうな気もしますが，なんかスクランブルが出た0.5秒後くらいにしかスクランブル画像が表示されずユーザー満足度が下がりそうな予感．少なくとも自分が使うのであればイライラするはずです．

まずセンターは固定である以上配列に入れる必要はない気がします．なので54-6=48個まで減らせます．
次にコーナーです．コーナーとエッジどちらにも言えることですが，同じパーツは1つもありません．上の図であれば青，黄色のコーナーパーツでも残り一色は赤とオレンジになります．青と黄色とその位置関係，具体的には手前青，上黄色，の時点であとは形が分かれば右か左のどちらに残り一色が来るか分かるのでそれでも情報量は減らせるかなと思います．
エッジは1パーツに対して二色持っています．なので青と赤，青と黄色，青とオレンジが分かって入れば残り1個の青のペアは必ず白です．つまりこの白は情報を持たせなくても勝手に分かるという形になります．青の対面色は緑なので緑についても3個のペアが分かって入れば残り1つも分かります．

エッジ12個，コーナー8個，合計20個のパーツからなるので持たせる情報も頑張って20くらいまで減らせないのかなと考えています．普通にキューブタイマーアプリ作ったことある人はどうやってキューブを描画してるんだろうという感じです．少し調べてもそんなAPIなんて出てこないんですよね