Lab 02 — Kociemba’s Two-Phase Algorithm (Rubik’s Cube)

Goal

Implement a Rubik’s Cube solver based on Kociemba’s two-phase algorithm: encode cube states as coordinates, precompute move and pruning tables, and run two chained IDA* searches to produce solutions of ≤ 30 moves (typically 19–23) in well under a second.

Background

The cube group G has |G| = 8! × 3^7 × 12! × 2^11 / 2 ≈ 4.33 × 10^19 states. Direct search is hopeless; even storing one bit per state is ~5 exabytes.

Thistlethwaite (1981): descend through a chain of 4 nested subgroups, solving into each in turn; ≤ 52 moves total.

Kociemba (1992): collapse the chain to just two phases via the subgroup

G1 = <U, D, R2, L2, F2, B2>
  • Phase 1 takes any state into G1. A state is in G1 exactly when: all corner orientations are 0, all edge orientations are 0, and the four middle-slice edges (FR, FL, BL, BR) are in the middle slice. The quotient space G/G1 has 2187 × 2048 × 495 ≈ 2.2 × 10^9 cosets.
  • Phase 2 solves within G1 using only the 10 G1 moves (U, U2, U’, D, D2, D’, R2, L2, F2, B2). |G1| = 8! × 8! × 4! / 2 ≈ 1.95 × 10^10.

Each phase is an IDA* search over small integer coordinates (not facelets), with precomputed move tables (coordinate × move → coordinate) and pruning tables (exact distance-to-goal in a simplified quotient — an admissible heuristic).

Max phase-1 depth is 12, max phase-2 depth is 18 → any cube solvable in ≤ 30 moves. Continuing to search shorter phase-1 solutions drives the total toward optimal. God’s number is 20 (Rokicki, Kociemba, Davidson, Dethridge 2010).

Interview Context

  • Direct interview question: essentially never, anywhere
  • Robotics / puzzle-solver take-homes and demo projects: the reference algorithm
  • Search/planning research roles: expected to know the ideas (coset decomposition, PDB heuristics)
  • Quant/FAANG: only as an open-ended “how would you even approach this?” conversation — the vocabulary (state encoding, admissible pruning tables, two-phase decomposition) is the answer
  • CTF / hobby: the standard kociemba library everyone uses

When to Skip This Topic

Skip if any of these are true:

  • You haven’t done Lab 01 (IDA* & pattern databases) — this lab is that lab, applied twice with group theory on top
  • You have any interview in the next 3 months — zero chance of direct payoff
  • You want a quick win — a correct implementation is a multi-day project even with this guide

Do this lab for depth, not coverage. It is the single best exercise in the curriculum for state encoding and search pruning; it is also the least likely to be asked.

Problem Statement

Solve the Cube.

Given a scrambled 3×3×3 Rubik’s Cube state (as a scramble move sequence, or a 54-character facelet string), return a move sequence of length ≤ 30 that solves it, in under 1 second (after one-time table precomputation).

Moves use face-turn metric: U, U2, U', D, D2, D', R, ..., B' — 18 moves total.

Constraints

  • Any reachable cube state (4.33 × 10^19 possibilities)
  • Solution length ≤ 30 moves (near-optimal); optimal (≤ 20) not required
  • Time: < 1 sec per solve; table precomputation may take seconds and be cached to disk
  • Memory: ≤ a few hundred MB for tables (basic variant needs < 10 MB)

Clarifying Questions

  1. Input format — facelet string or scramble sequence? (Either; scramble sequence lets you skip facelet parsing.)
  2. Is the state guaranteed reachable? (Ask. If not, validate: orientation sums and permutation parity — see Common Bugs.)
  3. Optimal or near-optimal? (Near-optimal ≤ 30. Optimal changes the algorithm to Korf’s IDA* with pattern databases.)
  4. Half-turn metric or quarter-turn metric? (Half-turn: U2 counts as one move.)
  5. May I precompute and cache tables? (Yes — that’s the entire design.)

Examples

