A Rubik's cube solver and generator in Rust, built as a backend for cube explorers. The name is a play on cubicle: a small room for working on cubes.
Today the 2×2×2 is solved optimally, the 3×3×3 is solved with an optimized implementation of the two-phase algorithm (derived from min2phase by Chen Shuang), the 4×4×4 is solved by a port of the three-phase reduction of TPR-4x4x4-Solver (about 47 moves, 12 MB of tables built in a fraction of a second), and the 5×5×5 is solved by a port of the five-phase reduction of cube555 (about 73 moves, 237 MB of cached tables). The cubacle::puzzle module describes cubes of every size from 2×2×2 to 7×7×7 behind one Solver trait; engines for the other sizes are being added. ARCHITECTURE.md explains how the crate is laid out and which module may depend on which.
cubacle stands on the work of Herbert Kociemba, who devised the two-phase algorithm and the Cube Explorer: thank you for this great work. The 6x6x6 and 7x7x7 engines follow Daniel Walton's staged reduction method. See Credits for everyone else.
Licensed under AGPL-3.0-or-later; see NOTICE.md for the MIT-licensed origin of the 3×3×3 core.
A solver accepts a cube as typed facelets and returns a typed move sequence. The crate also generates random states and scrambles, parses scrambles and applies them to a cube.
Made a mistake following a solution? Do not try to fix it by hand. Rescan the cube and run cubacle solve --now, with --at-move N for the move you stopped at (docs/cli.md).
cubacle solve A4ib8aejxj4Y # Orbit64 token
cubacle solve FUFUUFFFF UUUURRURU RRRFFRRFR BDBBDDBBB DLDDLLDDD LBLBBLLLL
cubacle solve GWGWWGGGG WWWWRRWRW RRRGGRRGR BYBBYYBBB YOYYOOYYY OBOBBOOOO
cubacle solve --scramble "R U R' U'" --max-moves 20 --budget-ms 500 --verbose
cubacle solve -s "R U R' U'" --now FACELETS --at-move 3 # after a mistake in a printed solution
cubacle convert --scheme jp WWWW RRRR GGGG BBBB OOOO YYYY
cubacle random | cubacle solve -
cubacle scramble -n 25
cubacle facelets "R U R' U'"
A scramble is standard move notation with whitespace between the moves (R U R' U', F2, B'). SiGN spellings (r, 3r) and SSE spellings (TR, T3R, MR, N2-4R) are read too and --notation sign or --notation sse writes them; see docs/cli.md. The aliases R1 (R), R3 (R'), and R2' or R'2 (R2) are accepted too, as in the WCA export form; unseparated runs such as RUR' and a lone - are rejected.
A cube may be written as an Orbit64 state token, as URFDLB facelets, or as sticker colors W R G Y O B. Facelets and colors may be compact or spaced, in any grouping, and need no quoting. Colors are read from the fixed centers of an odd cube, so western and Japanese cubes need no flag. A cube without centers (the 2×2×2) uses --scheme:
| Scheme | U R F D L B | Opposite pairs |
|---|---|---|
boy (default) |
W R G Y O B | white–yellow, green–blue, red–orange |
jp |
W R G B O Y | white–blue, green–yellow, red–orange |
Any six letters in URFDLB order also work, e.g. --scheme WRGYOB.
solve handles every size from the 2×2×2 to the 7×7×7. It prints the solution, and for every size but the 2×2×2 checks by replay that it solves the cube. On a 3×3×3 it makes 3000 probes for a shorter answer (--fast returns the first one, --probes, --improve, -m and -b set their own limits). It exits with a non-zero status when the state is impossible, the limit is too tight or the time budget runs out. Orbit64 tokens decode and encode for every size from 2×2×2 to 7×7×7 (convert --to token writes one; solve reads them too). --size 4 or --size 5 picks the cube for --scramble, scramble, random and facelets; a 4×4×4 solution has 47.5 moves on average (including the final whole-cube rotation) and a 5×5×5 solution 73, see docs/engines/_index.md and docs/performance.md.
The 2×2×2 solver (PocketSolver) keeps one corner fixed and searches an exact distance table of all 3,674,160 states, so its solutions are optimal in the half-turn metric (U, R and F turns by 90° or 180°). The table is built on first use in well under a second in a release build. A cube that is solved in any orientation needs no moves. A solve with a ready table takes microseconds and always meets --budget-ms; the first solve in a process includes the one-off table build, which a budget cannot interrupt and which counts against it. Solver::prepare() does the build ahead of time.
cubacle moves R "U'" Rw2 --icons draws moves as small pictures, move icons ("minicubes") (Kitty graphics on a capable terminal, text elsewhere, or SVG with --format svg --out FILE), and cubacle solve --icons shows each move of a solution that way. See docs/icons.md.
use cubacle::engines::three::Min2PhaseSolver;
use cubacle::puzzle::{Facelets, PuzzleKind, SolveOptions, Solver};
let scramble = "R U R' U'".parse().expect("valid scramble");
let cube = Facelets::solved(PuzzleKind::Cube3).apply(&scramble).expect("fits a 3x3");
let solver = Min2PhaseSolver::shared();
let result = solver.solve(&cube, &SolveOptions::default().with_max_moves(20));
let solution = result.solution().expect("solvable");
assert!(cube.apply(solution).expect("fits").is_solved());Failures are values, not strings: result.outcome is Err(Failure::InvalidInput) for an impossible cube, Err(Failure::BudgetExhausted) when the time budget ran out and Err(Failure::Exhausted) when no solution exists within the move limit; result.message carries a sentence for people.
Facelets::parse reads, and Facelets prints, stickers in this order:
U1U2...U9R1R2...R9F1...F9D1...D9L1...L9B1...B9
The solved 3×3×3 is:
UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB
A limit of 20 or 21 moves is recommended for the 3×3×3 (SolveOptions::with_max_moves; the default is 21).
puzzle:PuzzleKind,Facelets(withapply(&MoveSequence)),MoveandMoveSequence(parse withstr::parse), theSolvertrait,SolveOptions,SolveResultandFailure.notation:parse_cube(Orbit64 tokens, facelets and colors),parse_expression(move expressions with(...)*N,M E Sandx y z),ColorScheme(withpaint), theorbit64codec.render:icon(&state, &action, &style)draws a move as SVG, RGBA pixels, Kitty graphics or text; see the move icons page.generate:random_state(kind)(a uniform 2×2×2, 3×3×3 or 5×5×5 state) andscramble(kind, length).engines::three::Min2PhaseSolver: the 3×3×3Solver, plussolve_pattern(&from, &to, &options): moves that transform one cube state into another.solve_batch(&cubes, &options): independent cubes solved concurrently, results in input order.solve_parallel,solve_parallel_with_minimum_timeandsolve_pattern_parallel: experimental six-orientation single-cube searches.solve_with_minimum_time(&cube, &options, minimum): keep improving the solution until the minimum search time, within the hard maximum set byoptions.time_budget.
engines::two::PocketSolver: the optimal 2×2×2Solver.
A Min2PhaseSolver owns its move and pruning tables, built on first use or by prepare(). Clones share them: create one solver at startup and pass clones to whoever needs one. Min2PhaseSolver::new() starts a table set of its own, and Min2PhaseSolver::shared() returns a process-wide default for code with nothing to inject.
A time budget that expires after a solution was found still returns that solution; only a deadline reached with no solution is Failure::BudgetExhausted.
Use solve_pattern when the desired result is an arbitrary valid cube state rather than the solved cube:
use cubacle::engines::three::Min2PhaseSolver;
use cubacle::puzzle::{Facelets, PuzzleKind, SolveOptions};
let solved = Facelets::solved(PuzzleKind::Cube3);
let from = solved.apply(&"R U R' U'".parse().unwrap()).unwrap();
let to = solved.apply(&"F2 D L2".parse().unwrap()).unwrap();
let options = SolveOptions::default().with_max_moves(20);
let result = Min2PhaseSolver::shared().solve_pattern(&from, &to, &options);
assert_eq!(from.apply(result.solution().unwrap()).unwrap(), to);Min2PhaseSolver::solve_batch reuses a process-wide worker pool, avoiding per-solve thread creation. Set CUBACLE_THREADS to a positive worker count before its first use to override the default of available_parallelism(). The pool has no shutdown operation and lives for the process lifetime. It is optimized for many independent cubes, not lower latency for a single cube.
CUBACLE_THREADS=4 cargo run --release --example bulk_compare -- \
examples/scrambles.csv examples/scramble-report.csv 4 - 100 100The solve_parallel* methods split one solve across the six URF orientations, complete every orientation search, and select the first valid result in fixed URF order. The orientation searches share a best-length bound, so which valid solution comes back can vary between runs; it is always a solution within the move limit. They use the same pool, so set CUBACLE_THREADS before their first use. Wall-clock budgets still have the same timing sensitivity as the serial budget APIs. This is an experimental latency mode: it can perform more total IDA* work than serial search. Validate it on the target machine before adopting it.
examples/bulk_compare.rs compares the solutions in a scramble CSV with solutions generated by this crate at a 19-move limit and a 100 ms minimum and maximum search time per cube. After finding an initial solution, it continues searching for a shorter one until the minimum is reached, and never exceeds the hard maximum. The input CSV is not part of the repository (examples/*.csv is ignored by git); supply your own with the header competitionId,evntId,roundTypeId,group,isExtra,number,scramble,moves,solution.
RUSTFLAGS='-C target-cpu=native' cargo run --release --example bulk_compare -- \
examples/scrambles.csv examples/scramble-report-100ms.csvThe command uses one worker per available logical CPU by default and shows progress, elapsed time, and an ETA. Its live progress line also reports completed classifications, timeouts, accumulated phase-two probes, and average solve time. To choose a worker count, row limit, minimum search time, and maximum search time in milliseconds, pass optional third through sixth arguments:
cargo run --release --example bulk_compare -- \
examples/scrambles.csv examples/scramble-report-200-500ms.csv 12 100 200 500The command prints a summary and writes every row to the report CSV. The summary reports actual worker count, wall-clock batch duration, and the sum of per-job solve times. Each row includes the classification, expected and actual length, phase-two probes, elapsed microseconds, and timed_out status. A timed-out row has no solution before the hard limit; a row with a solution is returned after the minimum search time or the hard maximum, whichever comes first. Reference moves using 1 and 3 suffixes are normalized to the solver's bare-turn and apostrophe notation before comparison.
The summary distinguishes an exact move sequence, any same-length solution (including exact sequences), shorter solutions, longer solutions, errors, and timeouts. A timeout is Failure::BudgetExhausted: no solution was found before the hard limit. It is distinct from ordinary input errors.
To retry only longer rows from an existing report, use - for no row limit and pass longer after the minimum and maximum search times:
RUSTFLAGS='-C target-cpu=native' cargo run --release --example bulk_compare -- \
examples/scramble-report-100ms.csv examples/scramble-report-longer-200ms.csv \
12 - 200 500 longerUnbounded serial solves are deterministic for a fixed cube, move limit, solver version, and build; parallel solves are not guaranteed to be. Time-bounded solves are intentionally not deterministic: CPU scheduling and the point at which the search observes the time limit can affect the best result found.
target-cpu=native enables CPU features available on the host, including Apple M2 systems. Do not use that flag for binaries intended to run on other CPU models.
The validating benchmark warms the solver tables, solves a fixed corpus repeatedly, and checks every returned sequence by applying it to the cube. It reports average, median, and p95 solver time and phase-two probes per second. The argument is the number of passes over the corpus:
RUSTFLAGS='-C target-cpu=native' cargo run --release --example benchmark -- 100To benchmark the experimental single-cube parallel path with the same fixed corpus, add --parallel; compare its p50 and p95 against a serial run on the same warm machine:
RUSTFLAGS='-C target-cpu=native' cargo run --release --example benchmark -- 200 --parallelFor a parallel throughput comparison, run the same bulk sample with one worker and then with your desired worker count. The report and summary make probe totals and result classifications directly comparable.
Run the project quality checks with:
cargo fmt --check
cargo clippy --workspace --all-targets -- -D warnings
cargo test --workspace --releasetests/golden_test.rs replays tests/fixtures/golden.txt, a record of the exact solutions and probe counts of both engines for 554 fixed cubes; a change that alters search behavior fails it. tests/architecture_test.rs enforces the module dependency rules.
crates/server holds cubacle-server, a stateless REST backend (solve, convert, scramble, random) for the 2x2x2, 3x3x3, 4x4x4 and 5x5x5. See crates/server/README.md.
crates/wasm holds cubacle-wasm, a browser WebAssembly facade for the 2x2x2 and 3x3x3 and the G1 size/time/memory measurement. See docs/wasm.md.