Rubik's Cube Solver
A high-performance C++ cube solver with three interchangeable state models and four search strategies, culminating in Korf's IDA* search driven by a 4-bit packed corner pattern database.
Timeline
Oct — Nov 2025
Role
Solo — data structures, search algorithms, heuristic database
Status
CompletedTechnology Stack
Key Challenges
- Branching factor of 18 causes unpruned searches to explode in memory beyond shallow depths
- Creating an admissible heuristic database that fits entirely in cache-friendly memory
- Optimizing state rotations using bitwise operations
Key Learnings
- Templating search algorithms over state models allows seamless benchmarking across representations
- In-place state mutation with inverse moves eliminates copy overhead during tree traversal
- A 4-bit nibble array halves heuristic database memory footprint
Overview
A standard 3×3 Rubik's Cube has approximately 4.3 × 10¹⁹ reachable states. With 18 legal face turns per position, brute-force search quickly exhausts system memory.
This project explores efficient state representations in modern C++ and implements Iterative Deepening A* (IDA*) with an admissible pattern database to solve scrambles in seconds.
Core State Representations
An abstract RubiksCube interface decouples the game logic from underlying memory representations:
| Model | Representation | Characteristics |
|---|---|---|
RubiksCube3dArray | [6][3][3] face matrix | Intuitive and human-readable, ideal for debugging |
RubiksCube1dArray | Flat 54-element array | Contiguous memory with reduced cache misses |
RubiksCubeBitboard | Six 64-bit integers (uint64_t) | State rotations computed via bitwise shifts and masks |
Search Strategies
Solvers are templated over the cube representation (template<typename T, typename H> class IDAstarSolver), allowing the same search logic to run across any model:
- Breadth-First Search (BFS): Finds optimal shortest paths for scrambles up to ~6 moves before memory limits.
- Depth-First Search (DFS): Memory-efficient bounded depth exploration; yields non-optimal paths.
- Iterative Deepening DFS (IDDFS): Guarantees shortest path while maintaining low linear memory usage.
- IDA* (Iterative Deepening A*): Prunes subtrees using a cost function
f(n) = g(n) + h(n)powered by an admissible pattern database.
Corner Pattern Database & Bit Packing
To guide IDA* efficiently without exploring irrelevant branches, an admissible heuristic estimates remaining distance by solving only the 8 corner cubies:
- Breadth-First Generation: Precomputed via BFS from the solved state to record optimal corner solve depths.
- 4-Bit Nibble Array: Since corner distances never exceed 11 moves, each entry is packed into a 4-bit nibble (2 entries per byte), reducing the in-memory database footprint by 50%.
- Permutation Indexing: Maps corner configurations directly into dense array offsets without dynamic hash map lookups.
Performance & Build
- 8-move scrambles: Solved in under 3 seconds using uninformed search.
- 13-move scrambles: Solved in under 10 seconds using IDA* with bitboards.
mkdir build && cd build
cmake ..
make
./RubiksCubeSolverTech Stack Summary
- Language: C++17 / C++20
- Build System: CMake, Make
- Techniques: Bit Manipulation (Bitboards), Heuristic Search (IDA*), Pattern Databases, Data Packing