Rubik's Cube Solver

A high-performance C++ implementation of various algorithms to solve the Rubik's Cube, featuring multiple solving strategies and an efficient bitboard representation.

Table of Contents

• Features
• Architecture Overview
• Installation
• Usage
• Code Structure
• Implementation Details
• Algorithms
• Performance
• Contributing

Features

• Multiple Cube Representations: 3D array, 1D array, and bitboard implementations
• Various Solving Algorithms: DFS, BFS, IDDFS, and IDA* with pattern database
• Pattern Database: Pre-computed heuristics for efficient solving
• Interactive CLI: User-friendly menu system
• Performance Metrics: Timing information for each solve
• Cross-platform: Works on macOS, Linux, and Windows

Architecture Overview

rubiks-cube-solver/
├── Model/                    # Cube representations
│   ├── RubiksCube.h         # Abstract base class
│   ├── RubiksCube.cpp       # Common functionality
│   ├── RubiksCube3dArray.cpp
│   ├── RubiksCube1dArray.cpp
│   └── RubiksCubeBitboard.cpp  # Most efficient representation
├── Solver/                   # Solving algorithms
│   ├── DFSSolver.h          # Depth-First Search
│   ├── BFSSolver.h          # Breadth-First Search
│   ├── IDDFSSolver.h        # Iterative Deepening DFS
│   └── IDAstarSolver.h      # IDA* with pattern database
├── PatternDatabases/         # Heuristic databases
│   ├── PatternDatabase.h/cpp
│   ├── CornerPatternDatabase.h/cpp
│   ├── CornerDBMaker.h/cpp
│   └── NibbleArray.h/cpp    # Memory-efficient storage
├── Databases/                # Pre-computed databases
│   └── cornerDepth5V1.txt   # Corner pattern database
├── main.cpp                  # Interactive program
└── test_solver.cpp          # Test suite

Installation

Prerequisites

• C++ compiler with C++14 support (g++, clang++)
• CMake (optional)
• Git

Building on macOS/Linux

# Clone the repository
git clone https://github.com/aryan1xDD/Rubiks-Cube-Solver.git
cd Rubiks-Cube-Solver

# Compile the main program
g++ -std=c++14 -O2 -o rubiks_solver main.cpp Model/RubiksCube.cpp \
    PatternDatabases/NibbleArray.cpp PatternDatabases/PatternDatabase.cpp \
    PatternDatabases/CornerPatternDatabase.cpp PatternDatabases/CornerDBMaker.cpp \
    PatternDatabases/math.cpp -I.

# Compile the test program
g++ -std=c++14 -O2 -o test_solver test_solver.cpp Model/RubiksCube.cpp \
    PatternDatabases/NibbleArray.cpp PatternDatabases/PatternDatabase.cpp \
    PatternDatabases/CornerPatternDatabase.cpp PatternDatabases/CornerDBMaker.cpp \
    PatternDatabases/math.cpp -I.

Building with CMake

mkdir build
cd build
cmake ..
make

Usage

Interactive Mode

Run the main program:

./rubiks_solver

Menu options:

1. Solve a randomly shuffled cube - Automatically selects the best algorithm
2. Input custom cube state - (Not yet implemented)
3. Test different solvers - Compare algorithm performance
4. Create/Update Pattern Database - Generate deeper heuristic databases
5. Exit

Test Mode

Run the test suite:

./test_solver

This runs automated tests with different shuffle depths and algorithms.

Code Structure

Model Layer

RubiksCube Base Class (Model/RubiksCube.h)

Abstract base class defining the interface for all cube representations:

class RubiksCube {
public:
    enum class FACE { UP, LEFT, FRONT, RIGHT, BACK, DOWN };
    enum class COLOR { WHITE, GREEN, RED, BLUE, ORANGE, YELLOW };
    enum class MOVE { L, LPRIME, L2, R, RPRIME, R2, ... };
    
    virtual COLOR getColor(FACE face, unsigned row, unsigned col) const = 0;
    virtual bool isSolved() const = 0;
    virtual RubiksCube& move(MOVE ind) = 0;
    // ... rotation methods
};

RubiksCubeBitboard (Model/RubiksCubeBitboard.cpp)

Most efficient representation using 64-bit integers:

• Each face is represented by a 64-bit integer
• 8 bits per facelet (supporting up to 256 colors)
• Total memory: 6 × 8 bytes = 48 bytes per cube
• Bitwise operations for fast rotations

class RubiksCubeBitboard : public RubiksCube {
private:
    uint64_t bitboard[6];  // One 64-bit int per face
    // Efficient bit manipulation for moves
};

Solver Layer

DFS Solver (Solver/DFSSolver.h)

• Depth-First Search with depth limit
• Best for shallow shuffles (≤8 moves)
• Memory efficient but not optimal

BFS Solver (Solver/BFSSolver.h)

• Breadth-First Search
• Guarantees optimal solution
• Memory intensive for deep shuffles

IDDFS Solver (Solver/IDDFSSolver.h)

• Iterative Deepening DFS
• Combines benefits of DFS and BFS
• Optimal and memory efficient

