Mathematics: combinatorial group theory

God's Number — across every WCA puzzle

God's number is the maximum, over all states, of the minimum moves to solve. Formally it is the diameter of the Cayley graph of the puzzle group $G$ with generator set $S$ . Below, every WCA puzzle is listed with its exact diameter or current bounds.

D (G, S) = g \in G max w \in S^{*} w \cdot e = g min ∣ w ∣

G

= puzzle group,

S

= legal generating moves,

∣ w ∣

= word length (under the chosen metric)

3×3 HTM diameter (exact)

Rokicki et al. 2010

3×3 QTM diameter (exact)

Rokicki & Davidson 2014

35 CPU·yr

Google compute spent on the proof

55.88M cosets ·

4.3 \times 1 0^{19}

states

Θ (N^{2} / lo g N)

N \times N

God's number asymptotic (Demaine 2011)

arXiv:1106.5736

Reading roadmap

The page has 13 sections, each readable in isolation. Below: a 'first-time' linear path and a 'by interest' jump-table.

First read (~15 min)

Primer — understand the four words: group / generators / Cayley graph / diameter
Metrics — see why HTM ≠ QTM ≠ STM
17-puzzle grid — scan: which are proven, which are bounded
Superflip — see what the "hardest" state actually looks like
Rokicki proof animator — 7 frames: what those 35 CPU-years actually computed

Jump by interest

Math Compression chain → Subgroup chain → IDA*
Algorithm IDA* tree → Two-phase demo → 8 algorithm cards
Hands-on Two-phase demo → 2×2 BFS → IDA* slider
History Proof animator → Timeline → References
Data Distance distribution → 17-puzzle grid → Growth chart
Open Open problems → 4×4 / Megaminx gap

💡 Tip: hover any formula for KaTeX source; blue "interactive" cards reward clicking.

Two-minute group-theory primer

1. A cube is a group

Every legal state is a permutation: 8 corners (pos + orientation) and 12 edges (pos + orientation) reshuffled. Multiplication = compose two operations. Identity = solved state. Inverse = invert the sequence. All 3×3 states form a group $G$ with $∣ G ∣ = 4.3 \times 1 0^{19}$ .

2. Generators = "what you can turn"

The six 90° face turns ${U, D, L, R, F, B}$ plus their inverses / doubles form generator set $S$ . Every state is a finite product of elements of $S$ — that's " $G$ is generated by $S$ ".

3. The Cayley graph

Make a vertex for each state; draw an edge between two states differing by one generator. This is the Cayley graph $Γ (G, S)$ . "Solving" = finding a path from your state to the identity.

4. Diameter = God's number

The maximum, over all pairs of vertices, of the shortest-path length: that's the diameter $D (G, S)$ . In other words, worst-case minimum-move count. That's God's number.

5. Lagrange ⇒ coset decomposition

Any subgroup $H \subset G$ partitions $G$ into $∣ G ∣/∣ H ∣$ disjoint cosets. Kociemba's $H = ⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ ( $∣ H ∣ \approx 1.95 \times 1 0^{10}$ ) splits $4.3 \times 1 0^{19}$ states into 2,217,093,120 cosets — solve each once, 10 orders of magnitude saved.

6. Symmetry group $S_{48}$ ⇒ further squeeze

The cube itself has 48 symmetries (24 rotations × 2 mirror). Two states equivalent under symmetry share a diameter. Quotienting the 2.2B cosets by $S_{48}$ leaves ~55.88M — the feasibility threshold that made the 2010 proof possible.

Phase algorithms — interactive: Kociemba vs Thistlethwaite

Two main flavours of coset decomposition. Thistlethwaite (1981) splits solving into 4 phases, each freezing one symmetry. Kociemba (1992) simplifies to 2. Below: the subgroup chains side by side, each layer showing $∣ G_{i} ∣$ + coset count to next + phase worst-case moves.

…

The 2010 proof's compression chain — interactive: 4.3×10¹⁹ down to ~80 super-cosets

The 2010 proof isn't "scan every state". It folds $4.3 \times 1 0^{19}$ states through 4 mathematical layers: Lagrange cosets → cube-symmetry quotient → set-cover compression → per-super-coset IDA* verification. Each layer pulls in a different tool; together they make 35 CPU-years feasible.

…

Two-phase solver — interactive: split a solve into Phase 1 + Phase 2

Pick a scramble and watch how Kociemba's algorithm first pushes the state into the subgroup $H = ⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ , then solves inside $H$ . The "4 invariant bars" drain to zero exactly when Phase 1 ends — that's the geometric meaning of "entering H".

…

The metric decides the number — interactive: HTM / QTM / STM

God's number is always "graph diameter", but what edges exist depends on what counts as "one move". The three metrics below are the ones you'll see in the literature — click to switch, the example re-counts itself.

…

God's number for every WCA event

Click any card to expand details (algorithm, prover, references). "Proven" cards have exact values; "Bounds" cards show the best known gap, waiting to be closed.

3×3×3

∣ G ∣ = 4.3252 \times 1 0^{19}

· ~43 quintillion

Proven

20HTM

Partition all 4.3×10¹⁹ states into 2,217,093,120 cosets, then shrink to 55.88M via symmetry + set cover. ~35 CPU-years on Google in July 2010 nailed the HTM diameter at exactly 20. The QTM=26 (2014) and STM=18 results followed using the same coset framework.

The cube that gave us "God's number = 20"

The 3×3 group has 4.3252 × 10¹⁹ states (exactly 43,252,003,274,489,856,000). Naïve BFS is impossible — even storing one distance per state would take exabytes. Tomas Rokicki's 2010 victory came from three weapons: coset decomposition, symmetry compression, set cover.

The key subgroup is H = $⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ — Kociemba's 1992 "P1" or "G1" group. |H| = 19,508,428,800, so |G|/|H| = 2,217,093,120 cosets. Each coset is a set of states reachable from each other inside H; you only need one optimal solution per coset. That reduces a 4.3×10¹⁹-vertex graph to a 2.2-billion-vertex one.

