Benchmark results
Full comparison of all 34 registered methods on 3×3×3, 4×4×4, 5×5×5. Five random scrambles per size (seeds 1–5), node cap 500,000, 1 threads for DD-*.
Cross-size comparison
Mean wall-clock and success rate for every method across all puzzle sizes.
| Method | 3×3×3 | 4×4×4 | 5×5×5 | |||
|---|---|---|---|---|---|---|
| Mean | Success | Mean | Success | Mean | Success | |
| algorithm-x | — | 0/5 | — | 0/5 | — | — |
| astar | 31.4 s | 5/5 | — | 0/5 | — | — |
| bdfs | 25 ms | 5/5 | 1.3 s | 5/5 | — | — |
| bfs | 64.9 s | 1/5 | — | 0/5 | — | — |
| dd-bfs | 70.0 s | 1/5 | — | 0/5 | — | — |
| dd-dfs | 64.9 s | 1/5 | — | 0/5 | — | — |
| dd-factor-sgd | — | 0/5 | — | 0/5 | — | — |
| dd-mcts | — | 0/5 | — | 0/5 | — | — |
| dd-som | — | 0/5 | — | 0/5 | — | — |
| dd-tdr-zipper | 65.3 ms | 5/5 | 15.4 s | 5/5 | — | — |
| dd-zipper | 45.9 ms | 5/5 | 10.4 s | 5/5 | — | — |
| demaine | 127.4 s | 2/5 | — | 0/5 | — | 0/5 |
| dfs | — | 0/5 | — | 0/5 | — | — |
| dp | 75.6 s | 1/5 | — | 0/5 | — | — |
| dp-bfs | 126.0 s | 2/5 | — | 0/5 | — | — |
| exact-bfs | 74.6 s | 1/5 | — | 0/5 | — | — |
| factor-bp | — | 0/5 | — | 0/5 | — | — |
| factor-nmf | — | 0/5 | — | 0/5 | — | — |
| factor-sgd | — | 0/5 | — | 0/5 | — | — |
| fuzzy-pattern-db | 88.1 s | 1/5 | — | 0/5 | — | — |
| ida | — | 0/5 | — | 0/5 | — | — |
| irregular-astar | 59.3 s | 4/5 | — | 0/5 | — | — |
| irregular-bfs | 69.2 s | 1/5 | — | 0/5 | — | — |
| irregular-ida | — | 0/5 | — | 0/5 | — | — |
| max-breadth-fs | 38.3 s | 1/5 | — | 0/5 | — | — |
| mcts | — | 0/5 | — | 0/5 | — | — |
| polytree-bfs | 91.1 s | 1/5 | — | 0/5 | — | — |
| polytree-dfs | — | 0/5 | — | 0/5 | — | — |
| randomized-bfs | — | 0/5 | — | 0/5 | — | — |
| randomized-dfs | — | 0/5 | — | 0/5 | — | — |
| som | — | 0/5 | — | 0/5 | — | — |
| tdr-zipper | 85.3 ms | 5/5 | 15.0 s | 5/5 | — | — |
| tour | — | 0/5 | — | 0/5 | — | — |
| zipper | 58.3 ms | 5/5 | 10.2 s | 5/5 | — | — |
Mean wall-clock (ms)
3×3×3 · Five random scrambles per size (seeds 1–5; default length max(4, min(2n, 20)))
Loading chart…
Bar length = mean ms (successful runs only)Node cap 500,000
All methods · 3×3×3
| Method | Success | Mean | Min | Max | Notes |
|---|---|---|---|---|---|
| bdfs | 5/5 | 25 ms | 20.1 ms | 31.5 ms | optimal |
| dd-zipper | 5/5 | 45.9 ms | 32.6 ms | 56.8 ms | optimal |
| zipper | 5/5 | 58.3 ms | 39.4 ms | 72.3 ms | optimal |
| dd-tdr-zipper | 5/5 | 65.3 ms | 50.8 ms | 77.3 ms | optimal (ID) |
| tdr-zipper | 5/5 | 85.3 ms | 63.7 ms | 101.7 ms | optimal (ID) |
| astar | 5/5 | 31.4 s | 1.1 s | 73.9 s | optimal |
| max-breadth-fs | 1/5 | 38.3 s | 38.3 s | 38.3 s | optimal |
| irregular-astar | 4/5 | 59.3 s | 1.2 s | 135.4 s | optimal |
| dd-dfs | 1/5 | 64.9 s | 64.9 s | 64.9 s | optimal |
| bfs | 1/5 | 64.9 s | 64.9 s | 64.9 s | optimal |
| irregular-bfs | 1/5 | 69.2 s | 69.2 s | 69.2 s | optimal |
| dd-bfs | 1/5 | 70.0 s | 70.0 s | 70.0 s | optimal |
| exact-bfs | 1/5 | 74.6 s | 74.6 s | 74.6 s | optimal |
| dp | 1/5 | 75.6 s | 75.6 s | 75.6 s | optimal |
| fuzzy-pattern-db | 1/5 | 88.1 s | 88.1 s | 88.1 s | optimal |
| polytree-bfs | 1/5 | 91.1 s | 91.1 s | 91.1 s | optimal |
| dp-bfs | 2/5 | 126.0 s | 77.2 s | 174.9 s | optimal |
| demaine | 2/5 | 127.4 s | 75.3 s | 179.6 s | optimal |
| dfs | 0/5 | — | — | — | no solution |
| ida | 0/5 | — | — | — | no solution |
| tour | 0/5 | — | — | — | timeout |
| irregular-ida | 0/5 | — | — | — | no solution |
| polytree-dfs | 0/5 | — | — | — | no solution |
| randomized-bfs | 0/5 | — | — | — | no solution |
| mcts | 0/5 | — | — | — | suboptimal; no solution |
| dd-mcts | 0/5 | — | — | — | suboptimal; no solution |
| randomized-dfs | 0/5 | — | — | — | timeout |
| som | 0/5 | — | — | — | suboptimal; timeout |
| dd-factor-sgd | 0/5 | — | — | — | no solution |
| dd-som | 0/5 | — | — | — | suboptimal; timeout |
| factor-sgd | 0/5 | — | — | — | factorization; timeout |
| factor-bp | 0/5 | — | — | — | factorization; timeout |
| factor-nmf | 0/5 | — | — | — | positional-gram NMF; timeout |
| algorithm-x | 0/5 | — | — | — | no solution |
Method catalog
High-level categories from the research paper — names only, no implementation details.
Optimal (Demaine)
demainedptourexact-bfs
Classical
bfsdfsastaridabdfsalgorithm-x
Irregular / beam
irregular-bfsirregular-astarirregular-idamax-breadth-fs
Randomized
randomized-bfsrandomized-dfs
Structured
polytree-bfspolytree-dfsdp-bfszipper
Parallel (DD)
dd-bfsdd-dfsdd-zipperdd-mctsdd-somdd-factor-sgddd-tdr-zipper
Heuristic / ML
fuzzy-pattern-dbmctssomfactor-sgdfactor-bpfactor-nmf
TDR Zipper
Configurable variant and reset policies
tdr-zipper
Takeaways
- Benchmarks cover 34 methods on 3×3×3 (180 s wall, 500k nodes) and 4×4×4 (300 s wall), five random scrambles each, single-threaded execution.
- The zipper family and BDFS are the reliability winners at these sizes: 5/5 success on both puzzles with optimal or near-optimal move counts where reported.
- TDR zippers match classical zipper quality with modest overhead from tree-depth reset bookkeeping; dd-tdr-zipper parallelizes layer expansion.
- Table-building methods (Demaine, exact-bfs, fuzzy-pattern-db) pay upfront precomputation; on 4×4×4 most never reached a solution before the node cap.
- Heuristic and ML methods (MCTS, SOM, factor-sgd/bp/nmf) explore diverse paths but are exploratory baselines under default budgets on larger cubes.
- Positional-gram NMF (factor-nmf) latency grows sharply with puzzle size; classical misplaced/pattern heuristics scale more predictably on 3×3×3.
- Parallel deferred (DD) variants improve frontier throughput when width is high; on 3×3×3 sequential BDFS is often fastest.