On the performance analysis of solving the Rubik’s cube using swarm intelligence algorithms

ABSTRACT

Swarm intelligence algorithms are nature-inspired algorithms that mimic natural phenomena to solve optimization problems. These natural phenomena are intelligent animal behavior used by animals for survival from hunting prey, migration, escaping predators, and reproduction. Some examples are ant colonies, flocking of birds, tracking patterns of hawks, herding behaviour of animals, bacterial growth, fish schooling, and intelligent microbial organisms. The Rubik’s cube is a 3D combinatorial puzzle with six faces covered by nine stickers of colors: white, red, blue, orange, green, and yellow. The objective is to turn the scrambled cube, where each side will have more than one colour, into a solved cube having only one colour on each side. This study uses the following algorithms – particle swarm optimization, ant colony optimization, discrete krill herd optimization, and a greedy tree search algorithm – to investigate which of the four can solve the Rubik’s cube in the shortest time using the shortest possible move sequence and show that swarm intelligence algorithms are capable of solving the Rubik’s cube.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. Cube Explorer 5.14 can be download from http://kociemba.org/downloads/cube514.zip.

2. The source code for Cube Explorer 5.14 can be found at https://github.com/hkociemba/CubeExplorer.

3. Python code used for implementing Kociemba’s algorithm in this study https://github.com/hkociemba/RubiksCube-TwophaseSolver.

4. This summary on the working of Kociemba’s algorithm is taken from https://ruwix.com/the-rubiks-cube/herbert-kociemba-optimal-cube-solver-cube-explorer/.

5. More detailed explanation on the working of the Kociemba’s algorithm can be found at http://kociemba.org/math/imptwophase.htm.

6. Pseudo code for Kociemba’s algorithm and other details can be found at http://kociemba.org/math/twophase.htm.

7. Python Code for generating random Rubik’s cube scrambles is taken from: https://github.com/BenGotts/Python-Rubiks-Cube-Scrambler.

8. The code for this research are available at https://github.com/JishnuJeevan/Swarm-Intelligence-Algorithms-For-The-Rubik-s-Cube-2.