Then apply the 48-element cube symmetry group $S_{48}$ to crush cosets to 55.88M. Then a greedy set-cover absorbs neighbouring cosets into ~80 super-cosets that are actually solved. Google's cluster spent ~35 CPU-years; on 2010-07-13 they announced: every 3×3 state is solvable in $\leq 20$ HTM, and some (e.g. superflip) actually need 20. Upper = lower = 20. QED.

The QTM result of 26 (2014, Rokicki & Davidson) and STM result of 18 (2014, Rokicki) used the same coset framework. The 3×3 is the cleanest victory in God's-number history: not just the exact value, but also a geometric description of all 12 antipodes at distance 20.

Other metrics

QTM26
STM18

Proved / estimated by:Rokicki · Kociemba · Davidson · Dethridge · 2010

2×2×2

∣ G ∣ = 3.67 \times 1 0^{6}

· ~3.67 million

Proven

11HTM

Tiny state graph — your laptop can BFS the whole thing in seconds. Fixing one corner as anchor, the diameter is exactly 11 HTM and 14 QTM. The live BFS demo on this page reproduces it in your browser.

Small enough to BFS overnight

The 2×2 group has only 3.67M states because it has 8 corners and no edges or centres. Fixing one corner (DBL) to kill global rotation leaves 7 movable corners × 6 orientation DoF = 7! × $3^{6}$ = 3,674,160. A 1981-era PC could BFS the whole Cayley graph in reasonable time.

In HTM the distance distribution peaks around 8-10 moves; only 2,644 states require the full 11. Those 2,644 antipodes can be enumerated — they are literally every "hardest" 2×2 state. In QTM the diameter rises to 14.

Fun fact: the average optimal solution length over all 2×2 states is ≈ 8.76 HTM. One BFS pass gives you this number for free.

Other metrics

QTM14

Proved / estimated by:community BFS · 1981

Jaap Scherphuis — 2×2 page

4×4×4

∣ G ∣ = 7.40 \times 1 0^{45}

· ~7.4 × 10⁴⁵

Bounds

35–57OBTM

5×5×5

∣ G ∣ = 2.83 \times 1 0^{74}

· ~2.83 × 10⁷⁴

Bounds

52–130OBTM

6×6×6

∣ G ∣ = 1.57 \times 1 0^{116}

Bounds

75–200OBTM

7×7×7

∣ G ∣ = 1.95 \times 1 0^{160}

Bounds

99–280OBTM

3×3 Blindfolded

∣ G ∣ = 4.3252 \times 1 0^{19}

Proven

20HTM

3×3 Fewest Moves

∣ G ∣ = 4.3252 \times 1 0^{19}

Proven

20HTM

3×3 One-Handed

∣ G ∣ = 4.3252 \times 1 0^{19}

Proven

20HTM

Clock

∣ G ∣ = 2.05 \times 1 0^{16}

· ~2.05 × 10¹⁶ (incl. pin state)

Proven

12move

Megaminx

∣ G ∣ = 1.01 \times 1 0^{68}

· 20! · 3¹⁹ · 30! · 2²⁷

Bounds

48–194HTM

Pyraminx

∣ G ∣ = 9.33 \times 1 0^{5}

· ignoring 4 trivial tips

Proven

11HTM

Skewb

∣ G ∣ = 3.15 \times 1 0^{6}

Proven

11HTM

Square-1

∣ G ∣ = 5.53 \times 1 0^{11}

· 170 · 2 · 8! · 8!

Proven

13twist

4×4 Blindfolded

∣ G ∣ = 7.40 \times 1 0^{45}

Bounds

35–57OBTM

5×5 Blindfolded

∣ G ∣ = 2.83 \times 1 0^{74}

Bounds

52–130OBTM

Multi-Blind

∣ G ∣ = (4.3 \times 1 0^{19})^{k}

Trivial

20 \cdot k

HTM

Proven exact Bounds only Trivial / parametric

3×3 minimum-solution distribution — interactive: the FMC ceiling

Plot "how many 3×3 states are at distance $d$ (HTM)" and you get the distribution every FMC solver implicitly faces. Rokicki has published exact counts for $d = 0, \dots, 15$ ; $d = 16, \dots, 20$ are estimates constrained by the total sum $4.3 \times 1 0^{19}$ .

…

Superflip — the "hardest" 3×3 state

In 1995 Michael Reid proved superflip needs exactly 20 HTM, pushing the 3×3 lower bound to 20; in 2010 Rokicki's team proved the upper bound is also 20, closing the gap. Below: the 3-D superflip state, two optimal solutions, and a few other distance-20 antipode representatives.

…

N×N growth — interactive: state space vs diameter

Left axis grows double-exponentially ( $\sim 1 0^{N^{2}}$ ); right axis grows polynomially with a log shave. Their ratio is the "difficulty density". Hover an $N$ for exact values.

…

2×2 live BFS — re-prove "diameter = 11" yourself

