### Rubik's Cube

August 27, 2010 Symmetry is used to simplify many problems. One of the most fundamental mathematical symmetries that's useful in the physical sciences is the concept of odd and even functions. Knowing that the functions you are analyzing are odd or even leads to many simplifications, the most useful of which involves integration. The integral of an odd function from -x to +x is zero, provided that there is no vertical asymptote in that range. Likewise, the integral of an even function from -x to +x is twice the integral from 0 to +x (same caveat about an asymptote). Symmetry is useful in some unexpected places. A family member once purchased a Rubik's Cube puzzle for me at a garage sale. Unlike store-stocked cubes that are packaged as a "solved" cube with each face showing a single color, this cube was scrambled. The faces of this cube were colored by attachment of vinyl squares to the plastic mechanism. I immediately realized that this cube puzzle wasn't solvable, since someone had swapped some of the colored squares. A corner element on this particular cube had the same color on two faces. Since a solved cube has a different color on each face, there was no possible manipulation of the cube that would do this. I wrote about Rubik's Cube in a previous article (Rubik's Cube, April 11, 2008). There's a lot of mathematics in the Rubik's cube puzzle. The cube has its own mathematical group that corresponds to the set of all possible operations. Because of the plethora of initial states that a cube can have, this group has 43,252,003,274,489,856,000 elements; or, more descriptively,2^{27}3^{14}5^{3}7^{2}11^{1}

Mathematical analysis of Rubik's Cube began quite soon after it was introduced. The main question on everyone's mind was the minimum number of operations it takes to solve an arbitrary cube. There are quite a few known algorithms for "solving" the Cube that take fewer than a hundred moves. Notice the quotation marks around "solving." These operations work, but they are not proven to

*always*work. Rubik's Cube was introduced in America in 1980, and computing at that time was not sufficiently developed to analyze all positions of the cube and state with surety the minimum number of operations for solution. In 1981, the mathematician, Morwen Thistlethwaite, showed that at most 52 moves would suffice. Over the years, this number was reduced, [1] and in 2008 it was known that 22 moves will suffice. That number was found by Tomas Rokicki and John Welborn. [2] Rokicki, a programmer from Palo Alto, CA, continued to work on the problem with Morley Davidson, a mathematician from Kent State University, John Dethridge, an engineer at Google in Mountain View, CA, and Herbert Kociemba, a mathematics teacher from Darmstadt, Germany. In July, 2010, this team announced via their web site, http://www.cube20.org, that they had analyzed every Rubik's Cube position by computer and found that

**no more than 20 moves suffice**. The analysis consumed 35 CPU-years of idle computer time donated by Google. Their method, according to their web site,[1] was as follows: • They partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.

• They reduced the count of sets needed to solve to 55,882,296 using symmetry and set covering.

• They didn't attempt to find optimal solutions to each position, but instead only solutions of length 20 or less.

• Their program solved a single set in about 20 seconds.

• It would take a four-core, 2.8 GHz computer 1.1 billion CPU-seconds, or 35 CPU years, to find solutions to all of the positions in each of the 55,882,296 sets. [3] The graph of the required number of moves needed to solve Rubik's Cube is interesting. Of course, there is only one configuration that requires zero moves, and things are quite uniform on a logarithmic scale until close to the twenty move limit. As the team demonstrated, there are no configurations that require more than twenty moves to solve. This work reminds me of the computer-assisted proof of the Four-Color Conjecture that I wrote about in a previous article (You Can Get There From Here, March 26, 2008). The conjecture, that you need only four colors to color a map such that no adjacent regions have the same color, was not easy to prove analytically. In 1976, Kenneth Appel and Wolfgang Haken published a proof of this conjecture using a computer to analyze every conceivable map.

### References:

- Tomas Rokicki, "Twenty-Five Moves Suffice for Rubik's Cube" (ArXiv, March 24, 2008)
- The Cube-20 Web Site
- Surprisingly, this amounts to less than $10,000 of supercomputer time.

*Permanent Link to this article*

Linked Keywords: Symmetry; odd and even functions; asymptote; Rubik's Cube; mathematical group; algorithms; Morwen Thistlethwaite; Palo Alto, CA; Kent State University; Google; Mountain View, CA; Darmstadt, Germany; http://www.cube20.org; Four-Color Conjecture; Four-Color Theorem; Kenneth Appel; Wolfgang Haken.

RSS Feed

### Google Search

Latest Books by Dev Gualtieri

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Other Books

- Magnetocapacitive Tunnel Junctions - August 21, 2017

- Tardigrades - August 14, 2017

- Roman Concrete - August 7, 2017

- Solar Spicules - July 31, 2017

- Schroeder Diffuser - July 24, 2017

- Rough Microparticles - July 17, 2017

- Robot Musicians - July 10, 2017

- Walter Noll (1925-2017) - July 6, 2017

- cosmogony - July 3, 2017

- Crystal Prototypes - June 29, 2017

- Voice Synthesis - June 26, 2017

- Refining Germanium - June 22, 2017

- Granular Capillarity - June 19, 2017

- Kirchhoff–Plateau Problem - June 15, 2017

- Self-Assembly - June 12, 2017

- Physics, Math, and Sociology - June 8, 2017

- Graphene from Ethylene - June 5, 2017

- Crystal Alignment Forces - June 1, 2017

- Martian Brickwork - May 29, 2017

- Carbon Nanotube Textile - May 25, 2017

- The Scent of Books - May 22, 2017

- Patterns from Randomness - May 18, 2017

- Terpene - May 15, 2017

- The Physics of Inequality - May 11, 2017

- Asteroid 2015 BZ509 - May 8, 2017

- Fuzzy Fibers - May 4, 2017

- The Sofa Problem - May 1, 2017

- The Wisdom of Composite Crowds - April 27, 2017

- J. Robert Oppenheimer and Black Holes - April 24, 2017

- Modeling Leaf Mass - April 20, 2017

- Easter, Chicks and Eggs - April 13, 2017

- You, Robot - April 10, 2017

- Collisions - April 6, 2017

- Eugene Garfield (1925-2017) - April 3, 2017

- Old Fossils - March 30, 2017

- Levitation - March 27, 2017

- Soybean Graphene - March 23, 2017

- Income Inequality and Geometrical Frustration - March 20, 2017

- Wireless Power - March 16, 2017

- Trilobite Sex - March 13, 2017

- Freezing, Outside-In - March 9, 2017

- Ammonia Synthesis - March 6, 2017

- High Altitude Radiation - March 2, 2017

- C.N. Yang - February 27, 2017

- VOC Detection with Nanocrystals - February 23, 2017

- Molecular Fountains - February 20, 2017

- Jet Lag - February 16, 2017

- Highly Flexible Conductors - February 13, 2017

- Graphene Friction - February 9, 2017

- Dynamic Range - February 6, 2017

- Robert Boyle's To-Do List for Science - February 2, 2017

- Nanowire Ink - January 30, 2017

- Random Triangles - January 26, 2017

- Torricelli's law - January 23, 2017

- Magnetic Memory - January 19, 2017

- Graphene Putty - January 16, 2017

- Seahorse Genome - January 12, 2017

- Infinite c - January 9, 2017

- 150 Years of Transatlantic Telegraphy - January 5, 2017

- Cold Work on the Nanoscale - January 2, 2017

### Deep Archive

Deep Archive 2006-2008

**Blog Article Directory on a Single Page**