ルービックキューブを解く（その２：God's Numberへ）

ルービックキューブを手順に沿って解くのではなく、コンピュータの力技で解く。
最速で解く。

これは美しい。


3×3のどんなパターンであろうと、解くことができる最小の手順の数をGod's Number（ゴッドナンバー、神の数字）と呼ぶらしい。
Morley Davidsonらが2010年に20手であることをつきとめた。
果てしない木構造（6面のそれぞれ、右回転、左回転、それぞれ2回転の18通り）の探索は天文学的パターン数となる。
戻す回転を排除したとしても18×15×15×・・・（約4300京）のパターンを計算して揃っているかどうかを判別していかなければならない。

でも、そんな計算を超高速計算機を使って研究したところ、上記のように20手であることを証明したらしい。

ということで、「God's Number is 20」 も実装しちゃおう。
 God's Numberを証明した時のプログラム（cube20）が公開されているので実装する。

• God's Number is 20（http://cube20.org/ ）

ソースをダウンロードし、makeすると何やらmutexでエラーが出る。

$ make
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o twophase twophase.cpp phase1prune.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp -lpthread
./twophase.w:215:21: error: reference to 'mutex' is ambiguous

pthread_mutex_lock(&mutex);
./twophase.w:204:17: note: candidate found by name lookup is 'mutex'
pthread_mutex_t mutex;

mutexをmutex1に修正して再度make

$ make
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o twophase twophase.cpp phase1prune.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp -lpthread
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o hcoset hcoset.cpp phase1prune.cpp kocsymm.cpp cubepos.cpp -lpthread
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o cubepos_test cubepos_test.cpp cubepos.cpp
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o kocsymm_test kocsymm_test.cpp kocsymm.cpp cubepos.cpp
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o phase2prune_test phase2prune_test.cpp phase2prune.cpp kocsymm.cpp cubepos.cpp
c++ -DHALF -O4 -Wall -DLEVELCOUNTS -o phase1prune_test phase1prune_test.cpp phase1prune.cpp kocsymm.cpp cubepos.cpp

という感じでtwophaseソルバが出来上がる。
twophaseは、標準入力に完全になるべき各キューブの現在地を設定することで手順を計算してくれる。

コマンドは、

$ twophase [options] < input-sequences > solutions

input-sequencesにそれぞれのピースの位置と向きを与える。
完全形であれば、[1 2 3 4 5 ・・・20] = [UF UR UB UL DF ・・・DFL]となる。



【2020.2.12 追記】上の図の18番と20番は逆でした。（図の修正はしてません）

下の図と上の図（揃った状態）を比較する。
上の図の5番のピースは前面右（上の図の9の位置、色セットはFR）にある。
F側はオレンジ、R側は白となっているので、完全形の場合（上の図の5の位置、色セットはDF、D側はオレンジ、F側は白）と並びが同じで場所だけが異なるので、input-sequencesの5項目（上の図の5のピース（オレンジ・白）の位置）はFRとなる。
仮に、下の図の5のピースがFが白、Rがオレンジになっている場合は、input-sequencesの5項目は、RFとなる。

といった具合に20個のピースの位置と色のセットの状態をinput-sequencesにセットし、twophaseを実行する。

$ echo "RB DL FL BU FR FD LB LU UF BD DR UR DRF DBR ULF DLB FLD RBU BLU UFR" | ./twophase -s 20

引数の-s 20は最大手順を20というオプション。
初めてtwophaseを実行すると、データベースを作成するので、数分掛かるが、2回目以降は数秒で終了する。（我が家のサーバーは遅いので10秒ぐらいかかる）
以下が実行結果。

This is twophase 1.1, (C) 2010-2012 Tomas Rokicki. All Rights Reserved.
Solution 1 len 20 probes 21027
L3U2R3F2R2U2R2U2F3U1B1F2U1L1B2U3L2B1R3B2
Verified integrity of phase one pruning data: -1939391245
Verified integrity of phase two pruning data: 1084146253
Solved 1 sequences in 13.6223 seconds with 21027 probes.
Completed in 13.6225

なんと！20手で解決！
手順は、

L3U2R3F2R2U2R2U2F3U1B1F2U1L1B2U3L2B1R3B2

となった。
左面を右回りに3回転（＝左回りに1回転）、上面を2回転・・・と。

twophaseを前回のルービックキューブ画像から解決するプログラムに埋め込んで実装して手順を表示する。

ということで、God' Number（神の数字）の20手で解けた。
恐るべし。

人間が初期状態からこの手順を行うことは不可能。
去年の夏頃からルービックキューブのプログラムと格闘してきて、最後は神の数字に行き着いてしまった。

次は、最終目標のRaspberry Piでサーボモータ動かしてギュルギュルってやってみるかな。

定石も何もなく、コンピュータに言われたまま回す、ただそれだけ。ただそれだけ。

ただ、それで良いのか。
う〜ん。
徒然なるままに今日も明日も。