The 2×2 group has only 3.67M states — a laptop BFSes the whole graph in seconds without symmetry / cosets / GPU. The button below spawns a worker that runs full BFS over the 9 HTM generators (U U2 U' R R2 R' F F2 F') and streams the distance distribution to the chart.

…

How are these numbers actually computed?

Eight real-world techniques, ordered by group size — from "BFS the lot" to "symmetry-quotient your way to feasibility".

BFS

Tiny groups (

\leq 1 0^{8}

): plain BFS over the whole graph, 1 byte/state for distance, full distribution + diameter in seconds-to-minutes. The "2×2 live BFS" above is exactly this. Pyraminx, Skewb, Sq-1 (twist) too.

Bidirectional BFS

BFS from both ends, meet in the middle ⇒ search space drops from

b^{d}

2 \cdot b^{d /2}

. Used for Sq-1 twist; the same trick powers many general IDA* solvers.

IDA* + Pattern Database

Mid-sized groups (

1 0^{9} - 1 0^{12}

): precompute the shortest-solution table for a subset of cubies (e.g. all corners) — a few hundred MB — and use it as an admissible heuristic

h (s) \leq d^{*} (s)

for the full problem. Iterative Deepening A* + this

h

crushes plain BFS. Kociemba's P1/P2 tables are the canonical example.

Coset partition + set cover

Huge groups (

1 0^{19} +

): split

G

into

∣ G ∣/∣ H ∣

cosets of a subgroup

H

, solve each independently. 3×3 uses

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

∣ G ∣/∣ H ∣ = 2.2 \times 1 0^{9}

. Then a greedy set-cover packs neighbouring cosets into ~80 super-cosets and you actually solve only those.

Symmetry / antisymmetry reduction

The cube has 48 symmetries (24 rotations × 2 mirrors) plus antisymmetry (inverses are equivalent), 96 total. Equivalent states share their optimal solution length ⇒ solve once, propagate. The 3×3's 2.2B cosets shrink to 55.88M under symmetry — that 40× squeeze is the 2010 proof's enabler.

Disk-based BFS

When

∣ G ∣

outgrows RAM, batch-write each frontier layer to SSD; cross-layer dedup via external sort + uniq. Sq-1 face-turn (Shuang Chen 2017) used 722 GB — 2 bits/state to fit

1.2 \times 1 0^{13}

twistable states.

Canonical-sequence counting (lower bound)

Don't solve, just count: legal canonical sequences at depth

d

are

\leq N \cdot M^{d - 1}

(after rejecting same-axis-as-previous). Megaminx uses a commuting-faces recurrence

t (n + 1) = 36 t (n) - 240 t (n - 1) - 320 t (n - 2)

; set

t (d) \geq ∣ G ∣

⇒ lower bound on

d

. Megaminx 48, 4×4 35 came from here.

Asymptotic construction (Demaine)

Demaine et al. 2011: partition

N \times N

cubies into

O (N^{2} / lo g N)

commuting classes; solve each in

O (lo g N)

parallel moves. Match with the canonical-sequence

Ω (N^{2} / lo g N)

lower bound ⇒

Θ (N^{2} / lo g N)

, rigorous. Constants are big; only asymptotic.

IDA* + Pattern Database — interactive: how heuristics prune

A teaching-scale search tree. Switch the "heuristic h(s)" or drag the f-limit and watch subtrees collapse. Green leaf = a distance-8 solution (tree depth cap). Higher prune-rate ⇒ tighter heuristic ⇒ faster search.

…

IDA* + Pattern Database pseudocode

function solve(start):
  for depth = 0, 1, 2, ..., 20:
    if dfs(start, depth, 0) is not None: return solution
  return None  // unreachable for 3×3 (we know depth ≤ 20)

function dfs(state, max_depth, g):
  h = pattern_db.lookup(state)        // admissible: h ≤ true distance
  if g + h > max_depth: return None
  if state == identity:  return []    // solved
  for move in legal_moves(state):
    if same_axis_as_previous(move): continue
    sub = dfs(apply(state, move), max_depth, g + 1)
    if sub is not None: return [move] + sub
  return None

One IDA* call solves one state (milliseconds). Run it on all ~55.88M super-cosets with the assertion $\leq 20$ holds — and the diameter is nailed at 20.

Open problems

Four/five puzzles have no exact diameter to date. For each unfinished gap: why it's hard, what would close it, rough effort estimate.

…

Two milestone proofs — interactive frame-by-frame

The two key "God's number = 20" proofs split into frames: Reid 1995 (lower bound 20, SGI Indigo 90 hours) + Rokicki 2008→2010 (upper bound 20, Google 35 CPU-years). One sentence + one SVG + one formula per frame.

…

Timeline

1974
Ernő Rubik invents the Magic Cube in Budapest as a teaching aid for 3-D structure, spatial reasoning, and combinatorics.
1979
Cube hits commercial shelves; Western mathematicians immediately recognise it as a finite group of order $4.3 \times 1 0^{19}$ .
1981
David Singmaster publishes Notes on Rubik's Magic Cube — the first systematic notation (URFDLB) and group-theoretic terminology underpinning everything since.
1981
2×2 / Pyraminx / Skewb BFS feasible on early PCs ⇒ each diameter is 11 (a coincidence across three different groups).
1982
Morwen Thistlethwaite publishes the 4-phase algorithm: $G_{0} \to G_{1} \to G_{2} \to G_{3} \to {e}$ , each phase from a precomputed table, capping 3×3 at $\leq 52$ HTM.
1990
Hans Kloosterman tightens the upper bound to 42; several authors that year reach 40-37.
1992
Herbert Kociemba publishes the 2-phase algorithm with $H = ⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ (his "P1" / " $G_{1}$ "): 2.2 billion cosets, each $\leq 30$ HTM, total $\leq 30$ .
1995
Michael Reid uses computer-assisted enumeration to prove superflip needs $\geq 20$ ⇒ 3×3 lower bound = 20; also proves Kociemba's bound $\leq 22$ . The 20/22 gap stands for 15 years.
2005
Mike Masonjones BFS-proves Square-1 twist-metric diameter = 13.
2006
Silviu Radu pushes 3×3 upper bound to 27; Rokicki joins in 2007 and gets it to 26.
2008
Tomas Rokicki uses Sun's 8-GB cluster to drop the upper bound to 22 — finally reaching Reid's 1995 target, but the gap is not closed.
2010
Rokicki · Kociemba · Davidson · Dethridge spend 35 CPU-years on Google: symmetry compresses 2.2B cosets to 55.88M, set-cover absorbs neighbours into ~80 super-cosets, each actually solved. No counterexample. 2010-07-13: 3×3 HTM diameter = 20.
2011
Erik Demaine et al. (arXiv:1106.5736 "Algorithms for Solving Rubik's Cubes") prove $N \times N$ God's number is $Θ (N^{2} / lo g N)$ via parallel sub-algorithms + cubie commuting-class partitioning. The rigorous $N \times N$ asymptotic.
2012
Herbert Kociemba proves Megaminx lower bound = 48 HTM via commuting-faces counting.
2014
Rokicki & Davidson prove 3×3 QTM diameter = 26 with the same coset framework; Jakob Kogler proves Rubik's Clock diameter = 12 via front-cross cosets; Rokicki separately proves 3×3 STM diameter = 18. Three new exact diameters in one year.
2017
Shuang Chen (WCA 2008CHEN27) uses 722 GB disk BFS + 3816 symmetry cosets to prove Square-1 face-turn diameter = 31. The first cubing-domain disk-BFS at this scale.
2018
Sebastiano Tronto and Vincent Sheu publish the 4×4 OBTM lower bound $\geq 35$ on SpeedSolving.
2020
Graham Siggins sets the MBLD world record 62/65. MBLD is group-theoretically trivial (diameter $20 \cdot k$ ); the record is a memory + endurance limit.
2022
Yusheng Du sets 3×3 WR at 4.86s (later tied / surpassed by Yiheng Wang), avg solution ~40 HTM, far above the 20 theoretical optimum.
2024
Merino & Subercaseaux (arXiv:2501.00144) propose a "Demigod's number" — 500k random samples + Hoeffding prove $D \leq 36$ in 5 hours, error probability $< 1 0^{- 10}$ . Dedicated page.
2025
cube20.org publishes Rubik's Clock full distance distribution as an independent re-verification of Kogler's 2014 proof, 11 years on.

FAQ + glossary

Ten common questions ("why this nickname?", "are WCA scrambles near it?", "can CFOP reach 20?", "how much compute is 35 CPU-years today?"…) plus a group-theory / algorithm glossary.

…

References

cube20.org — Rokicki team's hub: 3×3 / Clock proof data + full distance distributions
cube20.org / QTM — 3×3 QTM diameter = 26 proof data (2014)
cube20.org / Clock — Rubik's Clock diameter = 12 and full distribution (2025-03-04)
Rokicki et al., SIAM J. Discrete Math 2014 — Peer-reviewed paper "The Diameter of the Rubik's Cube Group Is Twenty"
Demaine et al. 2011 — arXiv:1106.5736 — "Algorithms for Solving Rubik's Cubes", rigorous $Θ (N^{2} / lo g N)$ for N×N
Herbert Kociemba — Two-phase algorithm — Algorithm description + implementation guide by the author
Kociemba — Megaminx lower bound — Megaminx 48 lower bound via commuting-faces counting
Jaap Scherphuis\' puzzle pages — state counts + BFS data for 2×2, Skewb, Pyraminx, Square-1, Clock
Shuang Chen — Sq-1 face-turn = 31 — 722 GB disk-BFS write-up (2017-12)
Jakob Kogler — Clock = 12 — Original 2014-05 proof thread
Speedsolving — Megaminx bound — Megaminx HTM/QTM bound discussion thread
Merino & Subercaseaux 2024 — arXiv:2501.00144 — "Demigod's number" — 36 HTM probabilistic oracle
Tom Davis — Group Theory via Rubik\'s Cube — MIT primer treating the cube as a group-theory textbook
Wikipedia — God\'s algorithm — Encyclopedic article on God's number / God's algorithm

Mathematics: combinatorial group theory

God's Number — across every WCA puzzle

D (G, S) = g \in G max w \in S^{*} w \cdot e = g min ∣ w ∣

G

= puzzle group,

S

= legal generating moves,

∣ w ∣

= word length (under the chosen metric)

3×3 HTM diameter (exact)

Rokicki et al. 2010

3×3 QTM diameter (exact)

Rokicki & Davidson 2014

35 CPU·yr

Google compute spent on the proof

55.88M cosets ·

4.3 \times 1 0^{19}

states

Θ (N^{2} / lo g N)

N \times N

God's number asymptotic (Demaine 2011)

arXiv:1106.5736

Reading roadmap

The page has 13 sections, each readable in isolation. Below: a 'first-time' linear path and a 'by interest' jump-table.

First read (~15 min)

Primer — understand the four words: group / generators / Cayley graph / diameter
Metrics — see why HTM ≠ QTM ≠ STM
17-puzzle grid — scan: which are proven, which are bounded
Superflip — see what the "hardest" state actually looks like
Rokicki proof animator — 7 frames: what those 35 CPU-years actually computed

Jump by interest

Math Compression chain → Subgroup chain → IDA*
Algorithm IDA* tree → Two-phase demo → 8 algorithm cards
Hands-on Two-phase demo → 2×2 BFS → IDA* slider
History Proof animator → Timeline → References
Data Distance distribution → 17-puzzle grid → Growth chart
Open Open problems → 4×4 / Megaminx gap

💡 Tip: hover any formula for KaTeX source; blue "interactive" cards reward clicking.

Two-minute group-theory primer

1. A cube is a group

2. Generators = "what you can turn"

The six 90° face turns ${U, D, L, R, F, B}$ plus their inverses / doubles form generator set $S$ . Every state is a finite product of elements of $S$ — that's " $G$ is generated by $S$ ".

3. The Cayley graph

Make a vertex for each state; draw an edge between two states differing by one generator. This is the Cayley graph $Γ (G, S)$ . "Solving" = finding a path from your state to the identity.

4. Diameter = God's number

The maximum, over all pairs of vertices, of the shortest-path length: that's the diameter $D (G, S)$ . In other words, worst-case minimum-move count. That's God's number.

5. Lagrange ⇒ coset decomposition

6. Symmetry group $S_{48}$ ⇒ further squeeze

Phase algorithms — interactive: Kociemba vs Thistlethwaite

Total upper bound: 30 HTMPhases: 2Typical: 上界 30(实践常 20-22)

G₀|

G_{0}

| = 4.32 × 10¹⁹

⟨ U, D, L, R, F, B ⟩

Full group

G₁ (Kociemba P1)|

G_{1}

(Kociemba P1)| = 1.95 × 10¹⁰

⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩

Phase 1: kill corner orientation + edge orientation + place M-slice edges

Coset count

G_{0} / G_{1} = 2, 217, 093, 120

· phase max: 12 HTM

{e}|{e}| = 1

∅

Phase 2: solve within the restricted group

Coset count

G_{1} / G_{1} = 19, 508, 428, 800

· phase max: 18 HTM

Kociemba two-phase: $G_{1}$ = $⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ partitions the 4.3×10¹⁹ states into $2.2 \times 1 0^{9}$ cosets. Phase 1 finds the coset ( $\leq 12$ moves); Phase 2 solves inside it ( $\leq 18$ moves). Rokicki 2008 tightened to 22; 2010 added symmetry + set cover to reach 20 — meeting the lower bound (superflip needs 20), proving diameter = 20.

…

The 2010 proof's compression chain — interactive: 4.3×10¹⁹ down to ~80 super-cosets

Current scale

∣ G ∣ = 4.32 \times 1 0^{19}

Structure

Raw Rubik group

All legal 3×3 states. Lagrange's theorem lets us partition by a subgroup H — that's the starting point for everything below. A brute-force BFS storing 1 byte/state needs 43 EB; physically impossible.

Cumulative compression vs |G|: 1×

Total ≈ 35 CPU-years (2010 Google cluster). The bottleneck wasn't CPU but packing the 55.88M symmetry-classes' neighbourhood structure into the set cover — a math + engineering blend.

…

Two-phase solver — interactive: split a solve into Phase 1 + Phase 2

Scramble:

Phase 1 · 0/7

Step: 0 / 17· Total: 7 + 10 = 17 HTM

Phase 1: scramble → H7 HTM

B'U'BD2RFR'

Phase 2: solve in H10 HTM

U2R2U2F2R2U2B2D2L2D'

Phase 1 invariants (4 conditions for entering H):outside H

8 corner orient. remaining

100%

12 edge orient. remaining

100%

M-slice edges remaining

90%

Solved-ness (P2 progress)

This scramble: 7 + 10 = 17

\leq 20

(God's number). Phase 1 enters H in 7 moves; Phase 2 solves inside H in 10 moves. Phase 2 only uses 180° turns + U/D, never L/R/F/B alone.

Kociemba 1992 picks H = $⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ with |H| ≈ 1.95 × 10¹⁰. Any scramble s ∈ G: push it into a coset representative of H in $\leq 12$ moves (phase 1), then solve inside H in $\leq 18$ (phase 2) — total $\leq 30$ . Rokicki later tightened this to 20. The optimal two-phase split is rarely "shortest phase 1 then phase 2": Cube Explorer iterative-deepens to minimise |p1| + |p2|, accepting a longer p1 if it shrinks p2 more.

…

The metric decides the number — interactive: HTM / QTM / STM

Half-Turn Metric: each 90° or 180° face turn counts as 1. U2 = 1. The default in WCA literature and the metric behind the famous "20".

RU2R'U'RUR2F'RUR'U'R'FR2

total: 15 moves (HTM)

Puzzle	God's number (HTM)
2×2	11
3×3	20
Clock	12
Pyraminx	11
Skewb	11

…

God's number for every WCA event

Click any card to expand details (algorithm, prover, references). "Proven" cards have exact values; "Bounds" cards show the best known gap, waiting to be closed.

3×3×3

∣ G ∣ = 4.3252 \times 1 0^{19}

· ~43 quintillion

Proven

20HTM

The cube that gave us "God's number = 20"

Other metrics

QTM26
STM18

Proved / estimated by:Rokicki · Kociemba · Davidson · Dethridge · 2010

2×2×2

∣ G ∣ = 3.67 \times 1 0^{6}

· ~3.67 million

Proven

11HTM

Small enough to BFS overnight

Fun fact: the average optimal solution length over all 2×2 states is ≈ 8.76 HTM. One BFS pass gives you this number for free.

Other metrics

QTM14

Proved / estimated by:community BFS · 1981

Jaap Scherphuis — 2×2 page

4×4×4

∣ G ∣ = 7.40 \times 1 0^{45}

· ~7.4 × 10⁴⁵

Bounds

35–57OBTM

5×5×5

∣ G ∣ = 2.83 \times 1 0^{74}

· ~2.83 × 10⁷⁴

Bounds

52–130OBTM

6×6×6

∣ G ∣ = 1.57 \times 1 0^{116}

Bounds

75–200OBTM

7×7×7

∣ G ∣ = 1.95 \times 1 0^{160}

Bounds

99–280OBTM

3×3 Blindfolded

∣ G ∣ = 4.3252 \times 1 0^{19}

Proven

20HTM

3×3 Fewest Moves

∣ G ∣ = 4.3252 \times 1 0^{19}

Proven

20HTM

3×3 One-Handed

∣ G ∣ = 4.3252 \times 1 0^{19}

Proven

20HTM

Clock

∣ G ∣ = 2.05 \times 1 0^{16}

· ~2.05 × 10¹⁶ (incl. pin state)

Proven

12move

Megaminx

∣ G ∣ = 1.01 \times 1 0^{68}

· 20! · 3¹⁹ · 30! · 2²⁷

Bounds

48–194HTM

Pyraminx

∣ G ∣ = 9.33 \times 1 0^{5}

· ignoring 4 trivial tips

Proven

11HTM

Skewb

∣ G ∣ = 3.15 \times 1 0^{6}

Proven

11HTM

Square-1

∣ G ∣ = 5.53 \times 1 0^{11}

· 170 · 2 · 8! · 8!

Proven

13twist

4×4 Blindfolded

∣ G ∣ = 7.40 \times 1 0^{45}

Bounds

35–57OBTM

5×5 Blindfolded

∣ G ∣ = 2.83 \times 1 0^{74}

Bounds

52–130OBTM

Multi-Blind

∣ G ∣ = (4.3 \times 1 0^{19})^{k}

Trivial

20 \cdot k

HTM

Proven exact Bounds only Trivial / parametric

3×3 minimum-solution distribution — interactive: the FMC ceiling

Mean optimal length

16.22 HTM

Median

18 HTM

Current FMC WR

16 HTM

God's number (ceiling)

20 HTM

Hover a depth for exact values. d=0..15 are Rokicki's published exact counts; d=16..20 are estimates from the total-sum constraint. 99% of random 3×3 states need 17-19 moves optimally.

This is the "minimum-solution-length distribution": pick a random 3×3 state, ask how few moves it needs. Over 99% need 17-19. The exact-20 antipodes are about 10⁻¹¹ of all states (~490 million antipodes out of 4.3 × 10¹⁹). The 16-move FMC WR is essentially unreproducible because that antipode class is so rare.

…

Superflip — the "hardest" 3×3 state

Superflip — all 12 edges flipped, all 8 corners in place

A state that changed history

Superflip is a special 3×3 state: all 8 corners are in place (including orientation), but all 12 edges are "flipped 180°" (position fixed, U-colour face becomes D-colour). It was the first known distance-20 state.

In 1995 Michael Reid proved superflip needs $\geq 20$ HTM: computer-assisted enumeration of all $\leq 19$ -move solutions shows none works. Community had long suspected superflip was 'hard'; Reid's work nailed the 3×3 lower bound at 20.

Reid's 16-move QTM solution (= 20 HTM)

M' U M' U M' U2 M U M U M U2

20-move HTM optimal solution

R L U2 F U' D F2 R2 B2 L U2 F' B' U R2 D F2 U R2 U

Many 20-HTM solutions exist; the above is one. Rokicki 2010 proved there exist states (about 490M antipodes total) needing exactly 20, and superflip is the most "symmetric" representative.

…

N×N growth — interactive: state space vs diameter

Left axis grows double-exponentially ( $\sim 1 0^{N^{2}}$ ); right axis grows polynomially with a log shave. Their ratio is the "difficulty density". Hover an $N$ for exact values.

lo g_{10} ∣ G (N) ∣

(state space) proven diameter known lower bound

Θ (N^{2} / lo g N)

band (Demaine 2011)

Hover an N for exact values. 8–10 are asymptotic extrapolation only.

…

2×2 live BFS — re-prove "diameter = 11" yourself

Visited: 1 / 3,674,160Time: 0.00s

X-axis = minimum HTM distance from solved. Coloured bars = your live BFS; pale ghost = published distribution. Match ⇒ you just re-proved "2×2 God's number = 11" in the browser.

…

How are these numbers actually computed?

Eight real-world techniques, ordered by group size — from "BFS the lot" to "symmetry-quotient your way to feasibility".

BFS

Tiny groups (

\leq 1 0^{8}

): plain BFS over the whole graph, 1 byte/state for distance, full distribution + diameter in seconds-to-minutes. The "2×2 live BFS" above is exactly this. Pyraminx, Skewb, Sq-1 (twist) too.

Bidirectional BFS

BFS from both ends, meet in the middle ⇒ search space drops from

b^{d}

2 \cdot b^{d /2}

. Used for Sq-1 twist; the same trick powers many general IDA* solvers.

IDA* + Pattern Database

Mid-sized groups (

1 0^{9} - 1 0^{12}

): precompute the shortest-solution table for a subset of cubies (e.g. all corners) — a few hundred MB — and use it as an admissible heuristic

h (s) \leq d^{*} (s)

for the full problem. Iterative Deepening A* + this

h

crushes plain BFS. Kociemba's P1/P2 tables are the canonical example.

Coset partition + set cover

Huge groups (

1 0^{19} +

): split

G

into

∣ G ∣/∣ H ∣

cosets of a subgroup

H

, solve each independently. 3×3 uses

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

∣ G ∣/∣ H ∣ = 2.2 \times 1 0^{9}

. Then a greedy set-cover packs neighbouring cosets into ~80 super-cosets and you actually solve only those.

Symmetry / antisymmetry reduction

Disk-based BFS

When

∣ G ∣

outgrows RAM, batch-write each frontier layer to SSD; cross-layer dedup via external sort + uniq. Sq-1 face-turn (Shuang Chen 2017) used 722 GB — 2 bits/state to fit

1.2 \times 1 0^{13}

twistable states.

Canonical-sequence counting (lower bound)

Don't solve, just count: legal canonical sequences at depth

d

are

\leq N \cdot M^{d - 1}

(after rejecting same-axis-as-previous). Megaminx uses a commuting-faces recurrence

t (n + 1) = 36 t (n) - 240 t (n - 1) - 320 t (n - 2)

; set

t (d) \geq ∣ G ∣

⇒ lower bound on

d

. Megaminx 48, 4×4 35 came from here.

Asymptotic construction (Demaine)

Demaine et al. 2011: partition

N \times N

cubies into

O (N^{2} / lo g N)

commuting classes; solve each in

O (lo g N)

parallel moves. Match with the canonical-sequence

Ω (N^{2} / lo g N)

lower bound ⇒

Θ (N^{2} / lo g N)

, rigorous. Constants are big; only asymptotic.

IDA* + Pattern Database — interactive: how heuristics prune

…

IDA* + Pattern Database pseudocode

function solve(start):
  for depth = 0, 1, 2, ..., 20:
    if dfs(start, depth, 0) is not None: return solution
  return None  // unreachable for 3×3 (we know depth ≤ 20)

function dfs(state, max_depth, g):
  h = pattern_db.lookup(state)        // admissible: h ≤ true distance
  if g + h > max_depth: return None
  if state == identity:  return []    // solved
  for move in legal_moves(state):
    if same_axis_as_previous(move): continue
    sub = dfs(apply(state, move), max_depth, g + 1)
    if sub is not None: return [move] + sub
  return None

One IDA* call solves one state (milliseconds). Run it on all ~55.88M super-cosets with the assertion $\leq 20$ holds — and the diameter is nailed at 20.

Open problems

Four/five puzzles have no exact diameter to date. For each unfinished gap: why it's hard, what would close it, rough effort estimate.

4×4 diameter

35…57OBTM

|G| =

7.40 \times 1 0^{45}

· gap = 22 moves

Why it's hard

Indistinguishable centres mean each visual state covers ~

1.9 \times 1 0^{7}

internal states; symmetry compression is harder than 3×3. Reduction-style algorithms give loose upper bounds.

Path to close

Needs a Kociemba-style two-phase coset decomposition, but finding a suitable intermediate subgroup H ⊂ G(4×4) is hard — 4×4 has no natural "2-colour → 1-colour" reduction.

Estimate

Tightening upper to 40 likely needs ~1000 CPU-years. Lifting lower to 38-40 needs tighter canonical-sequence analysis.

Megaminx diameter

48…194HTM

|G| =

1.01 \times 1 0^{68}

· gap = 146 moves

Why it's hard

Megaminx has 12 faces, generators 11 × 2 × 2 = 44 (after rejecting same-axis). Branching factor is way larger than 3×3, limiting effective IDA* depth. Coset decomposition needs a 12-face-symmetric subgroup.

Path to close

Kociemba has experimented but found no good P1-like subgroup. Any exact proof likely needs purpose-built GPU solvers + ~100K GPU-years.

Estimate

A 146-move gap is unlikely to close within 10 years. Megaminx will probably remain "bounds known, exact diameter unknown" indefinitely.

5×5 / 6×6 / 7×7 diameter

52…130OBTM

|G| =

1 0^{74}

/ 10¹¹⁶ / 10¹⁶⁰ · gap = 78 moves

Why it's hard

State space defeats coset decomposition. Demaine's

Θ (N^{2} / lo g N)

gives the order, but the proof's hidden constants (hundreds) leave "exact diameter" physically unverifiable — no one can scan 10¹⁶⁰ states.

Path to close

Realistic progress is "tightening asymptotic constants" — shrinking Demaine's upper coefficient c1, or lifting the lower-bound coefficient c2. STOC/SODA-paper territory, not a cubing competition.

…

Two milestone proofs — interactive frame-by-frame

1 / 7

2008 starting point: ≤22, ≥20

Reid 1995 had lower 20 + upper 22. In 2008 Rokicki used Kociemba subgroup H + partial coset analysis to drop upper to 22. Still a 2-move gap.

…

Timeline

1974
Ernő Rubik invents the Magic Cube in Budapest as a teaching aid for 3-D structure, spatial reasoning, and combinatorics.
1979
Cube hits commercial shelves; Western mathematicians immediately recognise it as a finite group of order $4.3 \times 1 0^{19}$ .
1981
David Singmaster publishes Notes on Rubik's Magic Cube — the first systematic notation (URFDLB) and group-theoretic terminology underpinning everything since.
1981
2×2 / Pyraminx / Skewb BFS feasible on early PCs ⇒ each diameter is 11 (a coincidence across three different groups).
1982
Morwen Thistlethwaite publishes the 4-phase algorithm: $G_{0} \to G_{1} \to G_{2} \to G_{3} \to {e}$ , each phase from a precomputed table, capping 3×3 at $\leq 52$ HTM.
1990
Hans Kloosterman tightens the upper bound to 42; several authors that year reach 40-37.
1992
Herbert Kociemba publishes the 2-phase algorithm with $H = ⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ (his "P1" / " $G_{1}$ "): 2.2 billion cosets, each $\leq 30$ HTM, total $\leq 30$ .
1995
Michael Reid uses computer-assisted enumeration to prove superflip needs $\geq 20$ ⇒ 3×3 lower bound = 20; also proves Kociemba's bound $\leq 22$ . The 20/22 gap stands for 15 years.
2005
Mike Masonjones BFS-proves Square-1 twist-metric diameter = 13.
2006
Silviu Radu pushes 3×3 upper bound to 27; Rokicki joins in 2007 and gets it to 26.
2008
Tomas Rokicki uses Sun's 8-GB cluster to drop the upper bound to 22 — finally reaching Reid's 1995 target, but the gap is not closed.
2010
Rokicki · Kociemba · Davidson · Dethridge spend 35 CPU-years on Google: symmetry compresses 2.2B cosets to 55.88M, set-cover absorbs neighbours into ~80 super-cosets, each actually solved. No counterexample. 2010-07-13: 3×3 HTM diameter = 20.
2011
Erik Demaine et al. (arXiv:1106.5736 "Algorithms for Solving Rubik's Cubes") prove $N \times N$ God's number is $Θ (N^{2} / lo g N)$ via parallel sub-algorithms + cubie commuting-class partitioning. The rigorous $N \times N$ asymptotic.
2012
Herbert Kociemba proves Megaminx lower bound = 48 HTM via commuting-faces counting.
2014
Rokicki & Davidson prove 3×3 QTM diameter = 26 with the same coset framework; Jakob Kogler proves Rubik's Clock diameter = 12 via front-cross cosets; Rokicki separately proves 3×3 STM diameter = 18. Three new exact diameters in one year.
2017
Shuang Chen (WCA 2008CHEN27) uses 722 GB disk BFS + 3816 symmetry cosets to prove Square-1 face-turn diameter = 31. The first cubing-domain disk-BFS at this scale.
2018
Sebastiano Tronto and Vincent Sheu publish the 4×4 OBTM lower bound $\geq 35$ on SpeedSolving.
2020
Graham Siggins sets the MBLD world record 62/65. MBLD is group-theoretically trivial (diameter $20 \cdot k$ ); the record is a memory + endurance limit.
2022
Yusheng Du sets 3×3 WR at 4.86s (later tied / surpassed by Yiheng Wang), avg solution ~40 HTM, far above the 20 theoretical optimum.
2024
Merino & Subercaseaux (arXiv:2501.00144) propose a "Demigod's number" — 500k random samples + Hoeffding prove $D \leq 36$ in 5 hours, error probability $< 1 0^{- 10}$ . Dedicated page.
2025
cube20.org publishes Rubik's Clock full distance distribution as an independent re-verification of Kogler's 2014 proof, 11 years on.

FAQ + glossary

Ten common questions ("why this nickname?", "are WCA scrambles near it?", "can CFOP reach 20?", "how much compute is 35 CPU-years today?"…) plus a group-theory / algorithm glossary.

A community nickname: imagine "God" sees any state and outputs a minimum-move solution (an oracle solver). The worst-case answer is "God's number". The academic name is "Cayley graph diameter" or simply "group diameter".

Close. WCA 3×3 scrambles are random-state (post-2010), uniformly sampled from 4.3 × 10¹⁹ states. The distribution shows 99%+ need 17-19 moves optimally. Typical CFOP solutions are 50-60 moves; WR (Yiheng Wang 4.86 s) is ~40 moves — far from optimal because humans don't search.

Glossary

群 (Group): A set G with operation · satisfying closure, associativity, identity, inverses. 3×3 states under "multiplication = compose moves" form a group.
生成元 (Generator): A small set whose products give all of G. For 3×3: {U, U², U', D, …, B'} = 18 generators. Every solution is a product of these.
Cayley 图: A directed graph: vertices = group elements; edges connect any two differing by one generator. "Solving" = path from start to identity.
直径 (Diameter): Max over all pairs of vertices of shortest-path length. God's number = diameter.
陪集 (Coset): Subgroup H ⊂ G partitions G into equivalence classes: g₁ ~ g₂ ⇔ g₁⁻¹g₂ ∈ H. Coset count = |G|/|H| (Lagrange's theorem).
HTM / QTM / STM: Half-Turn / Quarter-Turn / Slice-Turn metric. Decides what counts as "one move". 3×3 HTM=20, QTM=26, STM=18.
IDA* + Pattern Database: Iterative Deepening A* + heuristic lookup. Precompute shortest distances for a cubie subset; main search uses it as an admissible lower bound.
Antipode: A state at distance = diameter from identity. 3×3 has ~ $4.9 \times 1 0^{8}$ ; 2×2 has 2,644.

…

References

cube20.org — Rokicki team's hub: 3×3 / Clock proof data + full distance distributions
cube20.org / QTM — 3×3 QTM diameter = 26 proof data (2014)
cube20.org / Clock — Rubik's Clock diameter = 12 and full distribution (2025-03-04)
Rokicki et al., SIAM J. Discrete Math 2014 — Peer-reviewed paper "The Diameter of the Rubik's Cube Group Is Twenty"
Demaine et al. 2011 — arXiv:1106.5736 — "Algorithms for Solving Rubik's Cubes", rigorous $Θ (N^{2} / lo g N)$ for N×N
Herbert Kociemba — Two-phase algorithm — Algorithm description + implementation guide by the author
Kociemba — Megaminx lower bound — Megaminx 48 lower bound via commuting-faces counting
Jaap Scherphuis\' puzzle pages — state counts + BFS data for 2×2, Skewb, Pyraminx, Square-1, Clock
Shuang Chen — Sq-1 face-turn = 31 — 722 GB disk-BFS write-up (2017-12)
Jakob Kogler — Clock = 12 — Original 2014-05 proof thread
Speedsolving — Megaminx bound — Megaminx HTM/QTM bound discussion thread
Merino & Subercaseaux 2024 — arXiv:2501.00144 — "Demigod's number" — 36 HTM probabilistic oracle
Tom Davis — Group Theory via Rubik\'s Cube — MIT primer treating the cube as a group-theory textbook
Wikipedia — God\'s algorithm — Encyclopedic article on God's number / God's algorithm

God's Number — across every WCA puzzle

Reading roadmap

First read (~15 min)

Jump by interest

Two-minute group-theory primer

1. A cube is a group

2. Generators = "what you can turn"

3. The Cayley graph

4. Diameter = God's number

5. Lagrange ⇒ coset decomposition

6. Symmetry group S48​ ⇒ further squeeze

Phase algorithms — interactive: Kociemba vs Thistlethwaite

The 2010 proof's compression chain — interactive: 4.3×10¹⁹ down to ~80 super-cosets

Two-phase solver — interactive: split a solve into Phase 1 + Phase 2

The metric decides the number — interactive: HTM / QTM / STM

God's number for every WCA event

The cube that gave us "God's number = 20"

Small enough to BFS overnight

3×3 minimum-solution distribution — interactive: the FMC ceiling

Superflip — the "hardest" 3×3 state

N×N growth — interactive: state space vs diameter

2×2 live BFS — re-prove "diameter = 11" yourself

How are these numbers actually computed?

IDA* + Pattern Database — interactive: how heuristics prune

IDA* + Pattern Database pseudocode

Open problems

Two milestone proofs — interactive frame-by-frame

Timeline

FAQ + glossary

References

God's Number — across every WCA puzzle

Reading roadmap

First read (~15 min)

Jump by interest

Two-minute group-theory primer

1. A cube is a group

2. Generators = "what you can turn"

3. The Cayley graph

4. Diameter = God's number

5. Lagrange ⇒ coset decomposition

6. Symmetry group S48​ ⇒ further squeeze

Phase algorithms — interactive: Kociemba vs Thistlethwaite

The 2010 proof's compression chain — interactive: 4.3×10¹⁹ down to ~80 super-cosets

Two-phase solver — interactive: split a solve into Phase 1 + Phase 2

The metric decides the number — interactive: HTM / QTM / STM

God's number for every WCA event

The cube that gave us "God's number = 20"

Small enough to BFS overnight

3×3 minimum-solution distribution — interactive: the FMC ceiling

Superflip — the "hardest" 3×3 state

A state that changed history

Reid's 16-move QTM solution (= 20 HTM)

20-move HTM optimal solution

N×N growth — interactive: state space vs diameter

2×2 live BFS — re-prove "diameter = 11" yourself

How are these numbers actually computed?

IDA* + Pattern Database — interactive: how heuristics prune

IDA* + Pattern Database pseudocode

Open problems

Two milestone proofs — interactive frame-by-frame

2008 starting point: ≤22, ≥20

Timeline

FAQ + glossary

Glossary

References

A state that changed history

Reid's 16-move QTM solution (= 20 HTM)

20-move HTM optimal solution

2008 starting point: ≤22, ≥20

Glossary

6. Symmetry group $S_{48}$ ⇒ further squeeze

6. Symmetry group $S_{48}$ ⇒ further squeeze