Scramble: (identity)          → Solution: []           (0 moves)
Scramble: R                   → Solution: [R']         (1 move)
Scramble: R U R' U'           → Solution: [U R U' R']  (4 moves)
Superflip (all edges flipped) → 20 moves — proven hardest-class state

Phase decomposition example: scramble F R is not in G1 (F flips edge orientations). Phase 1 might return F' (now in G1, corners/edges oriented, slice edges home), phase 2 returns R'. Total: F' R'.

Brute Force

BFS/DFS over raw states. Branching factor ~13.3 (after pruning same-face and commuting move pairs), depth up to 20 → 13.3^20 ≈ 10^22 nodes. Dead.

IDA* over raw facelets with a weak heuristic (misplaced stickers / 8) is also dead beyond depth ~14: the heuristic is far too loose.

Brute Force Complexity

  • Time: O(b^20), b ≈ 13.3 — computationally infeasible
  • Space: BFS frontier ~10^19 states — physically infeasible

Optimization Path

  1. Cubie representation, not facelets: corner permutation (8-array), corner orientation (8-array of 0..2), edge permutation (12-array), edge orientation (12-array of 0/1). A move is a fixed permutation + orientation delta applied to these arrays.
  2. Coordinates: pack each independent property into one integer —
    • corner orientation: Σ ori[i] · 3^i over first 7 corners → 0..2186 (8th is determined: sum ≡ 0 mod 3)
    • edge orientation: first 11 edges base-2 → 0..2047 (12th determined: sum ≡ 0 mod 2)
    • UD-slice: which 4 positions hold the slice edges → C(12,4) = 495 combinations
    • phase 2: corner permutation rank (0..40319), U/D-edge permutation rank (0..40319), slice permutation (0..23)
  3. Move tables: for each coordinate, a table move[coord][m] → coord' built once by applying all 18 moves to every value. Sizes: 2187×18, 2048×18, 495×18, 40320×18, 24×18 — all tiny.
  4. Pruning tables: BFS backward from the goal over pairs of coordinates (e.g. corner-ori × slice) storing exact distance. Exact distance in a projection = admissible heuristic in the full space.
  5. Phase 1 IDA:* search to any state with all three phase-1 coordinates zero, pruning when max(h_tables) > depth remaining.
  6. Phase 2 IDA:* from the G1 state, search to solved using only the 10 G1 moves, with phase-2 pruning tables.
  7. Optimality loop: don’t stop at the first phase-1 solution — iterate longer phase-1 solutions; a phase-1 solution one move longer often yields a much shorter phase 2. Stop when total stops improving (or timeout).

Final Expected Approach

Core skeleton (cubie level, one coordinate shown per kind, phase-1 search; phase 2 is the same machinery with its own coordinates and the restricted move set):

# Corner/edge cubie model. Moves defined as (perm, ori_delta) on cubie arrays.
cpU, coU = [3,0,1,2,4,5,6,7], [0]*8
epU, eoU = [3,0,1,2,4,5,6,7,8,9,10,11], [0]*12
# ... R, F, D, L, B analogously (R and F twist corners / F,B flip edges)

class Cube:
    def __init__(self):
        self.cp, self.co = list(range(8)), [0]*8
        self.ep, self.eo = list(range(12)), [0]*12

    def apply(self, m):
        cp, co, ep, eo = MOVES[m]
        self.cp = [self.cp[cp[i]] for i in range(8)]
        self.co = [(self.co[cp[i]] + co[i]) % 3 for i in range(8)]
        self.ep = [self.ep[ep[i]] for i in range(12)]
        self.eo = [(self.eo[ep[i]] + eo[i]) % 2 for i in range(12)]

    def corner_ori_coord(self):            # 0..2186
        return sum(self.co[i] * 3**i for i in range(7))

    def edge_ori_coord(self):              # 0..2047
        return sum(self.eo[i] * 2**i for i in range(11))

    def slice_coord(self):                 # 0..494, rank of slice-edge positions
        k, coord = 0, 0
        for pos in range(11, -1, -1):
            if self.ep[pos] >= 8:          # FR,FL,BL,BR are edges 8..11
                coord += comb(pos, 4 - k); k += 1
        return coord

def build_move_table(size, coord_of, set_coord):
    table = [[0]*18 for _ in range(size)]
    for c in range(size):
        for m in range(18):
            cube = set_coord(c); cube.apply(MOVE_NAMES[m])
            table[c][m] = coord_of(cube)
    return table

def build_pruning(size1, size2, mt1, mt2):
    dist = [[-1]*size2 for _ in range(size1)]
    dist[0][0], frontier = 0, [(0, 0)]
    while frontier:
        nxt = []
        for a, b in frontier:
            for m in range(18):
                na, nb = mt1[a][m], mt2[b][m]
                if dist[na][nb] < 0:
                    dist[na][nb] = dist[a][b] + 1; nxt.append((na, nb))
        frontier = nxt
    return dist

def phase1(co, eo, sl, depth, last, path):
    h = max(PRUNE_CO_SL[co][sl], PRUNE_EO_SL[eo][sl])
    if h > depth: return None
    if co == eo == sl == 0: return path
    if depth == 0: return None
    for m in range(18):
        if last >= 0 and m // 3 == last // 3: continue      # same face
        r = phase1(MT_CO[co][m], MT_EO[eo][m], MT_SL[sl][m],
                   depth - 1, m, path + [m])
        if r: return r
    return None

def solve(cube, max_len=30):
    best = None
    for d1 in range(13):
        p1 = phase1(cube.corner_ori_coord(), cube.edge_ori_coord(),
                    cube.slice_coord(), d1, -1, [])
        if p1 is None: continue
        p2 = phase2_from(cube, p1, budget=max_len - len(p1))
        if p2 is not None:
            total = p1 + p2
            if best is None or len(total) < len(best): best = total
    return best

Elided for space, required for a working solver: the other 5 move definitions, phase-2 coordinates (corner-permutation rank, UD-edge rank, slice permutation) with their move/pruning tables over the 10 G1 moves, facelet-string parsing, and coordinate → cube reconstruction (set_coord). Full implementations run 400–600 lines.

Data Structures

  • Four fixed-size int arrays per cube state (cp, co, ep, eo)
  • Flat uint16 move tables: coordinate × 18 → coordinate
  • Byte pruning tables over coordinate pairs (exact BFS distances; fits in a few MB)
  • Recursion stack only — IDA* needs no open/closed sets

Correctness Argument

  • G1 is a subgroup, and the three phase-1 coordinates are invariants of its cosets: a state lies in G1 ⟺ all three are zero. So phase 1 solves the coset problem exactly.
  • Move tables are exact by construction (built by applying real moves to real states).
  • Pruning tables store exact distances in a quotient of the state space. Distances in a quotient never exceed distances in the original ⇒ admissible heuristic ⇒ IDA* returns a shortest phase-1 (resp. phase-2) solution for each depth bound.
  • Termination bound: every coset is reachable in ≤ 12 phase-1 moves and every G1 state solvable in ≤ 18 phase-2 moves (known table maxima) ⇒ solver always returns ≤ 30 moves.
  • Concatenation of per-phase-optimal solutions is not globally optimal — hence the iteration over longer phase-1 solutions to shrink the total.

Complexity

  • Precomputation: O(Σ coord_size × 18) move tables + BFS over pruning-table spaces (~10^6–10^8 entries depending on variant) — seconds, cacheable
  • Solve: exponential in the worst case, but pruning tables cut effective branching so hard that typical solves visit 10^4–10^6 nodes — milliseconds to ~1 sec
  • Space: < 10 MB basic; Kociemba’s tuned tables ~80 MB

Implementation Requirements

  • Cubie-level move application must be exact (test: every move applied 4× = identity)
  • Orientation coordinates drop the last cubie (its value is forced by the mod-3 / mod-2 invariant)
  • Phase-2 move set excludes quarter turns of R, L, F, B — enforce in the move loop, not the tables
  • Prune same-face consecutive moves; also fix an order for commuting opposite-face pairs (U D = D U — search only one)
  • Validate input state: corner ori sum ≡ 0 (mod 3), edge ori sum ≡ 0 (mod 2), corner-permutation parity = edge-permutation parity
  • Cache tables to disk; rebuild only on cache miss

Tests

  • Identity cube → empty solution
  • Each single move m → solution is its inverse
  • 100 random scrambles (25 random moves each): apply returned solution, assert solved, assert length ≤ 30
  • Superflip: solver returns ≤ 24 in two-phase mode quickly; ≤ 20 with the optimality loop given time
  • Unsolvable states (single twisted corner, single flipped edge, two swapped corners) → rejected by validation
  • Move-table sanity: move[coord][m] then move[·][inverse(m)] returns coord
  • Pruning-table sanity: entry 0 exactly at the goal projection; max entry = 12 (phase 1)

Follow-up Questions

  • What is God’s number and how was it proven? → 20 in half-turn metric. Rokicki et al. 2010: partitioned the group into ~2.2 × 10^9 cosets of G1, solved each coset set to ≤ 20 with a coset solver, ~35 CPU-years donated by Google. Quarter-turn metric answer is 26.
  • How would you find provably optimal solutions for a single cube? → Korf’s algorithm (1997): plain IDA* in the full space with pattern-database heuristics (corner PDB: 88 M entries, plus two edge PDBs, take the max). Hours per hard cube vs milliseconds for two-phase.
  • Why two phases instead of Thistlethwaite’s four? → Fewer phases = fewer concatenation seams = shorter totals (30 vs 52), at the cost of bigger tables per phase. Two is the sweet spot where tables still fit in memory.
  • Why IDA and not A*?* → A* stores the open set; at 10^6+ expanded nodes with 13-way branching, memory explodes. IDA* is O(depth) memory and re-expansion overhead is bounded because node count grows geometrically per iteration.
  • How do the 48 cube symmetries help? → States equivalent under rotation/reflection share distances, shrinking pruning tables ~16–48× (Kociemba’s implementation stores sym-coordinates). Same trick as symmetry reduction in model checking.
  • Does this generalize to 4×4×4? → Partially. No fixed centers, orientation parity rules differ, and the group is ~7.4 × 10^45 — solvers use reduction (pair up pieces to emulate a 3×3×3) rather than a direct two-phase.

Product Extension

  • Robot solvers (the sub-second solve step behind every cube-robot demo)
  • kociemba / min2phase libraries powering cube apps and timers
  • The general pattern — compress state into coordinates, precompute exact distances in projections, IDA* with max-of-heuristics — is the production recipe for planning problems (warehouse robots, protein design search, chip-placement subproblems)
  • Coset-solving methodology reused in mathematical computation at scale (the God’s number computation itself)

Language/Runtime Follow-ups

  • C/C++: the reference choice; tables as flat arrays, solve in microseconds (min2phase).
  • Python: cubie math is fine; use flat lists + disk-cached tables. Pure-Python solves in ~0.1–1 sec. pip install kociemba wraps C.
  • Java: Herbert Kociemba’s original Cube Explorer lineage; min2phase Java port is the canonical fast one.
  • JavaScript: cubing.js implements two-phase for browser cube timers — tables via WASM.

Common Bugs

  1. Orientation coordinate includes all 8/12 cubies: the last orientation is dependent (sums ≡ 0); including it creates unreachable coordinates and breaks table indexing.
  2. Move applied to orientation without permuting first: orientation delta must be added to the orientation of the cubie arriving at the slot: co'[i] = co[cp_m[i]] + delta[i].
  3. Phase 2 accidentally uses all 18 moves: produces states outside G1 mid-search; pruning tables (built over 10 moves) then underestimate garbage states and the search corrupts.
  4. Parity mismatch accepted: corner and edge permutation parities must be equal; skipping validation makes the solver loop forever on unsolvable input.
  5. Stopping at the first phase-1 solution: correct but yields 25–30 move solutions; the iteration over longer phase-1 attempts is what gets you to ~20.
  6. Slice-coordinate ranking inconsistent between the coordinate function and the reconstruction used for table building — tables silently index wrong states.

Debugging Strategy

  • Verify each move: apply 4× → identity; verify R R' → identity
  • Verify coordinate round-trips: coord_of(set_coord(c)) == c for all c in range
  • Verify pruning tables: value 0 only at goal projection; histogram of distances matches published tables (phase-1 max 12, phase-2 max 18)
  • Solve states of known distance (1-move, 2-move scrambles) and assert exact lengths
  • Diff intermediate coordinates against the kociemba reference library on random scrambles

Mastery Criteria

  • Explain the coset decomposition (why G1, what phase 1 actually solves) in ≤ 5 min without notes
  • Implement the cubie model + all three phase-1 coordinates in ≤ 60 min
  • Build move + pruning tables and a working phase-1 IDA* in ≤ half a day
  • State from memory: |G| ≈ 4.3 × 10^19, phase-1 space 2.2 × 10^9, max depths 12/18, God’s number 20
  • Articulate why pruning tables are admissible (quotient-space argument) and why two-phase is near- but not exactly optimal
  • Name the optimal alternative (Korf + pattern databases) and its cost trade-off