The Diameter of the Rubik's Cube Group Is Twenty
Authors:
- Tomas RokickiTRTomas Rokicki
- Herbert KociembaHKHerbert Kociemba
- Morley DavidsonMDMorley Davidson
- John DethridgeJDJohn Dethridge
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Review
- Vol. 56 (4) , 645-670
Abstract
We give an expository account of our computational proof that every position of the Rubik's Cube can be solved in 20 moves or fewer, where a move is defined as any twist of any face. The roughly $4.3 \times 10^{19}$ positions are partitioned into about two billion cosets of a specially chosen subgroup, and the count of cosets required to be treated is reduced by considering symmetry. The reduced space is searched with a program capable of solving one billion positions per second, using about one billion seconds of CPU time donated by Google. As a byproduct of determining that the diameter is 20, we also find the exact count of cube positions at distance 15.
Keywords
This publication has 6 references indexed in Scilit:
- Twenty-Two Moves Suffice for Rubik’s Cube®The Mathematical Intelligencer, 2009
- Harnessing parallel disks to solve Rubik’s cubeJournal of Symbolic Computation, 2009
- Linear-time disk-based implicit graph searchJournal of the ACM, 2008
- Twenty-six moves suffice for Rubik's cube2007
- Pattern DatabasesComputational Intelligence, 1998
- Depth-first iterative-deepeningArtificial Intelligence, 1985