最新の関心ニュース

ルービックキューブの復元は最大２０手

8月 21st, 2010

Wired Visionより

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秒。

昔流行ったゲームです。たった２０手でもとに戻す手順があるとはね。それにしても世界記録保持者はどうやってこの数字をたたき出したんでしょう。たぶん、見た瞬間に答えがわかってしまっているのでしょう。