ルービックキューブが考案されたのは1974年のこと。それから長い年月を経て「全知全能の神がルービックキューブを解いたら、最大で何手かかるか?」(神のアルゴリズム)の問いに答えが見つかりました。結論からいうと、それは20手。ルービックキューブを渡されて揃えるまでに21手以上かかったら、どこかにミスがあったということになります。(余談ながら、少なくとも20手必要な配置はsuperflipと呼ばれ、1995年に発見されています。今回の発見により最大でも20手、最小でも20手が確定)

答えを見つけたのはケント州立大学 Morley Davidson氏らのグループ。ルービックキューブの全組み合わせ43,252,003,274,489,856,000通りを対象に、意味的に重複するものなどをまとめ、分析する必要のある55,882,296セットに分類、各セットあたり20秒で解法を見つけだすプログラムを作り、しらみつぶしに分析しました。計算にはグループメンバーが所属するGoogleのマシンを利用。どれほどの性能のマシンが提供されたのかは不明とのことですが、たとえば4コア・2.8GHzのIntel Nehalemを使ったとしたら11億秒 / 35年くらいかかるとのこと。Googleが35年分の計算をやってくれたというわけで、なによりその力技が印象的です。すべての答えは42でも、Googleの答えは20。覚えておきましょう。

ルービックキューブの全パターンを分析、最大20手と解明
広告

0 コメント

広告