26手以内でルービックキューブは揃う!! 米研究者が証明

 

米ノースイースタン大学のコンピュータ科学部のGene Cooperman教授と大学院生のDan Kunkle氏が、3×3×3のルービックキューブをどのような状態からでも26手以内で揃えられることを証明した。これまでは27手以内が証明されている最少のソリューションだった。

3×3×3のルービックキューブ

「ルービックキューブは、SearchとEnumerationの問題に結びつく研究題材である」とCooperman氏。ルービックキューブのソリューションを導きだす過程は、AIからオペレーションに至るまで、様々な分野において異なったメソッドを比較検討する機会になるという。両氏は、大規模なテーブルを展開するために、7テラバイトの分散ディスクをRAMの拡張として利用。その上でルービックキューブのすべてのコンフィギュレーションをセット化し、1つの動きが全てのセットに与える結果を調べた。そのデータを基に、1秒あたり100,000,000回のシミュレーションが可能なコンピュータを用いて、26手以内のソリューションにたどり着いた。

ルービックキューブのソリューションについては1997年にカリフォルニア大学ロサンゼルス校のRichard Korf教授が、最少で18手以内、多くとも20手以内で解けると発表した。ところが実証できずに、長い間27手以内が最少のソリューションと見られていた。従来の研究についてKunkle氏は、「Korf氏はルービックキューブの1つ状態から最適なソリューションを導き出すプログラムづくりに時間をかけていた」と指摘。「われわれのプログラムは先に大規模な予測計算を行い、その結果ルービックキューブをどのような状態からでも26手以内に揃えられるソリューションを、およそ1秒程度のスピードで見つけ出せる」という。

ルービックキューブは6色に色分けされた立方体のパズルで、一面が3×3に分割されている。キューブを回して色をバラバラにし、それを再び揃えるというシンプルなパズルだが、4300京通り以上の状態が考えられるという奥深さがマニアを作り出している。現在では基本の3×3×3以外にも、4×4×4や5×5×5など、より高度なソリューションが必要なキューブが登場している。

人気記事

一覧

イチオシ記事

新着記事

日テレ改編、プライム新バラエティは『1周回って』のみ - 全日改編率3.9%
[14:39 9/1] エンタメ
i☆Risの芹澤優と茜屋日海夏がDAM★ともコラボ番組に登場
[14:36 9/1] ホビー
2016年第2四半期、iPhone出荷台数が前年同期比28.8%増 - IDC
[14:35 9/1] 企業IT
女性の自己投資、何に使ってる?
[14:35 9/1] マネー
パナソニック、転送レートTyp.50Mbpsの産業機器向けフォトカプラを製品化
[14:31 9/1] テクノロジー

本音ランキング