fc2ブログ

2010年08月18日 (水) 20:27:00

ルービック・キューブの 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.
Entry No.2168  |  普通の日記  |  コメント(0)  |  トラックバック(0)  |  to page top ↑

コメント

コメントを投稿する

URL
コメント
パスワード  編集・削除するのに必要
非公開  管理者だけにコメントを表示
 

トラックバック

この記事のトラックバックURL



この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック

 | BLOG TOP |