〇△□スレ立て依頼所〇△□

【GK歓喜】ルービックキューブの最短解法が25から23に縮む

【Technobahn 2008/6/6 15:24】ルービックキューブは「どんな状態（No position）」にあったとしても必ず23手で完成させる
ことが可能ということが米ソニー・ピクチャー・イメージワークスの社員が発表した論文により5日、明らかとなった。
（中略）

　今回、改めて従来まで最短だった解法を更に2手も短縮することに成功した米ソニー子会社社員というのは、前回、25手の
解法を発表した同じロキッキさん。
　ロキッキさんの解析手法は、ルービックキューブの動きを個別な「手」としてではなく「動きの組み合わせ」と考えることで、
200億通り存在するルービックキューブの空間遷移の状態を20億通りまでに集約。しかし、ここまでは前回とまったく同じ。

　前回はスタンフォード大学の助手という立場だったため、利用できる資源が限られたため、20億通りまでに集約したルービッ
クキューブの空間遷移状態をインテルのQ6600プロセッサーを搭載したパソコンを使って枝木の絞込みを行いながら部分的
解析を実施することで25手という最短の解法を見つけたが、今回は、更に、解析過程を完全にするために、彼の新しい職場と
なるソニー・ピクチャー・イメージワークスでCG制作用に使われているスーパーコンピューターの計算資源を利用することを
上司から承諾を受けた上で、夜間にスーパーコンピューターが使われていない時間帯にルービックキューブの空間遷移状
態探索のためのプログラムを稼動。その結果、これまでパソコンを使った部分的探索ではわからなかったより効率的な解法
を見つけることに成功した。

　計算結果からロキッキさんによるとルービックキューブは「どんな状態」にあったとしても最短では21手、悪くても23手では
必ずマス目をそろえることが可能だということが判ったとしている。

（中略）

　ルービックキューブの解法を巡っては、著名な数学者のダグラス・ホフスタッター（Douglas Hofstadter）が1996年に出版した
数学の入門書で20手以内で完成可能という理論上の枠組みを示しており、今回、発表された成果がそのまま、最短の解法と
はならなそうだ。

http://www.technobahn.com/cgi-bin/news/read2?f=200806061524&page=2