Home

Solving a Rubik's Cube Using Simulated Annealing

Optimization of problems without governing equations

Authors: Quinton Uradomo, William Wang

Complexity of a 3x3x3 Rubik's Cube

43,252,003,274,489,856,000 possible permutations [3]
Minimum of 20 moves to solve any permutation [3]
Pieces can be in the correct position but wrong orientation
Discrete problem without gradient

Motivating Study

The study this project is based on is written by Shahram Saeidi Solving a Rubik's Cube using Simulated Annealing and Genetic Algorithms [1] that compares the performance of the two optimization algorithms in performance and application. The purpose of this project is to replicate the results of this study in terms of its simulated annealing algorithm to learn about its application with a complex optimization problem (i.e. solving a Rubik's Cube). Simulated annealing was chosen because of its faster computation times and robustness when solving any scramble state.

Simulated Annealing

A method of determining a global maximum using probabilistic search to choose values based on cost functions. As the sample space is searched, "temperature" decreases over time making the search more greedy.

Rubik's Cube Simulator

Figure 1: Image of the GUI provided with the Rubik's Cube simulator obtained from MATLAB [2]. The simulator can be downloaded from this link: Simulator/Solver.

Using an existing simulator in MATLAB, we represent the Rubik's Cube's face colors as a three-dimension matrix and manipulate this matrix representation in our SA algorithm. Although the simulator provides different solving algorithms, we did not use them in order to best explore the SA methodology of solving the Rubik's Cube.

Page updated

Google Sites

Report abuse