Open Access   Article Go Back

Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube

Hewa Majeed Zangana1

Section:Research Paper, Product Type: Journal Paper
Volume-8 , Issue-2 , Page no. 1-6, Feb-2020

CrossRef-DOI:   https://doi.org/10.26438/ijcse/v8i2.16

Online published on Feb 28, 2020

Copyright © Hewa Majeed Zangana . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: Hewa Majeed Zangana, “Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube,” International Journal of Computer Sciences and Engineering, Vol.8, Issue.2, pp.1-6, 2020.

MLA Style Citation: Hewa Majeed Zangana "Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube." International Journal of Computer Sciences and Engineering 8.2 (2020): 1-6.

APA Style Citation: Hewa Majeed Zangana, (2020). Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube. International Journal of Computer Sciences and Engineering, 8(2), 1-6.

BibTex Style Citation:
@article{Zangana_2020,
author = {Hewa Majeed Zangana},
title = {Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {2 2020},
volume = {8},
Issue = {2},
month = {2},
year = {2020},
issn = {2347-2693},
pages = {1-6},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=5021},
doi = {https://doi.org/10.26438/ijcse/v8i2.16}
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
DO = {https://doi.org/10.26438/ijcse/v8i2.16}
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=5021
TI - Using Genetic Algorithm With Simulated Annealing To Solve Rubik Cube
T2 - International Journal of Computer Sciences and Engineering
AU - Hewa Majeed Zangana
PY - 2020
DA - 2020/02/28
PB - IJCSE, Indore, INDIA
SP - 1-6
IS - 2
VL - 8
SN - 2347-2693
ER -

VIEWS PDF XML
265 758 downloads 147 downloads
  
  
           

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.

Key-Words / Index Term

Rubik Cube, Simulated Annealing, Genetic Algorithm

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