God's number = 20

G is a finite group of size 4.3 × 10¹⁹. View it as a graph (vertices = states, edges = single face turns). What is its diameter?

Known as God's number. In 2010, Rokicki's team used 35 CPU-years on a Google cluster to prove this exhaustively: partition the 4.3 × 10¹⁹ states into ~2 billion symmetry classes, optimally solve a representative of each, and verify ≤ 20 every time.

Under the quarter-turn metric (QTM, where U' counts as a separate move) the diameter is 26. The distribution of states by optimal depth (log scale):

11.1 Outline of the proof

Rokicki's proof consumed 35 CPU-years on a Google cluster. The strategy combines symmetry-equivalence reduction with phased solving:

1. Symmetry quotient: the 48 outer cube symmetries (24 rotations × 2 mirrors) reduce 4.3 × 10¹⁹ states to ~9 × 10¹⁷ equivalence classes.
2. Coset partition: further slice by cosets of G_1 (the two-phase solver's stage-1 subgroup, §10), yielding ~2 × 10⁹ "sets" to process (each containing ~2 × 10¹⁰ states).
3. Brute-force solve: for each set, run an improved Kociemba two-phase solver to certify every state's optimal length ≤ 20. If any state required > 20, the bound is broken.
4. Every set verified ≤ 20. Combined with the long-known fact that superflip requires ≥ 20 moves (Reid, 1995), this gives diameter = 20.

11.2 Half-turn vs quarter-turn metric

The same cube has different diameters under different metrics:

Different metrics correspond to different "competition rules" or "physical costs," but the underlying group G is the same. This is a textbook illustration of "graph distance is not an intrinsic group property."

11.3 Historical timeline

From Thistlethwaite's 52 to Rokicki's 20, the upper and lower bounds converged after 29 years to the value 20 — God's number.

11.4 Reid 1995 — superflip needs ≥ 20

The lower-bound proof shows the superflip state (all 12 edges flipped, corners home) strictly requires 20 HTM. Michael Reid (1995) argued via the "EO conservation + independent corner constraint" pair:

1. Superflip needs $\sum e_o=12\equiv 0(\mathrm{mod}2)$, i.e. the total number of "F or B" moves must be even (only F/B change EO; R/L/U/D don't).
2. All corners must return home with CO = 0. R/L/F/B all change CO, so the non-U/D steps must mutually cancel — giving an additional combinatorial constraint.
3. Systematically enumerate every alg of length < 20 over the 18-generator alphabet and verify none produces superflip. Reid combined the parity argument with a corner/edge independence lemma to rule out 19.

11.5 Rokicki 2010 — upper bound = 20 outline

1. Coset enumeration: slice $|G|=4.33\times 10^{19}$ into $[G:G_2]=2.22\times 10^9$ Kociemba cosets, each of size $|G_2|=1.95\times 10^{10}$.
2. Outer symmetry reduction: collapse via the 48-element $O_h$ outer symmetry group from $2.22\times 10^9$ to $\approx 5.6\times 10^7$ equivalence classes (most cosets have trivial stabiliser, so the division by 48 is essentially exact).
3. ≤ 20 HTM verification per coset: for each representative, run a 20-bounded IDA* using both Kociemba phase-1 and phase-2 pruning tables, seeking a ≤ 20-step solve. Any failure would falsify the conjecture (none did).
4. Total compute: ≈ 35 CPU-years, donated by Google. Combined with Reid's 1995 lower bound: diameter(G, HTM) = 20.

11.6 QTM diameter = 26 (2014)

The same recipe, but using QTM (12 generators, all 90°), gave Rokicki & Kociemba's 2014 result: diameter(G, QTM) = 26. Extremal states include "superflip ∘ 4-spot" and "superflip ∘ 6-spot" at exactly 26 QTM. Since $\text{HTM}\le \text{QTM}\le 2\cdot \text{HTM}$, the QTM diameter must sit in [20, 40], measured to be 26.

11.7 Schoenert 1990s — early heroics

Martin Schoenert (1995) used the GAP computational-algebra package to verify |G| and the conjugacy class structure, giving the best-then upper bound of ≤ 29 (based on a known 29-step solve of superflip). This foreshadowed Rokicki's "divide-and-conquer + massive parallel" route. Kunkle & Cooperman (2007) ran a 7 TB distributed IDA* to push the bound to 26, leaving only a "single 6-step gap." Rokicki single-handedly drove it to 22 by 2008, and then the 35 CPU-year leap to 20 in 2010.