ルービックキューブは20手で解ける

30年くらい前に流行ったルービックキューブですが、どんな配置であっても最大20手で解けることが最近証明されました。

難しいことは「God's Number is 20」のページでも読んでもらうとして、ここでは簡単に彼らが何をやったのかを紹介します。

まず、ルービックキューブが取り得る状態の数ですが、43,252,003,274,489,856,000 通りになるそうです。すごい数ですね。いくら最近のコンピュータが速いからといって、これを全部処理するわけにはいきません。そこで、対称性とかを考えて色々と処理するわけですが、結果として、この中の55,882,296通りを解けば解が得られることが分かります。

ただ、プログラムを作ったところ、1通りの状態について答えを得るまでに20秒ほどかかるとのこと。これは、5千万通りをまともに計算したら35年くらいかかる計算量です。これでは普通に計算することは出来ません。

そこで登場するのがgoogleです。googleにはたくさんコンピュータがありますので、それらを使って並列に問題を解いてやればいいわけです。詳しい情報は非公開ですが、2,3週間でこれらの問題をすべて解いたそうです。

その結果、一番多くの手数がかかる問題でも最大20手で解けることが判明しました。で、最低でも20手必要な問題というのは既に知られていますので、挟み撃ちで解が決定されたということです。

実はこの問題、1981年ころから研究されていて、年々解に近づいていたのですが、googleのコンピュータパワーを使うことでついに解決されたということになります。四色問題などもそうですが、こういったコンピュータによる力技を使った問題解決にはロマンがありますね。これからもソフト・ハードともに進化していくでしょうから、もっと難しい問題が次々と解かれていくのでしょう。楽しみです。