Research · Benchmarks · Paper
God's Algorithm for Rubik's Cubes
Polynomial-time optimal search for generalized c₁×c₂×n puzzles, paired with a modular laboratory comparing classical, parallel, and learning-guided graph search.
34
Search methods
All registered techniques compared on each size
O(n)
Optimal class
Polynomial in n for fixed c₁, c₂ (Demaine §6)
3–4³
Benchmarks
3×3×3, 4×4×4 · seeds 1–5 · 500k nodes
Key findings
- On 3×3×3 and 4×4×4, only BDFS and the zipper family (zipper, dd-zipper, tdr-zipper, dd-tdr-zipper) solved all five scrambles under a 500k node cap.
- BDFS averaged ~25 ms on 3×3×3 and ~1.3 s on 4×4×4; parallel DD zippers traded ~10× latency for layer throughput on 4×4×4.
- A* reached 5/5 on 3×3×3 but averaged ~31 s—an order of magnitude slower than bidirectional methods on the same seeds.
- Demaine optimal solvers, BFS/IDA*, and ML-guided search (MCTS, SOM, factor-*) timed out or missed solutions on 4×4×4 within budget.
- Algorithm X (Knuth dancing links) provides a classical exact-cover baseline; it did not finish within cap on 3×3×3 or 4×4×4 in our sweep.