Solving the Rubik’s Cube using Simulated Annealing and Genetic Algorithm

The Rubik’s cube is 3D puzzle with 6 different colored faces. The classis puzzle is a 3x3x3 cube with 43 quintillion possible permutations having a complexity of NP-Hard. In this paper, new metaheuristic approaches based on Simulated Annealing (SA) and Genetic Algorithm (GA) are proposed for solving the cube. The proposed algorithms are simulated in Matlab software and tested for 100 random test cases. The simulation results show that the GA approach is more effective in finding shorter sequence of movements than SA, but the convergence speed and computation time of the SA method is considerably less than GA. Besides, the simulation of GA confirms the claim that the cube can be solved with maximum 22 numbers of movements.