ルービック・キューブの 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 の推移です。アプレットですから、オートもしくはマウスクリックによりマニュアルで動かすことが出来ますが、環境により動かなかったらゴメンなさいです。いずれにせよ、単なるゲームでありながら、それ相応に奥が深いもんだということがよく分かります。

date	upper bound	lower bound	gap	contributor(s)
Jul. 1981	18	52	34	Morwen Thistlethwaite
Apr. 1992	18	42	24	Hans Kloosterman
May 1992	18	39	21	Michael Reid
May 1992	18	37	19	Dik Winter
Jan. 1995	18	29	11	Michael Reid
Jan. 1995	20	29	9	Michael Reid
Dec. 2005	20	28	8	Silviu Radu
Apr. 2006	20	27	7	Silviu Radu
May 2007	20	26	6	Dan Kunkle, et al.
Mar. 2008	20	25	5	Tomas Rokicki
Apr. 2008	20	23	3	Tomas Rokicki, et al.
Aug. 2008	20	22	2	Tomas Rokicki, et al.
Jul. 2010	20	20	0	Morley Davidson, et al.