ルービックキューブの神の数

並びを数えるには、まず部品を見る。動く部品は、3色の角が8個と、2色の辺が12個。面の中心6個は互いの位置を変えないので、中心を目印にすれば、数えるのは角と辺の置き方だけになる。8と12と6は立方体の頂点と辺と面の数で、オイラーの多面体定理の$8-12+6=2$がそのまま成り立つ。

キューブを分解して組み直すなら、どの置き方も作れる。では、回すだけで作れるのは、そのうちのどれだけか。

1. 角8個の並べ方は$8!$通りで、1個ごとに向きが3通りある

   $$8!\cdot 3^8$$

2. 辺12個の並べ方は$12!$通りで、1個ごとに向きが2通りある

   $$12!\cdot 2^{12}$$

3. 組み直して作れる置き方は、2つを掛けた数になる

   $$8!\cdot 3^8\cdot 12!\cdot 2^{12}\approx 5.2\times 10^{20}$$

4. 角$i$の向き（ねじれ）$x_i$を0, 1, 2で記録する。面を90°回すと、4つの角に$+1,+2,+1,+2$が加わるか、どれも変わらない。和の変化は6か0で、3で割った余りは保たれる

   $$\sum _{i=1}^8{x}_i\equiv 0(\mathrm{mod}3)$$

5. 辺$j$の向き$y_j$を0, 1で記録する。面を回して裏返る辺は0個か4個なので、和の偶奇は保たれる

   $$\sum _{j=1}^{12}{y}_j\equiv 0(\mathrm{mod}2)$$

6. 90°回しは、角4個と辺4個をそれぞれ1つの輪で入れ替える。長さ4の輪は互換3回に分かれる奇置換なので、角を並べ替える置換$\sigma$と、辺を並べ替える置換$\tau$は、偶奇がいつも一緒に入れ替わる

   $$\mathrm{sgn}\sigma =\mathrm{sgn}\tau$$

7. 角は7個の向きを決めれば残る1個も決まり、辺も11個の向きを決めれば残る1個が決まる。置換の組は、偶奇がそろった半分だけが残る

   $$|G|=\frac{8!\cdot 3^7\cdot 12!\cdot 2^{11}}{2}$$

8. 数値を入れる

   $$|G|=43,252,003,274,489,856,000$$

「1手回す」を押すと、線が太くなった角と辺が入れ替わったりねじれたりするが、2つの和の余りと偶奇の組は崩れない。180°回しは90°回しを2回重ねたものなので、どの1手でも同じである。「分解して角をねじる」を押すと、ねじれの和を3で割った余りが0でなくなり、その並びは回すだけでは揃わなくなる。

逆に、3つの条件を満たす置き方は、どれも回すだけで作れる。ほかを崩さずに辺を3個だけ入れ替える$L{R}^{-1}{U}^2{L}^{-1}R{B}^2$のような手順を組み合わせると、角と辺を1個ずつ正しい位置と向きに送れるからだ。ジャネット・チェンのノートは、高校生向けの夏の数学キャンプで群論を教えたときのもので、この逆の証明を最後まで追っている。

組み直した置き方のうち、回して作れるのは12個に1個。分解して適当にはめ直したキューブは、12分の11の確率で、回すだけでは二度と揃わない。

上限のほうは、数えるだけでは済まない。$4.3\times 10^{19}$通りのすべてについて、20手以内の手順を実際に見つける必要がある。

ロキッキらの見積もりでは、性能のよいパソコンで並びを1個ずつ解くと、最短の解なら1秒に0.36個、20手以内の解を探すだけでも1秒に3,900個だった。後者の速さでも、全部を解くには約3.5億年かかる。そこで4人は、並びを同じ大きさの箱に分けた。

1. 上下の面は自由に、ほかの4面は180°だけ回してできる並びを集める

   $$H=⟨U,D,R^2,L^2,F^2,B^2⟩$$

2. $H$の中では角と辺の向きが変わらず、中段の辺4個は中段から出ない。角8個、上下の段にある辺8個、中段にある辺4個が、それぞれの中で並び、偶奇の条件で半分になる

   $$|H|=\frac{8!\cdot 8!\cdot 4!}{2}=19,508,428,800$$

3. 並び全体を$H$の剰余類に分ける。箱の数は、角と辺の向きと、どの辺4個が中段に来るかで決まる

   $$\frac{|G|}{|H|}=3^7\cdot 2^{11}\cdot \left(\genfrac{}{}{0ex}{}{12}{4}\right)=2,217,093,120$$

4. 立方体の向きを変えたり鏡に映したりしても、揃えるのに要る手数は変わらない。向きの24通りと鏡を合わせた48通りの対称性を使い、さらに大きな集合被覆の問題を解いて、解く箱を減らす

   $$2,217,093,120\to 55,882,296$$

5. 1つの箱を約20秒で解く

   $$55,882,296\times 20\mathrm{s}\approx 1.1\times 10^9\mathrm{s}$$

約11億秒は、CPUの時間にして約35年分にあたる。この計算をGoogleの多数の計算機に配り、数週間で終えた。

箱1つは、当時のパソコンのメモリーに収まる大きさだった。箱ごとにまとめて解くと、20手以内の解が1秒に10億個のペースで見つかる。1個ずつ解くときの約26万倍である。最短の解を求めなかったのは、スーパーフリップが20手を要すると分かっていたからで、すべての並びに20手以内の解があれば、それで足りる。

こうして、上からも下からも20になった。

手の数え方を変えると、答えも変わる。ここまでのように180°回しも1手と数える数え方を、ハーフターン・メトリック（HTM）と呼ぶ。90°回しだけを1手とし、180°回しを2手と数えるクォーターターン・メトリック（QTM）では、2014年8月、ロキッキとデイヴィッドソンが同じ箱分けを使って、神の数が26であることを示した。計算はオハイオ・スーパーコンピューター・センターで、CPUの時間にして約29年分。この数え方では1手ごとに置換の偶奇が入れ替わるので、並びを見ただけで、最短の手数が偶数か奇数かが分かる。26手かかる並びは、スーパーフリップに「フォースポット」と呼ぶ並びを重ねた1つと、その向きを変えた2つしか見つかっていない。