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など、より高度なソリューションが必要なキューブが登場している。

人気記事

一覧

イチオシ記事

新着記事

[実力試し]HTML5 認定試験 Lv2 想定問題 (10) 関数の定義方法
[07:30 9/26] 企業IT
松坂屋上野店で秋の行楽グルメフェア--魚屋の"おにぎらず"や浅草今半弁当も
[07:30 9/26] 趣味
東京都内をアートで埋め尽くす! 街がギャラリーになるアートと音楽の祭典
[07:30 9/26] 趣味
ブラッド・ピット、長男と大げんか - アンジーが離婚決断する原因に?
[07:18 9/26] エンタメ
“M字開脚”インリンは今…『深イイ話』で密着取材
[06:00 9/26] エンタメ

本音ランキング