This project is a Rubik's Cube solver written in C. It includes two different solvers, an optimal solver and a Two-Phase solver. The optimal solver uses an Iterative Deepening A* search (IDA*) approach to identify the shortest possible solution to a given state. The Two-Phase solver uses Kociemba's Two-Phase algorithm to quickly identify nearly optimal solutions.
The optimal solver in the Half-Turn metric, averages 55 seconds to solve a random cube state, the average solve time is slightly different in the other move metrics. The Two-Phase solver, is much faster, and will find solutions that are within a few moves of solved. When searching for solutions that are ≤ 20 moves, it can solve around 70 scrambles a second. When searching for solutions that are ≤ 22 moves, it can solve around 500 cubes a second. These times will vary for the other metrics and are hardware dependent, however you can see time estimations for the other metrics in the repository.
As with almost all computer based Rubik's Cube solvers, this program heavily relies on precomputed lookup tables. The main use of these is to provide an admissible heuristic for certain subgoals on the cube. These tables are automatically generated by the solving program on the first run and saved to a file where they can be loaded from in the future. The table generation process can take several hours, so alternatively they can be downloaded below.
More info + Table DownloadsThis program can be configured to use any of four different move metrics. This provides different solutions depending on what counts as a single move. The four move metrics used by this program are HTM (Half-Turn metric), QTM (Quarter-Turn metric), STM (Slice-Turn metric) and ATM (Axial-turn metric). HTM is the most commonly used move metric and is therefore the default, but the program can be switched into any of the others depending on the use case. For more information on different move metrics click here.
The optimal solver was tested using 100 randomly generated cube states. These cubes were then optimally solved in all 4 move metrics. Detailed results from these tests can be found in the GitHub repository. If you want to repeat the same test, you can download the test cases below.
The optimal solutions generated for the Half-Turn Metric and Quarter-Turn Metric were also verified by generating optimal solutions to the same set of scrambles, using Herbert Kociemba's Cube Explorer.
The average solve times and solution lengths were as follows:
| Metric | Average solution length | Average solve time |
|---|---|---|
| HTM | 17.74 moves | 55.44 seconds |
| QTM | 20.55 moves | 76.05 seconds |
| STM | 16.11 moves | 89.08 seconds |
| ATM | 13.81 moves | 47.36 seconds |