はじめに
3×3×3のルービックキューブはどんな状態からも最長20動作でもとに戻せるそうです。20手くらいならコンピュータで求められないか？そう考えたのが今回の動機です。
テーマ
今回のテーマは「ルービックキューブの最短解を求める」ことです。結論
ルービックキューブを解くPythonプログラムをすでに公開してくれている人がいました。qiita.com
qiita.com
qiita.com
前編、中編、後編と3つに分かれた大作です。非常にわかりやすく書かれています。
「大体1秒位 & 20手強くらいで解く」と解説されています。
今回は「時間にはこだわらず最短解を求める」のを目標としました。
プログラムのほとんどは上記で公開されているものを少し変更しただけです。最短解を求める命題に対して「Two-Phase-Algorithm」をどのように使用していいかわからないためそのアルゴリズムの部分は実装しませんでした。
当たり前ですが探索はすすまず、現状は13手の問題を解くのに1時間かかっています。
20手の問題は到底解けそうにありません。
# Start searching length 1 # Start searching length 2 # Start searching length 3 # Start searching length 4 # Start searching length 5 # Start searching length 6 # Start searching length 7 # Start searching length 8 # Start searching length 9 # Start searching length 10 # Start searching length 11 # Start searching length 12 # Start searching length 13 Finished! (4044.01 sec.) Solution: L2 D F2 L2 D U L2 F2 B R F- U R
これから
速度を上げるために何が必要か？これからいろいろトライしてみようと思います。それなりの結果になったときにPythonスクリプトを公開します。
