Twenty-six moves suffice for Rubik's cube

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Twenty-six moves suffice for Rubik's cube

Full text

Pdf (240 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 2007 international symposium on Symbolic and algebraic computation table of contents

Waterloo, Ontario, Canada

SESSION: Contributed papers table of contents

Pages: 235 - 242

Year of Publication: 2007

ISBN:978-1-59593-743-8

Authors

Daniel Kunkle	Northeastern University, Boston, MA
Gene Cooperman	Northeastern University, Boston, MA

Sponsors

ACM: Association for Computing Machinery
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 203, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1277548.1277581 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Gene Cooperman , Larry Finkelstein , N. Sarawagi, Applications of Cayley Graphs, Proceedings of the 8th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.367-378, August 20-24, 1990
	2	Alexander H. Frey, Jr. and David Singmaster. Handbook of Cubik Math. Enslow Publishers, 1982.
	3	Herbert Kociemba. Cube Explorer. http://kociemba.org/cube.htm, 2006.
	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.
	5	Silviu Radu. Rubik can be solved in 27f. http://cubezzz.homelinux.org/drupal/?q=node/view/53, 2006.
	6	Michael Reid. New upper bounds. http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid_new_upper_bounds.html, 1995.
	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.

CITED BY 5

	Eric Robinson , Daniel Kunkle , Gene Cooperman, A comparative analysis of parallel disk-based Methods for enumerating implicit graphs, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada
	Daniel Kunkle , Gene Cooperman, Solving Rubik's Cube: disk is the new RAM, Communications of the ACM, v.51 n.4, April 2008
	Richard E. Korf, Linear-time disk-based implicit graph search, Journal of the ACM (JACM), v.55 n.6, p.1-40, December 2008
	Daniel Kunkle , Gene Cooperman, Harnessing parallel disks to solve Rubik's cube, Journal of Symbolic Computation, v.44 n.7, p.872-890, July, 2009
	Richard E. Korf, Minimizing disk I/O in two-bit breadth-first search, Proceedings of the 23rd national conference on Artificial intelligence, p.317-324, July 13-17, 2008, Chicago, Illinois