How shubhampatil11/rubiks-cube-solver works
1. This is a C++ Rubik’s Cube solving project built with CMake. The codebase is organized around three main concerns: cube state modeling, search-based solving, and pattern-database support for heuristic lookup.
2. The entry point is main.cpp, which likely wires together a chosen cube representation, solver strategy, and optional database loading/generation. The repository does not show a UI or service layer; it is primarily an algorithmic/CLI-style application.
3. The Model/ subtree defines the cube domain model. RubiksCube.h/.cpp appears to be the core abstraction, while RubiksCube1dArray.cpp, RubiksCube3dArray.cpp, and RubiksCubeBitboard.cpp suggest multiple internal state representations for the same cube logic. This is an important architectural boundary: the solver can operate against different state encodings depending on performance tradeoffs.
4. Model/PatternDatabase/PatternDatabase.h indicates a model-facing interface for heuristic databases. This sits at the boundary between the cube state layer and the solver layer, allowing search algorithms to ask for estimated distances or lookup values rather than directly reasoning about cube geometry.
5. The Solver/ directory contains several search strategies: BFSSolver, DFSSolver, IDAstarSolver, and IDDFSSolver. These are distinct algorithm modules rather than one monolithic solver, implying the application can choose between exhaustive search, depth-first search, iterative deepening variants, and heuristic-guided A* style solving.
6. The architecture likely flows from main.cpp into one of these solver implementations, which then manipulates a RubiksCube instance and optionally consults a pattern database. The solver layer is therefore the orchestration point, while the model layer owns cube state transitions and legality of moves.
7. The PatternDatabases/ directory is a separate subsystem for building and using heuristic tables. It includes CornerDBMaker.cpp/.h, CornerPatternDatabase.cpp/.h, PatternDatabase.cpp/.h, PermutationIndexer.h, NibbleArray.cpp/.h, and small math helpers. This suggests a compact encoded database structure, likely optimized for storing heuristic distances for cube corner permutations/orientations.
8. CornerDBMaker implies offline or precomputation-style database generation, while CornerPatternDatabase and PatternDatabase are the runtime lookup components. The presence of PermutationIndexer and NibbleArray indicates the database is indexed combinatorially and stored densely to reduce memory footprint.
9. The Databases/ folder contains at least one concrete artifact, cornerDepth5V1.txt. This is likely a generated heuristic table or precomputed state-depth dataset consumed by the pattern-database code, which means the repository separates database generation from database usage.
10. The project has a clear layering boundary: model code knows cube state and moves, pattern-database code knows compact heuristic indexing/storage, and solver code knows search strategy. That separation is important for an architecture diagram because the solver depends on both lower layers, but those lower layers do not depend on the solver.
11. The multiple cube representations suggest performance experimentation is a key design goal. An architecture diagram should show these as alternative implementations behind a common cube interface or common behavior set, rather than as separate applications.
12. Overall, the system is best understood as an offline/algorithmic solver pipeline: build or load a heuristic database, instantiate a cube state in a chosen representation, run a selected search algorithm, and produce a solved move sequence. There are no obvious external services, persistence systems, or network boundaries beyond local file-based database artifacts.
Main entry points: RubiksCube.h Rubik's Cube · main.cpp main.cpp · CornerDBMaker.h DB Maker · CornerPatternDatabase.h Corner PDB
Components 17
Application
CLI entry and top-level wiring.
- main.cpp · Program entry point that selects cube state, solver, and database use.
main.cpp
Cube Model
Cube state abstraction and alternative internal representations.
- Rubik's Cube · Core cube abstraction shared across the solver and representations.
Model/RubiksCube.h - 1D Array · One concrete cube representation optimized around a flat array layout.
Model/RubiksCube1dArray.cpp - 3D Array · One concrete cube representation using a 3D array layout.
Model/RubiksCube3dArray.cpp - Bitboard · Compact bit-level cube representation for performance experimentation.
Model/RubiksCubeBitboard.cpp - Model PDB · Model-facing pattern-database abstraction used by solving code.
Model/PatternDatabase/PatternDatabase.h
Search Solvers
Alternative search strategies for solving the cube.
- BFS · Breadth-first search solver implementation.
Solver/BFSSolver.h - DFS · Depth-first search solver implementation.
Solver/DFSSolver.h - IDA* · Iterative deepening A* solver using heuristic guidance.
Solver/IDAstarSolver.h - IDDFS · Iterative deepening depth-first solver implementation.
Solver/IDDFSSolver.h
Pattern Databases
Heuristic database interfaces, encodings, and builders.
- PDB Base · Shared pattern-database infrastructure and storage logic.
PatternDatabases/PatternDatabase.h - Corner PDB · Runtime corner-pattern database used for heuristic lookup.
PatternDatabases/CornerPatternDatabase.h - DB Maker · Generates pattern-database tables from cube-state exploration.
PatternDatabases/CornerDBMaker.h - Indexer · Maps permutations or orientations to dense database indices.
PatternDatabases/PermutationIndexer.h - Nibble Array · Compact packed array used to store small database values densely.
PatternDatabases/NibbleArray.h - Math Helpers · Small utility math routines for database indexing and generation.
PatternDatabases/math.h
Database Artifact
Generated heuristic data stored on disk.
- cornerDepth5V1.txt · Generated depth table consumed by pattern-database code.
Databases/cornerDepth5V1.txt
Connections 24
- main.cpp → Rubik's Cube: creates · Entry point instantiates the cube model used by the chosen solver.
- main.cpp → BFS: selects · Main can dispatch to the BFS solver.
- main.cpp → DFS: selects · Main can dispatch to the DFS solver.
- main.cpp → IDA*: selects · Main can dispatch to the heuristic IDA* solver.
- main.cpp → IDDFS: selects · Main can dispatch to the IDDFS solver.
- main.cpp → Corner PDB: loads · Main can load a heuristic database for solving.
- main.cpp → DB Maker: builds · Main can invoke database generation tooling.
- Rubik's Cube → 1D Array: impl · One concrete cube representation behind the common cube abstraction.
- Rubik's Cube → 3D Array: impl · One concrete cube representation behind the common cube abstraction.
- Rubik's Cube → Bitboard: impl · One concrete cube representation behind the common cube abstraction.
- BFS → Rubik's Cube: searches · Breadth-first search expands cube states.
- DFS → Rubik's Cube: searches · Depth-first search expands cube states.
- IDA* → Rubik's Cube: searches · IDA* explores cube states while evaluating heuristic cost.
- IDDFS → Rubik's Cube: searches · IDDFS explores cube states with iterative deepening.
- IDA* → Model PDB: heuristic · Heuristic solver queries the model-facing pattern database interface.
- Corner PDB → PDB Base: extends · Corner database builds on shared pattern-database infrastructure.
- Corner PDB → Model PDB: adapts · Runtime database exposes the model-level heuristic interface.
- DB Maker → Corner PDB: generates · Offline builder produces the concrete corner database.
- DB Maker → Indexer: indexes · Database generation relies on combinatorial indexing.
- DB Maker → Nibble Array: stores · Generated values are packed into compact storage.
- DB Maker → Math Helpers: uses · Builder uses helper math routines for table construction.
- Corner PDB → cornerDepth5V1.txt: reads · Runtime database loads generated depth data from disk.
- PDB Base → Indexer: uses · Shared database logic depends on combinatorial indexing.
- PDB Base → Nibble Array: uses · Shared database logic uses packed storage.