Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube

Authors

  • Hewa Majeed Zangana Dept. of Computer Science, College of Computer Science and IT, Nawroz University, Kurdistan Region of Iraq

DOI:

https://doi.org/10.26438/ijcse/v8i2.16

Keywords:

Rubik Cube, Simulated Annealing, Genetic Algorithm

Abstract

The Rubik cube is 3D puzzle with 6 different colored faces. The classic 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) 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.

References

[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, 80-89, 2010.

[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, 442-451, 2010.

[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, 636-641, 2015.

[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, 789-796, 2016.

[12] Hewa Majeed Zangana "A New Algorithm for Shape Detection", IOSR-JCE, Vol. 19, Issue 3, pp. 71-76, 2017.

[13] K. Nandhini, B. Gomathi, "Implementation of LSB Based Steganography Algorithms in FPGA", International Journal of Scientific Research in Network Security and Communication, Vol.6, Issue.5, pp.32-37, 2018

[14] Riddhi H.Shaparia, Narendra M.Patel, Zankhana H. Shah, "Flower Classification using Different Color Channel", International Journal of Scientific Research in Computer Science and Engineering, Vol.7, Issue.2, pp.1-6, 2019

Downloads

Published

2020-02-28
CITATION
DOI: 10.26438/ijcse/v8i2.16
Published: 2020-02-28

How to Cite

[1]
H. M. Zangana, “Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube”, Int. J. Comp. Sci. Eng., vol. 8, no. 2, pp. 1–6, Feb. 2020.

Issue

Vol. 8 No. 2 (2020): IJCSE February Edition

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.