Daniel Kunkle
ABSTRACT
The number of moves required to solve any state of Rubik's cube has been a matter of long-standing conjecture for over 25 years -- since Rubik's cube appeared. This number is sometimes called "God's number". An upper bound of 29 (in the face-turn metric) was produced in the early 1990's, followed by an upper bound of 27 in 2006.
An improved upper bound of 26 is produced using 8000 CPU hours. One key to this result is a new, fast multiplication in the mathematical group of Rubik's cube. Another key is efficient out-of-core (disk-based) parallel computation using terabytes of disk storage. One can use the precomputed data structures to produce such solutions for a specific Rubik's cube position in a fraction of a second. Work in progress will use the new "brute-forcing" technique to further reduce the bound.
- Gene Cooperman, Larry Finkelstein, and Namita Sarawagi. Applications of Cayley graphs. In AAECC: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, International Conference, pages 367--378. LNCS, Springer-Verlag, 1990. Google Scholar
Digital Library
- Alexander H. Frey, Jr. and David Singmaster. Handbook of Cubik Math. Enslow Publishers, 1982.Google Scholar
- Herbert Kociemba. Cube Explorer. http://kociemba.org/cube.htm, 2006.Google Scholar
- Richard Korf. Finding optimal solutions to Rubik's cube using pattern databases. In Proceedings of the Workshop on Computer Games (W31) at IJCAI-97, pages 21--26, Nagoya, Japan, 1997.Google Scholar
- Silviu Radu. Rubik can be solved in 27f. http://cubezzz.homelinux.org/drupal/?q=node/view/53, 2006.Google Scholar
- Michael Reid. New upper bounds. http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid_new_upper_bounds.html, 1995.Google Scholar
- Michael Reid. Superflip requires 20 face turns. http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael reid_superflip_requires_20_face_turns.html, 1995.Google Scholar
Index Terms
- Twenty-six moves suffice for Rubik's cube
Recommendations
From Chaos to Order: A Group Theory Approach to the Rubik's Cube
ICACS '23: Proceedings of the 7th International Conference on Algorithms, Computing and SystemsRubik's cube is a classic puzzle toy, and restoring it is not an easy task, especially without memorizing formulas. In fact, the restoration of the Rubik's Cube is closely related to group theory. If we consider the cubes or facelets at each position of ...
Harnessing parallel disks to solve Rubik's cube
The number of moves required to solve any configuration of Rubik's cube has held a fascination for over 25 years. A new upper bound of 26 is produced. More important, a new methodology is described for finding upper bounds. The novelty is two-fold. ...
The Diameter of the Rubik's Cube Group Is Twenty
We give an expository account of our computational proof that every position of Rubik's Cube can be solved in 20 moves or less, where a move is defined as any twist of any face. The roughly $4.3 \times 10^{19}$ positions are partitioned into about two ...
Comments