Shahram Saeidi

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

Full Text (PDF, 562KB), PP.1-10

Views: 0 Downloads: 0

Author(s)

Shahram Saeidi ^1,*

1. Tabriz Branch Islamic Azad University Tabriz, Iran

* Corresponding author.

DOI: https://doi.org/10.5815/ijeme.2018.01.01

Received: 31 Jan. 2017 / Revised: 10 Apr. 2017 / Accepted: 11 Sep. 2017 / Published: 8 Jan. 2018

Index Terms

Rubik’s Cube, Simulated Annealing, Genetic Algorithm

Abstract

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.

Cite This Paper

Shahram Saeidi,"Solving the Rubik’s Cube using Simulated Annealing and Genetic Algorithm", International Journal of Education and Management Engineering(IJEME), Vol.8, No.1, pp.1-10, 2018. DOI: 10.5815/ijeme.2018.01.01

Reference

[1] El-Sourani, N., Hauke, S., Borschbach, M. An evolutionary approach for solving the Rubik’s cube incorporating exact methods. EvoApplications, Part I, LNCS 6024, 2010, 80-89.

[2] Korf, R.E. Finding optimal solutions for Rubik’s cube using pattern databases, American Association for Artificial Intelligence. (www.aaai.org), 1997.

[3] Lee, D., Miller, W. A prolog program and demonstration of an efficient heuristic search method, Ziff-Davis magazine, 2(4), 1997.

[4] Kapadia, M., Deshpande, M.V., Umale, J. Rubik’s heuristic, Mumbai, India, Electro Info-Com, 2007.

[5] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P. Optimization by Simulated Annealing, Science 220, 1983.

[6] Aarts, E.H.L., Korst, H.H.M. Simulated Annealing and Boltzmann Machines, Wiley, Chichester, 1989.

[7] El-Sourani, N., Hauke, S., Borschbach, M. Design and Comparison of two Evolutionary Approaches for Solving the Rubik’s Cube, Parallel Problem Solving from Nature, PPSN XI, 2010, 442-451.

[8] El-Sourani, N. Design and Benchmark of different Evolutionary Approaches to Solve the Rubik's Cube as a Discrete Optimization Problem. Diploma Thesis, WWU Muenster, Germany, 2009.

[9] Anil, K. S., Solution for Rubik’s Cube by Using Genetic Algorithm, International Journal of Engineering Sciences & Research Technology , 2015, 636-641.

[10] Mantere, T., Solving Rubik's cube with cultural algorithm, unpublished, 2012.

[11] Smith, R. J., Kelly, S., Heywood, M. I., Discovering Rubik's Cube Subgroups using Co-evolutionary GP: A Five Twist Experiment, GECCO '16 Proceedings of the Genetic and Evolutionary Computation Conference, 2016, 789-796.

International Journal of Education and Management Engineering (IJEME)