IDA* Solver (Solver/IDAstarSolver.h)

• Iterative Deepening A* with pattern database
• Uses corner pattern database for heuristic
• Most efficient for moderate shuffles (5-13 moves)

Pattern Database Layer

Corner Pattern Database

• Pre-computes minimum moves for all corner configurations
• 8 corners × 3 orientations = 88,179,840 states
• Stored efficiently using nibble arrays (4 bits per entry)

Database Generation

CornerDBMaker dbMaker("cornerDepth8.txt", 0xFF);
dbMaker.bfsAndStore();  // Generates database using BFS

Implementation Details

Move Notation

• Basic moves: F, B, U, D, L, R (Front, Back, Up, Down, Left, Right)
• Prime moves: F', B', U', D', L', R' (Counter-clockwise)
• Double moves: F2, B2, U2, D2, L2, R2 (180-degree turns)

Cube State Representation

The cube is displayed in an unfolded format:

       U U U
       U U U
       U U U

L L L  F F F  R R R  B B B
L L L  F F F  R R R  B B B
L L L  F F F  R R R  B B B

       D D D
       D D D
       D D D

Algorithm Selection Strategy

The main program automatically selects the best algorithm:

• Shuffles ≤10 moves: IDA* with pattern database
• Shuffles >10 moves: BFS for guaranteed optimal solution

Memory Optimization

• Bitboard representation: 48 bytes per cube state
• Nibble arrays: 4 bits per database entry
• Hash tables: Efficient duplicate detection

Algorithms

1. Depth-First Search (DFS)

template<typename T, typename H>
class DFSSolver {
    vector<RubiksCube::MOVE> solve() {
        // Recursive DFS with depth limit
        // Returns first solution found
    }
};

2. Breadth-First Search (BFS)

template<typename T, typename H>
class BFSSolver {
    vector<RubiksCube::MOVE> solve() {
        // Level-by-level exploration
        // Guarantees shortest solution
    }
};

3. IDA* with Pattern Database

template<typename T, typename H>
class IDAstarSolver {
    vector<RubiksCube::MOVE> solve() {
        // Iterative deepening with heuristic
        // f(n) = g(n) + h(n)
        // h(n) from pattern database
    }
};

Performance

Typical solving times on modern hardware:

Shuffle Depth	Algorithm	Time	Optimal
5 moves	IDA*	~50ms	Yes
10 moves	IDA*	~200ms	Yes
12 moves	BFS	~2-3s	Yes
15 moves	BFS	~10-30s	Yes

Optimization Techniques

1. Bitboard representation for fast state manipulation
2. Pattern databases for admissible heuristics
3. Move pruning to avoid redundant sequences
4. Hash tables for duplicate detection
5. Compiler optimizations (-O2 flag)

Advanced Usage

Creating Deeper Pattern Databases

// In main program, option 4
// Creates a depth-8 database (takes several minutes)
CornerDBMaker dbMaker("cornerDepth8.txt", 0xFF);
dbMaker.bfsAndStore();

Custom Cube Input (Future Feature)

The framework supports custom cube states:

RubiksCubeBitboard cube;
// Set custom configuration
cube.setColor(FACE::FRONT, 0, 0, COLOR::RED);
// ... set all facelets

Contributing

1. Fork the repository
2. Create your feature branch (git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add amazing feature')
4. Push to the branch (git push origin feature/amazing-feature)
5. Open a Pull Request

Areas for Contribution

• Implement custom cube input
• Add more pattern databases (edge patterns)
• Implement Kociemba's algorithm
• Add GUI interface
• Optimize for even deeper shuffles
• Add more cube representations (e.g., permutation-based)

Technical Details

Bitboard Move Implementation

Example of the UP face rotation:

RubiksCube& u() {
    rotateFace(0);  // Rotate UP face clockwise
    // Cycle edge pieces between adjacent faces
    uint64_t temp = bitboard[FRONT] & TOP_ROW_MASK;
    bitboard[FRONT] = (bitboard[FRONT] & ~TOP_ROW_MASK) | 
                      (bitboard[RIGHT] & TOP_ROW_MASK);
    // ... continue cycling
    return *this;
}

Pattern Database Structure

class CornerPatternDatabase : public PatternDatabase {
    NibbleArray database;  // 4 bits per entry
    
    uint32_t getDatabaseIndex(const RubiksCubeBitboard& cube) {
        // Convert corner configuration to unique index
        // 8 corners, 3 orientations each
    }
};

Hash Function for Cube States

struct HashBitboard {
    size_t operator()(const RubiksCubeBitboard& cube) const {
        uint64_t hash = cube.bitboard[0];
        for (int i = 1; i < 6; i++) 
            hash ^= cube.bitboard[i];
        return hash;
    }
};

License

This project is open source and available under the MIT License.

Acknowledgments

• Inspired by various Rubik's Cube solving algorithms
• Pattern database concept from Korf's research
• Bitboard representation adapted from chess engines

Contact

For questions or suggestions, please open an issue on GitHub.