§22

Solving algorithms

Starting from §10's Thistlethwaite subgroup chain, through Kociemba's two-phase, Korf's optimal IDA*, and Rokicki's coset enumeration — each solver translates a different group-theoretic idea into running code. Group theory rendered as engineering, in one of its cleanest forms.

22.1 Comparison table

Algorithm	Type	avg HTM	max HTM	Tables	Runtime
Thistlethwaite (1981) first finite-memory suboptimal	4-stage subgroup chain	~52	~52	< 100 KB	milliseconds
Kociemba (1992) modern fast-suboptimal standard	Two-phase	~21	~30	~50 MB	ms-seconds
Korf IDA* (1997) first truly optimal solver	Optimal IDA* + pattern DBs	17.34	20	~80 MB	sec-min
Rokicki cosets (2010) used to prove God's # = 20	symmetry-reduced enumeration	17.7	20	~3 GB cosets	CPU-years

22.2 Thistlethwaite: subgroup chain + per-stage search

Core idea: decompose the solve into 4 independent subproblems, each a bounded BFS/IDA* on the quotient $G_{i} / G_{i + 1}$ . The quotients are small (≤ 10⁶), so each stage has a complete pruning table.

G_{0} = G \supset G_{1} \supset G_{2} \supset G_{3} \supset {e}

G₀ → G₁

fix edge orientation

EO = 0

G₁ → G₂

fix CO + UD slice

CO = 0, FR/FL/BL/BR in slice

G₂ → G₃

reach domino orbits

corner & edge orbit parity

G₃ → e

solve (only 180° turns)

identity

theoretical max depth sum: 45 moves (HTM). The improved 45-move bound comes from optimal IDA* within each stage.

22.3 Kociemba's two-phase algorithm

Kociemba collapsed 4 stages into 2: Phase 1 moves the state into $G_{2} = ⟨ U, D, L^{2}, R^{2}, F^{2}, B^{2} ⟩$ , Phase 2 solves within G₂. Both phases run IDA* with pruning tables.

Phase 1

G → G₂

Coords: (co, eo, slice). Table sizes 2187 × 2048 × 495 ≈ 2.2 × 10⁹. IDA* with heuristic max(co, eo, slice).

→

Phase 2

G₂ → e

Coords: (cp, ep_UD, ep_slice). Table 40320 × 40320 × 24 ≈ 4 × 10¹⁰. Only 10 generators allowed in this phase.

Two-phase is not optimal (overshoots a few moves) but runs in milliseconds at ~21 HTM avg.; nearly every production solver is a variant (cube20 uses Reid's tweaks; kociemba.org uses Phase-2 lookup with N=18).

22.4 Korf's IDA*: the first optimal solver

In 1997 Richard Korf delivered the first optimal Rubik's Cube solver via IDA* (Iterative Deepening A*) plus an ~80 MB pattern database. Key idea: precompute exact distances on chosen subsets (8 corners, or 6 edges) and use h(s) = max of subset distances. The h is admissible (never overestimates), so IDA* yields the optimum.

function IDAstar(start): bound = h(start) while True: t = search(start, 0, bound) if t == FOUND: return path bound = t function search(node, g, bound): f = g + h(node) if f > bound: return f if isGoal(node): return FOUND min = ∞ for child in successors(node): t = search(child, g + 1, bound) if t == FOUND: return FOUND if t < min: min = t return min

22.5 Rokicki coset enumeration: the 20-move proof

Tomas Rokicki et al. (2010) used an algorithm that does not solve cubes: partition G into cosets G/H (H = Kociemba's G₂), and for each coset prove "solvable in ≤ 20 moves." Key ingredients:

Symmetry reduction: use the order-48 Oₕ symmetry group to collapse |G/H| ≈ 2 × 10⁹ cosets down to ~5 × 10⁷ equivalence classes.
Each coset ≤ 20 moves: for each representative, IDA* asks "solvable in ≤ 19 moves?" If yes, all 4 × 10¹⁰ states in that coset are. If not, try 20 — must succeed.
Total CPU time: Google donated ~35 CPU-years. Announced 2010: the cube's diameter is exactly 20 HTM.

22.6 Korf IDA* — proving admissibility

Theorem 22.1 — admissibility

Let

h_{1}, h_{2}, h_{3} : G \to N

be three "subproblem distances" (corners, edge subset 1, edge subset 2). Define

h (g) = max (h_{1}, h_{2}, h_{3})

. Then

h (g) \leq d_{S} (g, e)

for every g (admissible).

Proof

Let g ∈ G with $d_{S} (g, e) = k$ . Project g via the homomorphism $π_{i}$ onto subset i; then $h_{i} (g) = d_{S} (π_{i} (g), e)$ .

Since π_i is a homomorphism, a k-step word for g pushes forward to a k-step word for π_i(g). So $h_{i} (g) \leq k$ , and the max of admissible heuristics is admissible. ∎

Key point: each $h_{i}$ in Korf's pattern database is the exact BFS distance in subset i — this is what makes admissibility hold. A loose heuristic (e.g. "mismatch count") gives no optimality guarantee.

∎

22.7 Complexity comparison

Algorithm	Optimal?	Time	Space	Typical len
Naive BFS	yes	$O (∣ G ∣)$	$O (∣ G ∣)$	infeasible
Korf IDA* (1997)	yes	$O (b^{d})$ , b ≈ 13.34, d ≤ 20	~80 MB	opt. 18–20 HTM
Kociemba two-phase (1992)	no (suboptimal)	~ms	~100 MB	~21 HTM
Thistlethwaite (1981)	no	~ms	~10 MB	~50 HTM
Rokicki 2010	verifier, not solver	35 CPU-yr	~2 GB	no alg output
DeepCubeA (2019)	no	~s	~GB	~21 HTM

22.8 DeepCubeA — deep reinforcement learning (2019)

In 2019 a UC Irvine team (McAleer, Agostinelli, Shmakov, Baldi) published DeepCubeA in Nature Machine Intelligence: a neural network approximates the cost-to-go function h(s), replacing Korf's pattern database. The net is trained "autodidactically" on scrambles solved by reverse BFS, then combined with A* search.

h is no longer admissible — the network is approximate, occasionally over- or underestimating, so output is not guaranteed optimal (but typically close: ~21 HTM avg, comparable to Kociemba).
Generalises across puzzles: the same architecture learned near-optimal heuristics for 4×4, 5×5, the 24-puzzle, and Lights Out — something Korf-style PDBs cannot, since they are hand-crafted per puzzle.
Training cost: hundreds of GPU-hours (orders of magnitude cheaper than Rokicki's 35 CPU-years). Yet the only worst-case guarantee remains Rokicki's exact 20 HTM proof.

∎

cuberoot.me · Rubik's Cube as a Group · 2026