IDA* + prune tables

The cube has 4.33×10¹⁹ states; a plain BFS is hopeless. A* prunes much of the tree with a heuristic, but A*’s OPEN/CLOSED lists must live in memory — the active frontier at any moment is roughly the surface of a ball of radius d, and for d ≈ 20 that’s 10¹²+ nodes. Won’t fit.

IDA* (Iterative Deepening A*) trades memory for redundant work: run A* depth-first with no OPEN/CLOSED, just a recursion stack. Space drops from O(b^d) to O(d). Each subtree gets re-expanded log-many times, but for cube-shaped problems (b ≈ 13, d ≤ 20) this trade is overwhelmingly worth it.

IDA* doesn’t commit to a depth limit. Start with bound = h(start); do a bounded DFS that expands only nodes with g + h ≤ bound. If nothing is found, raise bound to the smallest f-value that overflowed this round, and search again. Each round explores strictly more states than the previous one.

function idaStar(start: State): Move[] | null {
  let bound = h(start);
  while (true) {
    const t = search(start, [], 0, bound);
    if (t === FOUND) return solution;
    if (t === Infinity) return null;   // unsolvable
    bound = t;                          // next round = smallest overflow f
  }
}

function search(node: State, path: Move[], g: number, bound: number): number {
  const f = g + h(node);
  if (f > bound) return f;              // prune; revisit next round
  if (isGoal(node)) { solution = path; return FOUND; }
  let min = Infinity;
  for (const m of moves(node, path)) {  // includes move pruning
    const child = apply(node, m);
    path.push(m);
    const t = search(child, path, g + 1, bound);
    if (t === FOUND) return FOUND;
    if (t < min) min = t;
    path.pop();
  }
  return min;
}

Two invariants give correctness: (1) any solution found in a round has length ≤ bound; (2) bound is monotonically increasing. If h is admissible (≤ true distance), IDA* finds the optimum.

Search quality is entirely about h. Two properties to keep straight:

• Admissible: h(n) ≤ d*(n) — never overestimates. Required for optimality.
• Consistent / monotone: h(n) ≤ 1 + h(n') for any neighbor n' — the triangle inequality. Stronger than admissibility; lets A* skip re-opening CLOSED nodes, and lets IDA* drop some redundant g+h checks.

For the cube, any lower bound on distance-to-solved is automatically admissible. The canonical construction: pick a sub-state (a subset of cubies or a coordinate), precompute the optimal distance from every value of that sub-state to its solved value, and store it as a lookup table — the pattern database (or "prune table").

Bigger sub-states give tighter h and harsher pruning, but bigger tables. The practical recipe: take max over a handful of disjoint small tables — still admissible, plus a combined lower bound.

Materialize "sub-state s → optimal distance to solved" as an array prune[s]; O(1) lookups during search. This is the heart of IDA* on the cube.

Kociemba phase 1 uses the (corner-orient, UD-slice) pair as a sub-state: space = 3⁷ × C(12,4) = 2187 × 495 = 1,082,565. Stored as one integer per entry, ~1 MB. The phase-1 IDA* takes max(corner_prune, edge_prune, slice_prune) as h.

CubeRoot’s own CFOP std solver is more aggressive: every CFOP stage owns a prune table, and all four F2L slots share one table by mapping each slot to a canonical one via conjugation — see the CFOP multi-stage solver page.

Distances in a cube prune table are typically ≤ 14 (each sub-state diameter is small), so 4 bits per entry is plenty. Two entries per byte halves the table footprint.

function packed(idx: number): number {
  const byte = table[idx >>> 1];
  return (idx & 1) ? (byte & 0x0F) : (byte >>> 4);
}

function setPacked(idx: number, val: number): void {
  const i = idx >>> 1;
  if (idx & 1) table[i] = (table[i] & 0xF0) | (val & 0x0F);
  else         table[i] = (table[i] & 0x0F) | ((val & 0x0F) << 4);
}

14 isn’t a tight ceiling in practice. When you do want to shrink further: the distance-mod-3 trick stores just (d mod 3) in 2 bits and recovers the true distance from a neighbor (d(n) = d(n') ± 1; mod-3 disambiguates). Cuts the table again at the cost of one extra lookup per access.

Entries must hold true shortest distances. Running BFS from each state would be O(N) BFSes. The trick: run one BFS, starting from the solved state and walking outwards. Each newly discovered state gets d = current_depth + 1.

function buildPruneTable(N: number): Uint8Array {
  const table = new Uint8Array(N).fill(0xFF);
  table[encode(SOLVED)] = 0;
  let depth = 0, filled = 1;
  while (filled < N) {
    for (let s = 0; s < N; s++) {
      if (table[s] !== depth) continue;
      for (const m of MOVES) {
        const t = encode(apply(decode(s), m));
        if (table[t] === 0xFF) {
          table[t] = depth + 1;
          filled++;
        }
      }
    }
    depth++;
  }
  return table;
}

"From solved" works because every cube move is a bijection — forward and backward distances are equal. Real implementations don’t re-scan all N each level; they keep a frontier list and advance it.

Real branching factor is well below 18. Two rules push it to ~13:

• No consecutive same-face moves: after U, never U / U' / U². All same-face combinations are already enumerated as a single move.
• Canonical order for same-axis pairs: U and D commute. Allow only one of the orderings (say, U before D) and prune the reverse.

Implementation: moves(node, path) peeks at the previous face and filters. Effective branching factor drops from 18 to about 13.34 — not dramatic per step, but the ratio 1320 / 1820 is ~10⁵.

The cube has 48 symmetries (24 rotations × 2 reflections). A state s and any image σ(s) have identical optimal solve lengths, so a prune table can store only one representative per equivalence class. Size shrinks by ~48× (closer to 16× after accounting for stabilizers).

min2phase pushes this to the limit — its huge tables (CornUDSliceFlip / CornEdg) wouldn’t fit in memory without it. The cost: each lookup needs symmetry normalization first, mapping the live state to its canonical form.

For a full symmetry-compressed implementation see min2phase.

One IDA* solve runs are roughly bound by three things:

• How tight h is — closer to d*, earlier the prune. Going from 0.5 to 0.8 tightness typically buys ~10× speed.
• Branching factor — at the same d, going from b=18 to b=13 cuts cost by (13/18)^d.
• Table access locality — prune tables get hammered. Fitting in L2 vs L3 is a few × difference. That’s why 4-bit packing / mod-3 isn’t just space, it’s speed.

Three families of solver on CubeRoot all sit on IDA*:

1. Kociemba two-phase — one IDA* per phase; the max of three sub-state prune tables is h.
2. min2phase — phases interleaved; huge symmetry-compressed prune tables; sub-millisecond per solve in steady state.
3. CFOP std solver — one IDA* per CFOP stage; F2L slots share prune tables via conjugation; cross-stage lower-bound propagation.

Same template, different answers to: which sub-state for the prune table, how to compress it, how to glue the stages together.