ルービックキューブは20手以内で必ず解ける、数学者チームが特定

2010年08月17日 14:41　発信地:ワシントンD.C./米国

クリッピングする

写真をブログに利用する

メディア・報道関係・法人の方写真購入のお問合せはこちら

ドイツ中部ハノーバー（Hanover）で開かれた世界最大の情報技術見本市「CeBIT」会場で展示された「ルービックタッチキューブ（Rubik's Touch Cube）」。タッチスクリーンでできており、自動解法装置も内蔵されている（2009年3月4日撮影）。(c)AFP/JOHN MACDOUGALL

関連写真1/1ページ全1枚

【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