Article

Twenty-six moves suffice for Rubik's cube

Authors:

Daniel Kunkle,

Gene CoopermanAuthors Info & Claims

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Pages 235 - 242

https://doi.org/10.1145/1277548.1277581

Published: 29 July 2007 Publication History

Get Access

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.

References

[1]

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.

Digital Library

Google Scholar

[2]

Alexander H. Frey, Jr. and David Singmaster. Handbook of Cubik Math. Enslow Publishers, 1982.

Google Scholar

[3]

Herbert Kociemba. Cube Explorer. http://kociemba.org/cube.htm, 2006.

Google Scholar

[4]

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

[5]

Silviu Radu. Rubik can be solved in 27f. http://cubezzz.homelinux.org/drupal/?q=node/view/53, 2006.

Google Scholar

[6]

Michael Reid. New upper bounds. http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid_new_upper_bounds.html, 1995.

Google Scholar

[7]

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

Cited By

View all

Khan ASnow SMatthews B(2023)Participatory Design Tools: Leveraging Materiality and Familiarity to Adapt Unconventional Materials into Design ToolsProceedings of the 15th Conference on Creativity and Cognition10.1145/3591196.3593339(399-412)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3591196.3593339
Jin JPark S(2023)Key generation and management method using AI generated Rubik’s cube states2023 International Conference on Information Networking (ICOIN)10.1109/ICOIN56518.2023.10048916(719-724)Online publication date: 11-Jan-2023
https://doi.org/10.1109/ICOIN56518.2023.10048916
Singh MPant MDiwan SSnášel V(2022)Genetic Algorithm-enhanced Rank aggregation model to measure the performance of Pulp and Paper IndustriesComputers and Industrial Engineering10.1016/j.cie.2022.108548172:PAOnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108548
Show More Cited By

Index Terms

Twenty-six moves suffice for Rubik's cube
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

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 Systems

Rubik'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

Information & Contributors

Information

Published In

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

July 2007

406 pages

ISBN:9781595937438

DOI:10.1145/1277548

General Chair:
Dongming Wang
Beihang University and UPMC-CNRS (China/France)

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 29 - August 1, 2007

Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
2,694
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)5

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Khan ASnow SMatthews B(2023)Participatory Design Tools: Leveraging Materiality and Familiarity to Adapt Unconventional Materials into Design ToolsProceedings of the 15th Conference on Creativity and Cognition10.1145/3591196.3593339(399-412)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3591196.3593339
Jin JPark S(2023)Key generation and management method using AI generated Rubik’s cube states2023 International Conference on Information Networking (ICOIN)10.1109/ICOIN56518.2023.10048916(719-724)Online publication date: 11-Jan-2023
https://doi.org/10.1109/ICOIN56518.2023.10048916
Singh MPant MDiwan SSnášel V(2022)Genetic Algorithm-enhanced Rank aggregation model to measure the performance of Pulp and Paper IndustriesComputers and Industrial Engineering10.1016/j.cie.2022.108548172:PAOnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108548
Avola DCascio MCinque LFagioli AForesti GMarini MRossi F(2022)Real-time deep learning method for automated detection and localization of structural defects in manufactured productsComputers and Industrial Engineering10.1016/j.cie.2022.108512172:PAOnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108512
Lyu ZLiu ZKhojandi AJunfang Yu A(2022)Q-learning and traditional methods on solving the pocket Rubik’s cubeComputers and Industrial Engineering10.1016/j.cie.2022.108452171:COnline publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108452
Zheng TGlock CGrosse E(2022)Opportunities for using eye tracking technology in manufacturing and logisticsComputers and Industrial Engineering10.1016/j.cie.2022.108444171:COnline publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108444
Garg SKumar Sharma D(2022)Linguistic features based framework for automatic fake news detectionComputers and Industrial Engineering10.1016/j.cie.2022.108432172:PAOnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cie.2022.108432
Diego-Mantecón JArcera ÓBlanco TLavicza Z(2019)An Engineering Technology Problem-Solving Approach for Modifying Student Mathematics-Related Beliefs: Building a Robot to Solve a Rubik’s CubeInternational Journal for Technology in Mathematics Education10.1564/tme_v26.2.0226:2(55-64)Online publication date: 1-Jun-2019
https://doi.org/10.1564/tme_v26.2.02
Bonzio SLoi APeruzzi L(2018) On the n × n × n Rubik's Cube Mathematica Slovaca10.1515/ms-2017-015868:5(957-974)Online publication date: 20-Oct-2018
https://doi.org/10.1515/ms-2017-0158
Hulpke AKauers MOvchinnikov ASchost É(2018)Constructive Membership Tests in Some Infinite Matrix GroupsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3208983(215-222)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3208983
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

From Chaos to Order: A Group Theory Approach to the Rubik's Cube

Harnessing parallel disks to solve Rubik's cube

The Diameter of the Rubik's Cube Group Is Twenty

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations