Rubik's Cube Solver

Projects | 2023 | Links: Link

The following project involves the development of a code that solves the 3$\times$3$\times$3 Rubik’s Cube using the A* algorithm. This implementation is built on the PyRubikSim simulator from Miguel Hernando’s repository and uses visualization utilities from David Hogg’s MagicCube. The project serves as a testbed for discrete planning techniques, allowing for the exploration of advanced problem-solving strategies.

Functionality and Features

The program is designed to solve a Rubik’s Cube from a given number of random initial movements. It features:

• State Rendering: The ability to generate images of the cube at different stages of disassembly.
• 3D Interactive Animation: A 3D visualization that displays the cube’s assembly and disassembly process, enhancing user interaction and understanding.
• State Codification: The cube’s state is encoded following the conventions laid out in Miguel Hernando’s repository.
• Heuristic for A*: The heuristic used in the A* algorithm is based on the number of moves required to correctly position and orient all cubies (edges and corners) on the cube.

Approach and Algorithm Selection

Given the complexity of the Rubik’s Cube, with $4.32 \cdot 10^{19}$ possible states, brute-force methods are impractical. The A* algorithm was selected for its heuristic-based search, enabling a more efficient solution process. Although Iterative Deepening A* (IDA*) offers memory advantages, A* was chosen to explore its limitations and performance in solving the cube.

Action Space and Cost Function

The program’s action space consists of rotations along three axes and two layers, yielding a reasonable set of 18 possible actions from any given state. The cost function $f(x)$ for each state is calculated as the sum of the path cost $g(x)$ and the heuristic $h(x)$, where $h(x)$ estimates the number of moves needed to reach the solution. The heuristic considers the minimal number of moves required to correctly position and orient each cubie.

Results and Optimizations

Through experimentation, the best performance was achieved using a heuristic divisor of 5. The solver performs efficiently with cube configurations involving up to six random moves but shows limitations with more complex scenarios, indicating the need for enhanced heuristics or alternative planning algorithms.

Conclusion and Future Work

The A* algorithm effectively solves the Rubik’s Cube for low-complexity configurations. For more challenging setups (seven or more initial moves), further improvements are necessary. Future directions could include testing different heuristics, optimizing memory usage, comparing the performance with systematic solving techniques (like CFOP), or implementing the algorithm in C++ for faster execution.

Code