« 大阪タイガースのユニフォームで乱打戦を制して首位固め! | トップページ | 横浜相手に快勝! »

2010年8月18日 (水)

ルービック・キューブの God's Number は20に確定!

ルービック・キューブのファンは日本でも数多くいて、実は、我が家のおにいちゃんも大好きだったりするんですが、この6面完成までの最少プレー数が20であることが証明されました。なお、ルービック・キューブを完成させる最少プレー数のことを英語で "God's Number" といいます。まず、これを報じた記事を BBC のサイトから最初の5パラだけ引用すると以下の通りです。Entertainment ではなく、Technology のカテゴリで取り扱われています。

Rubik's Cube quest for speedy solution comes to an end
A 30-year quest to find the fewest number of moves needed to solve any one of the billions of configurations for a Rubik's Cube may have ended.
Any scrambled puzzle can be solved in 20 moves or fewer, researchers claim.
The international team used a bank of computers at Google to help crank through the solutions.
The figure is known as "God's number" because an all-knowing entity would know the optimal number of steps needed to solve the puzzle.
"We now know for certain that the magic number is 20," Professor Morley Davidson, a mathematician from Kent State University, told BBC News.
Super solution for Rubik's cube Teenager grasps top Rubik's title The results suggest that there are more than 100 million starting positions - of a possible 43 billion billion - that can be solved in exactly 20 moves.

引用した記事にある通り、ルービック・キューブの初期状態、すなわち、ランダムに色が並んでいる状態は 43 billion billion 通り、より正しく表せば、43,252,003,274,489,856,000 通りあるんですが、そこから、最小20手で全6面が完成するということです。20手必要なのは約3億通りです。18手必要とするのが約 29 billion billion 通りで最も多くなっています。これらの出典はすべて God's Number is 20.というサイトです。私が計算できるハズもありません。
以下も同じ God's Number is 20. のサイトからの引用で、ルービック・キューブのアプレットとこの約30年間における God's Number の推移です。アプレットですから、オートもしくはマウスクリックによりマニュアルで動かすことが出来ますが、環境により動かなかったらゴメンなさいです。いずれにせよ、単なるゲームでありながら、それ相応に奥が深いもんだということがよく分かります。

dateupper
bound
lower
bound
gapcontributor(s)
Jul. 1981185234Morwen Thistlethwaite
Apr. 1992184224Hans Kloosterman
May 1992183921Michael Reid
May 1992183719Dik Winter
Jan. 1995182911Michael Reid
Jan. 199520299Michael Reid
Dec. 200520288Silviu Radu
Apr. 200620277Silviu Radu
May 200720266Dan Kunkle, et al.
Mar. 200820255Tomas Rokicki
Apr. 200820233Tomas Rokicki, et al.
Aug. 200820222Tomas Rokicki, et al.
Jul. 201020200Morley Davidson, et al.

|

« 大阪タイガースのユニフォームで乱打戦を制して首位固め! | トップページ | 横浜相手に快勝! »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/207184/36231018

この記事へのトラックバック一覧です: ルービック・キューブの God's Number は20に確定!:

« 大阪タイガースのユニフォームで乱打戦を制して首位固め! | トップページ | 横浜相手に快勝! »