Magical Patterns

May 30, 2016

(Published in Aftenposten Monday May 30, 2016, in Norwegian.)

*How many moves are needed to solve Rubik's Cube?**How quickly can Rubik's cube be solved?**Here's more on cube research and cube records!*

A precise mathematical problem about Rubik's cube, which was open and unsolved until 2010, is the question of how many moves it takes to solve it. More specifically: How many moves is needed to solve *all possible configurations* of the cube?

If you scramble the cube just a little bit, very few moves are needed. The more you scramble it, the more moves are needed to solve it. But exactly where is the limit? If you scramble it *as much as possible*, how many moves are needed then?

For the record, this is not an easy question to answer, because the cube can be in forty-three billion billion (43 252 003 274 489 856 000) different states.

Mathematicians are fond of talking about *upper* and *lower* bounds, and this is also the case here. Let us start with the upper bound for how many moves are required to solve the cube. An upper bound is a number of moves such that no configuration requires *more* moves than this number.

In the late 70s, the British mathematician David Singmaster (1939–) proved that 277 moves is sufficient. That means that 277 is an *upper bound*: By using 277 moves, *any* cube can be solved.

But since the 70s, mathematicians have over and over managed to find lower numbers. In the early 80s, Morwen Thistlethwaite found out that 52 moves were sufficient. For a long time, it was uncertain whether the upper bound could be any lower.

On the other hand, the hunt was on for *lower bounds* of the number of moves necessary. It was well known that certain cube configurations required eighteen moves, but it was unclear whether the number could be higher. *Were there configurations even more difficult to solve?*

In the mid 90s, a special configuration, the superflip, was found, that actually required twenty moves. This was the new lower bound, and it would take another fifteen years before the upper bound was found.

In 2010 the answer was found: Twenty was *also* the upper bound! This means that twenty moves is both *necessary* and *sufficient* in order to solve any configuration of Rubik's cube. It is *necessary* due to configurations like superflip, and it *sufficient* because you never need *more* than twenty moves to solve any cube.

It was the American programmer Tomas Rokicki from Palo Alto, California who was responsible for the breakthrough, with help from Google, who donated spare computing time. This number has since been referred to as God's number, and the full story can be read on the website cube20.org.

The story of upper and lower bounds does not really stop with the number twenty. The story above namely supposes that *one move* consists of turning one side completely freely, that is, 90 degrees in one direction or 180 degrees in any direction.

If we restrict ourselves to moves of exactly 90 degrees, we get a different analysis. Mathematicians like naming things, and this is often called *quarter-turn metric* instead of *half-turn metric*.

This creates a much more difficult problem, because a move of 180 degrees now counts as two moves instead of one. The story about upper and lower bounds evolved similarly, and in August 2014, the problem was finally solved.

It was again Tomas Rokicki and his collaborators who found the answer: With quarter-turn metric the answer is 26.

New records for speed cubing are continuously being set. If we take a look at the website of World Cube Association, a great resource for competitions and registered cube records, we see how the records of the regular 3x3x3 cube has evolved from 2004 to 2016:

In the graph above you find all of the official records, but also the tenth and hundredth places. It is clear that we are approaching a limit to how quickly the cube can be solved. The current world record for solving the regular 3x3x3 cube was made by the American 14-year old Lucas Etter in November 2015 at 4.90 seconds.

Here in Norway, it is Jonathan Hamstad and Morten Arborg who compete for the Norwegian record. Since October 2015 it is the former who holds the record at 6.33 seconds. To see all the records, I recommend the website of the World Cube Association. The Norwegian Cube Association (in Norwegian) provides information on cubing in Norway.

It is perhaps no surprise that robots solve Rubik's Cube faster than humans. But just *how fast* can a robot solve the cube?

In January 2016, a new world record in robot cubing was set. At that time, a robot was able to to see, analyze and completely solve the cube in no more than 0.887 seconds.

Finally, it must be noted that there are many variations to *how* the cube is solved and to *how* similar cube puzzles are constructed. In the video above you can see a little of this fascinating universe of varieties.

by Roger Antonsen