ルービックキューブの神の数字、解かれる

ルービックキューブを、あらゆる状態から最小手で解くには、一体何手必要か。この最小手を得るアルゴリズムを、「神のアルゴリズム」といい、このアルゴリズムが弾きだす最大の手数を、「神の数字」と呼ぶ。神の数字はいくつかであるかということは、これまで研究者を魅了させてきた。

ルービックキューブの多くの状態は、神のアルゴリズムを使えば、15手から18手で解ける。このことから、明確な証明はないものの、神の数字は18手以上であるといわれてきた。しかし、20手未満ではどうしても解けぬ状態が発見されたので、18手であるとする説は否定された。では何手か。これまでも、25手以下であるとか、23手以下である、いや22手まで削減できた、などという証明がされてきたが、このたび、神の数字を弾きだすことに成功した。

証明は、コンピューターを使ってすべての組み合わせを検証するという総当り的な手法で行われた。組み合わせの数は、「絶望的に多かった」ため、低減する努力が試みられた。重複やほとんど似た状態を省き、約二千万にまで組み合わせを削減することに成功した。

ひとつの組み合わせを検証するのに、高性能なPCで20秒から30秒ほどかかる。研究者たちは、スーパーコンピューターを借りて計算させようと考えた。ところが、ここに意外な者からの協力が得られた。Googleである。Googleが計算をしようと申し出たのであった。

「我々は、未だGoogleがどのような電算機を用いて計算を成し遂げたのかを知らず」と研究者は語る。

計算はなされた。もっとも、この二千万の組み合わせからは漏れた例外的な組み合わせが、まだいくつか残っていたので、それはもっと遅い、通常のデスクトップ機で計算しなければならなかったが、ともかく、計算はなされた。神の数字は、20手であった。

「なんだか、原点に戻ってきたんだという感じがします」と研究者は言う。「ルービックキューブは80年代を象徴する存在であり、私が数学という学問の道に入った理由でした」と。

しかし、ルービックキューブへの研究は、これもって終わるものではない。今回解いたのは、3x3x3のルービックキューブである。研究チームは、これから4x4x4のルービックキューブへの研究に着手するという。

参考文献：
God's Number is 20
God's algorithm - Wikipedia, the free encyclopedia
BBC News - Rubik's Cube quest for speedy solution comes to an end