¶ Rubik’s Cube (3×3×3)
The 3×3×3 Rubik’s Cube is a deterministic permutation puzzle with a very large state space and highly structured transitions. The number of reachable configurations is approximately . [1]
From an algorithmic perspective, cube solving is a shortest-path problem on an implicit state graph:
- Vertices: cube configurations (states)
- Edges: legal moves (actions)
- Goal: the solved configuration
- Cost model: uniform step cost (typically), so the objective is a minimum-length move sequence for a chosen metric.[2]
¶ Puzzle model
¶ State space and constraints
Rubik’s Cube states can be described by the permutation and orientation of corner and edge cubies, subject to invariants (e.g., parity constraints and orientation sum constraints). These constraints reduce the naive count of permutations and orientations to the reachable set size stated above.[1:1]
The legal moves generate the Rubik’s Cube group, a finite group acting on cubie permutations and orientations.
Korf reports how rapidly the search tree grows with depth under standard pruning rules (e.g., forbidding redundant successive twists). Even at moderate depths the node counts become extremely large, motivating strong heuristics and careful search design (in particular, reducing the effective branching factor).[1:2]
¶ Move set and move-count metrics
Two move-count conventions are widely used:
- Half-turn metric (HTM) (often called face-turn metric): quarter turns and half turns each count as one move.
- Quarter-turn metric (QTM): quarter turns count as one move; half turns count as two moves.
Publications must be compared under the same metric: solution lengths can differ substantially between HTM and QTM.[3][4]
Metric note: Korf (1997) reports optimal solutions under a face-turn-style metric (HTM). McAleer et al. (2018) report results in QTM, and explicitly note that cross-metric comparisons can produce apparent outliers.[1:3][4:1]
¶ Solver families
The literature and practical tooling for cube solving cluster around three families:
- Optimal heuristic search (provably shortest solutions, typically expensive at high difficulty)
- Group-structure solvers (complete and extremely fast, but not optimal)
- Learned planning (high solve rate under budgets, learned guidance, not guaranteed optimal)
¶ Optimal heuristic search: IDA* + Pattern Databases
The classic optimal approach is iterative deepening A* (IDA*), a linear-space variant of A*. IDA* searches in cost-bounded iterations over , increasing the bound until a goal is found.[5][2:1]
The decisive ingredient is a strong admissible heuristic . Korf’s breakthrough was to use pattern databases (Pattern Databases): precomputed exact distances for carefully chosen abstractions (subproblems). Table lookup then yields admissible lower bounds during search.[6][1:4]
These tables are constructed by running breadth-first search (BFS) backward from the goal within the reduced state space (conceptually aligned with Retrograde Analysis).[1:5]
¶ What the PDB heuristic stores
Korf (1997) builds three large PDBs and combines them using a maximum:
- one PDB over all 8 corners
- two PDBs over two disjoint sets of 6 edges
The maximum combination preserves admissibility while strengthening pruning.[1:6]
¶ Empirical scale (optimal search)
Korf solved ten random instances optimally; the measured node generations reach into the hundreds of billions to over a trillion nodes for the hardest instances in that sample.[1:7]
¶ Group-structure solver: Kociemba two-phase
A widely used practical baseline is the Kociemba two-phase solver (Kociemba Two-Phase Solver). It decomposes the cube group into two phases by first moving into a restricted subgroup and then solving within it. The method is complete and typically very fast, but it does not guarantee shortest solutions.[7][4:2]
¶ Learned planning: DeepCube (ADI + MCTS)
DeepCube couples a learned value/policy model with search. Training is performed without human demonstrations, and planning is performed by a guided tree-search procedure:
- Autodidactic Iteration (ADI)[4:3]: trains a joint policy (action priors) and value (distance-to-go estimate) model from generated cube states and shallow lookahead targets.
- Monte Carlo Tree Search (MCTS)[4:4][8][9]: uses these priors and value estimates to bias exploration and allocate computation toward promising branches, producing an explicit solution path.
¶ MCTS as the planning component
In DeepCube, MCTS constructs a search tree rooted at the scrambled cube and uses the network output for guidance:
- Policy guidance: prior action probabilities steer expansion toward moves rated as promising by the policy head.
- Value guidance: leaf evaluations estimate progress toward the solved state and influence backup values.
- Compute allocation: repeated simulations concentrate expansions on the most promising parts of the tree.[4:5]
DeepCube’s implementation uses an asynchronous variant of MCTS and applies a virtual loss mechanism to reduce duplicate exploration across workers operating in parallel.[4:6]
¶ Extracting a concrete move sequence
Once a solved node is reached, DeepCube can extract a move sequence in two ways:
- Direct extraction from the traversal that reached the solved node, which can include cycles.
- Shortest-path extraction by converting the explored structure into an undirected unit-weight graph and running BFS, which tends to shorten solutions by removing cycles (reported as a small but consistent improvement).[4:7]
¶ Empirical behavior (runtime variance)
McAleer et al. report that DeepCube solves the evaluated fully scrambled cubes within the experiment’s time limit, but with substantial variance in runtimes; the histogram below summarizes the runtime profile for fully scrambled cubes.[4:8]
Compared to group-structure solvers (e.g., Kociemba’s two-phase method), DeepCube’s solve times are less stable; compared to optimal heuristic search baselines, the guided learned planning approach is designed to reduce expansions under a fixed compute budget by focusing search on high-value regions of the state space.[4:9]
¶ Comparison
¶ Solve rate under a fixed time budget
DeepCube reports high solve rates under time limits across scramble distances, while greedy or optimal-search baselines degrade sharply under the same budget as scramble difficulty increases.[4:10]
¶ Solution length distributions (trade-off: speed vs optimality)
The distributions below illustrate the central trade-off:
- Kociemba: extremely fast and complete, but solution lengths are not minimal.
- DeepCube: learned planning can match or beat Kociemba frequently, with larger variance.
- Korf (optimal): near-optimal/optimal lengths on near-solution cubes, but runtime becomes prohibitive for full scrambles.[4:11][1:8]
¶ Summary
| Aspect | IDA* + PDBs (optimal) | Kociemba two-phase (group-based) | DeepCube (ADI + MCTS) |
|---|---|---|---|
| Primary objective | Provable shortest solutions (for a chosen metric) | Fast complete solving | High solve rate under budgets via learned guidance |
| Completeness | Yes | Yes | Yes (as reported in evaluation) |
| Optimality | Yes | No | No (often short, not guaranteed) |
| Guidance signal | Admissible lower bounds from PDBs | Phase constraints + pruning tables | Learned value + policy priors |
| Dominant cost | Online search time at high depths | Engineering + tables, but fast online | Offline training + online MCTS budget |
| Typical behavior | Extremely large node expansions on hard scrambles | Very fast and stable runtime | Variable runtime; small tree expansions relative to optimal search |
¶ References
¶ Image references
- Fig. 1 — Wikimedia Commons (illustrative Rubik’s Cube SVG).
- Fig. 2 — Korf (1997), Table 1 (nodes vs depth).
- Fig. 3 — Korf (1997), Table 2 (nodes generated for 10 random instances).
- Fig. 4 — McAleer et al. (2018), solve-time distribution histogram.
- Fig. 5 — McAleer et al. (2018), solve rate vs scramble distance.
- Fig. 6 — McAleer et al. (2018), solution-length distributions.
¶ Literature
Richard E. Korf. “Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases.” AAAI, 1997. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Peter E. Hart, Nils J. Nilsson, Bertram Raphael. “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics 4(2), 1968. ↩︎ ↩︎
Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. “The Diameter of the Rubik’s Cube Group is Twenty.” SIAM Review 56(4), 2014. ↩︎
Stephen McAleer, Forest Agostinelli, Alexander Shmakov, Pierre Baldi. “Solving the Rubik’s Cube Without Human Knowledge.” arXiv:1805.07470, 2018. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Richard E. Korf. “Depth-first Iterative-deepening: An Optimal Admissible Tree Search.” Artificial Intelligence 27(1), 1985. ↩︎
Joseph C. Culberson, Jonathan Schaeffer. “Searching with Pattern Databases.” Advances in Artificial Intelligence (Canadian AI), Springer, 1996. ↩︎
Herbert Kociemba. “Two-phase algorithm details.” Technical description hosted at kociemba.org. ↩︎
Levente Kocsis, Csaba Szepesvári. “Bandit Based Monte-Carlo Planning.” ECML, 2006. ↩︎
Rémi Coulom. “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search.” Computers and Games, 2006/2007. ↩︎