拾い物 ルービックキューブと数学

【数学】ルービックキューブは25手で完成可能、米研究者が新解法の証明に成功

1 ：トリニダート小鳩φ ★：2008/03/29(土) 11:39:58 ID:???
ルービックキューブは「どんな状態(No position)」にあったとしても必ず25手で完成させることが可能ということが米研究者の論文により24日、明らかとなった。

これまでの研究では「どんな状態」の場合のルービックキューブの完成には2007年に米ノースイースタン大学のジーン・コッパーマン博士らが発表した26手が最短の解法だった。
今回、明らかとなった解法は従来発表されていた最短の解法を1手、短縮することに成功した
ことになる。

この「数学的証明」に成功したのは米スタンフォード大学で数学の研究助手を務めるトマス・ロキッキ（Tomas Rokicki）さん。

ロキッキさんはルービックキューブの動きを個別な「手」としてではなく「動きの組み合わせ」と考えることで、200億通り存在するルービックキューブの空間遷移の状態を20億通りまでに集約。その上で、その20億通りの組み合わせをインテルのCore2 Quad Q6600（1.6GHz）のパソコンを使って1500時間をかけて解析を行うことで、ルービックキューブはどんな状態にあったとしても必ず25手で完成させることが可能という新解法を見つけることに成功した。

Technobahn 　2008/03/27
http://www.technobahn.com/news/2008/200803271347.html
◆画像　ルービックキューブ
http://upload.wikimedia.org/wikipedia/commons/1/10/Rubiks_cube.jpg

Twenty-Five Moves Suffice for Rubik's Cube
http://arxiv.org/abs/0803.3435