ルービックキューブを解く（その２：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でサーボモータ動かしてギュルギュルってやってみるかな。

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

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

ルービックキューブを解く（その１：画像認識して解く）

ルービックキューブの写真を撮って、色を認識して解く。
そんなことが出来ればと思い、格闘。

一面づつ写真を撮ってというやりかたは、面白くないので、3面づつまとめて。

最初はPHPでがりがり書いたが、画像認識に限界があり、C++とOpenCVの組み合わせに乗り替え。

まずは、写真の撮り方。画像処理をやりやすくするために、背景は100均で買ったフェルト生地を置いて撮影。
ルービックキューブの配置は、以下の面の位置で。
最終的には各面に番号を付け、行列（配列）に色を代入する。

左の写真 左手前の面：Front面（中央が白）→0 上の面：Up面（中央が赤）→1 右手前の面：Right面（中央が緑）→5

右の写真 左手前の面：Back面（中央が青）→2 上の面：Down（中央がオレンジ）→3 右手前の面：Left面（中央が黄）→4

写真をアップロードして、C++のプログラムで色の認識を行う。

【手順】

1. 白黒画像に変換
   void cvCvtColor(const CvArr* src, CvArr* dst, int code)
2. 確率的ハフ変換による線分の検出
   CvSeq* cvHoughLines2(CvArr* image, void* storage, int method, double rho, double theta, int threshold, double param1=0, double param2=0)
3. 3点透視図として扱い消失点を求める
4. 面に変換するためのホモグラフィ行列の推定
   void cvFindHomography(const CvMat* srcPoints, const CvMat* dstPoints, CvMat* H int method=0, double ransacReprojThreshold=3, CvMat* status=NULL)
5. ホモグラフィ変換で各面（正方形）の画像を生成
   void cvWarpPerspective(const CvArr* src, CvArr* dst, const CvMat* mapMatrix, int flags=CV_INTER_LINEAR+CV_WARP_FILL_OUTLIERS, CvScalar fillval=cvScalarAll(0))
6. 重み付け最小二乗法（Biweight推定法）で各キューブを推定
7. HSV色空間に変換し、色相（H:Hue）を昇順ソート、彩度（S:Saturation、白）は降順ソートし、それぞれの色を推定
8. 6x9の行列（面[6] × キューブ数[9]）に色を設定

という感じで処理する。

各キューブの色行列ができたところで、3点透視図で再現。

1. アフィン変換行列を算出
   CvMat* cvGetPerspectiveTransform(const CvPoint2D32f* src, const CvPoint2D32f* dst, CvMat* mapMatrix)
   
   
2. 各ポイントをアフィン変換し、画像を生成

とりあえず、画像認識で色を判別し、配列に代入。
さて、ルービックキューブを解きましょう。

まずは、回転の軸の設定

というような感じで各面を正面から見た時に、右回転を1に、左回転を-1に設定。
ルービックキューブ攻略サイトなどを参考にしながら、ステップごとにプログラミング。
メガハウスの６面完成攻略書を参考に。

【手順】

1. クロスを作って上面（Up）を揃える（最小の手数で揃えられる面を選ぶ）
2. 中段を揃える
3. 裏（Down）のクロスを作る
4. 裏（Down）を揃える
5. コーナー、サブキューブを揃える

脳ミソがよじれる感じで計算し、回転方向を図示。
以下、抜粋。

 

クロスを作る。クロスの面は裏（Back）面なのでこの図では見えません。

以下が最終局面。 

で完成。
でも、120手が必要。う〜ん。