Rubik's Cube Solver

A C++17 implementation of a Rubik's Cube solver using both uninformed (IDDFS) and informed (A*, IDA*) search strategies.

Project Structure

rubiks-cube-solver/
├── include/
│   ├── Cube.h          — Cube state, 18-move set, move parser
│   ├── Heuristic.h     — Abstract heuristic + Manhattan/Misplaced implementations
│   └── Solver.h        — IDDFS, A*, and IDA* solver interfaces
├── src/
│   ├── Cube.cpp        — Full cube mechanics (face rotations, edge cycles)
│   ├── Heuristic.cpp   — Heuristic implementations
│   ├── Solver.cpp      — All three search algorithms
│   └── main.cpp        — CLI driver with file I/O
└── CMakeLists.txt

Algorithms

IDDFS (Iterative-Deepening DFS)

• Runs DFS with increasing depth limits (1, 2, 3, …) until a solution is found.
• Optimal: always finds the shortest solution in moves.
• Space: O(d) — only the current path is stored.
• Time: O(b^d) where b=18 (branching factor) and d=solution depth.
• Best for: verifying correctness; shallow scrambles (≤6 moves).

A* Search

• Priority queue ordered by f(n) = g(n) + h(n).
• g(n) = moves made so far; h(n) = admissible heuristic estimate.
• Optimal with an admissible heuristic (guaranteed).
• Space: O(b^d) — stores all frontier nodes in memory.
• Best for: moderate scrambles where memory is not a constraint.

IDA* (Iterative-Deepening A*)

• Combines IDDFS with a heuristic threshold instead of pure depth.
• Cuts branches when g(n) + h(n) exceeds the current threshold.
• Optimal and memory-efficient (O(d) space like IDDFS).
• Best for: deep scrambles; the industry standard for Rubik's Cube.

Heuristic: Manhattan Distance

The ManhattanHeuristic counts stickers not on their home face and divides by 8 (the maximum stickers one move can fix). This is admissible — it never overestimates — so IDA* remains optimal.

Build

mkdir build && cd build
cmake ..
make -j$(nproc)

Usage

# Run built-in demo (solves R U R' U' and verifies)
./cube_solver --demo

# Scramble and solve with IDA* (default)
./cube_solver --scramble "R U F' D2 L"

# Use plain IDDFS
./cube_solver --algo iddfs --scramble "R U R' U'"

# Use A*
./cube_solver --algo astar --scramble "F R U"

# Load cube from file, write solution
./cube_solver --input state.txt --output solution.txt

# Increase search depth
./cube_solver --scramble "R U R' U'" --max-depth 25

Input File Format

54 integers (0–5), space or newline separated, representing all six faces in order U, L, F, R, B, D, each row-major:

Color encoding:
  0 = White  (U face center)
  1 = Orange (L face center)
  2 = Green  (F face center)
  3 = Red    (R face center)
  4 = Blue   (B face center)
  5 = Yellow (D face center)

OOP Design

• Cube encapsulates state and move logic. Copying a Cube is cheap (54-byte array).
• Heuristic is a pure abstract interface — solvers depend on the interface, not the implementation.
• IDDFSSolver, AStarSolver, IDAStarSolver are independent classes with a uniform solve(Cube) → SolveResult API.
• SolveResult carries moves, node count, depth, and elapsed time for easy comparison.