ルービックキューブ、どんな状態であっても、20手以内

ルービックキューブが考案されたのは1974年のこと。
それから長い年月を経て「全知全能の神がルービックキューブを解いたら、
最大で何手かかるか？」（神のアルゴリズム）の問いに答えが見つかりました。
ルービックキューブの最大手については、1981年から諸説が発表されているようですが、
今回の研究で確定ということだそうです。
ルービックキューブのブームが再燃している中、大きなニュースが飛び込んできました。

どんな状態であっても、20手以内であることを解明。
それが、神の数20
God's Number is 20.

解明されたこと自体には、意義がありますが、
任意の状態から、完成させるための、
その手を考えるのは至難の業。

ところで、ルービックキューブの状態（組み合わせ）は、何通りあるのでしょうか。
4325京2003兆2744億8985万6000通りあります。
その求め方は、
例えば、ルービックキューブ - Wikipedia で説明されています。

4325京2003兆2744億8985万6000通りについて、
コンピュータを駆使して、力づくで計算したのでしょうか？

それをやると、どんなに優秀なコンピュータでも、人が生きているうちに答えを出せません。

そこで、神の数を割り出すため、数学教師、Google社のエンジニア，
プログラマーからなる研究チームは、
ルービックキューブを解くという大きな問題を、
22億1709万3120個の小さな下位の問題に分けたのです。
（下位の問題はそれぞれ195億842万8800通りのパターンを含んでいます）
つまり、
22億1709万3120×195億842万8800 ＝ 4325京2003兆2744億8985万6000
ということです。

ということで、
22億1709万3120ケースについて、
コンピュータを駆使して、力づくで計算したということです。

研究チームはGoogle社の協力により実現しました。
(同社は提供したコンピューター・リソースについて、具体的には明らかにしていない)。
計算時間は、わずか数週間であった。

WIRED

ルービックキューブ「神の数字」を証明　2010-08.17火


3Dパズル『ルービックキューブ』の4325京2003兆2744億8985万6000通りの配置はすべて、そろった状態への復元に、多くても20手しか必要としない。つまり、回転操作でどれだけゴチャゴチャにしようと、ルービックキューブは20手以内で解くことが可能だという。米Google社から提供されたコンピュータ使用時間を利用して、複雑な計算を実行した研究チームがそう証明した。

最も効率的な手順でルービックキューブを解く場合にかかる最小の手数は「神の数字(God's Number)」と呼ばれる。1981年には上限として52手が必要だと考えられた。その後2008年8月までに、上限の数は22にまで小さくなっていた。

神の数字を割り出すため、数学教師、Google社のエンジニア、プログラマーからなる研究チームは、ルービックキューブを解くという大きな問題を、22億1709万3120個の小さな下位の問題に分けた。下位の問題はそれぞれ195億842万8800通りのパターンを含んでいた。

こうしてできた下位の問題は、現代のパソコンのメモリに入るほどの小ささだった。しかし計算を実行するとなると、米Intel社の『Nehalemマイクロ・アーキテクチャー』による2.8GHz4コアチップを採用したデスクトップ・コンピューターで、11億秒(約35年)かかる。そこで研究チームはGoogle社の協力を借りることにしたわけだ(同社は提供したコンピューター・リソースについて、具体的には明らかにしていない)。

ルービックキューブは1974年にハンガリーの建築学者兼彫刻家Erno Rubik教授が発明したパズルで、世界的に人気がある。2009年1月の段階で、世界全体で少なくとも3億5000万個が販売されていた。世界大会も行なわれており、公式の世界最短記録は2008年の7.08秒。

[ルービックキューブの全ての配置、「4325京2003兆2744億8985万6000通り」の計算根拠はこちら。「最短解法を教えてくれるiPhoneアプリ」を紹介する過去記事などについては、関連記事セクション参照]

[日本語版：ガリレオ-緒方 亮]
WIRED NEWS 原文(English)

　
AFPBB NEWS

ルービックキューブは20手以内で必ず解ける、数学者チームが特定
2010-08.17火 14:41　発信地:ワシントンD.C./米国

【8月17日 AFP】米グーグル（Google）の支援を受けた国際研究チームが、人気立方体パズル「ルービックキューブ（Rubik's Cube）」の全パターンを調べ上げ、どんな状態からでも20手以内で全面の色をそろえることができることを突き止めた。

　これを突き止めたのは、米オハイオ（Ohio）州立ケント大学（Kent State University）のMorley Davidson氏、グーグルのエンジニア、John Dethridge氏、ドイツの数学教師のHerbert Kociemba氏、米カリフォルニア（California）州のプログラマーのTomas Rokicki氏らを含む数学者チーム。

　数学者チームによると、「（ルービック）キューブを解く人は手順をまとめたアルゴリズムを使う。さまざまな種類のアルゴリズムがあり、複雑性の度合いや必要な手数などが異なっているが、人間が記憶できるアルゴリズムは、最小手でも40手以上を必要とする」のだという。

「しかし神であればもっと効率的なアルゴリズム、常に最短の手数で済むアルゴリズムを用いるだろうと人びとは考える。これは『ゴッドアルゴリズム（神のアルゴリズム、God's Algorithm）』と呼ばれている。また、このアルゴリズムで解くために最大で必要な手数は『ゴッドナンバー（神の数、God's Number）』と呼ばれている。そしてついに、ゴッドナンバーは20であることを突き止めた」（数学者チーム）

　研究チームは、グーグルが提供した同社内のコンピューターの空き時間を用いて、膨大なキューブの状態のそれぞれの解法をすべて突き止めた。それにかかった時間は「わずか数週間」だった。グーグルは研究に提供したコンピューターの詳しい仕様などは明らかにしていない。(c)AFP

　
[ツカミルのコメント]
計算時間は、わずか数週間ということですが、
（数週間を２週間と仮定）

ルービックキューブを解くという大きな問題を、
22億1709万3120個の小さな下位の問題に分けたのが、
大きなポイントです。

それをやらなければ、
4325京2003兆2744億8985万6000通りについて、
コンピュータを駆使して、力づくで計算したら、
８億年程度の時間を要するということです。

やはり、工夫することは大事なことですね。