ThatsMaths

The article in this week’s That’s Maths column in the Irish Times ( TM038 ) is about Rubik’s Cube and the Group Theory that underlies its solution.

Rubik’s Cube, invented in 1974 by Hungarian professor of architecture Ernő Rubik.

The Rubik’s cube craze ran through the world like wildfire in the 1980s. This simple mechanical puzzle is made from small pieces, called “cubies”, in a 3x3x3 structure in which each of the six faces of the cube can rotate freely. In the solved puzzle each face is a single colour, distinct from the other five faces. A move consists of twisting the nine cubies of any face through 90 or 180 degrees. But how many twists are needed to unscramble an arbitrary position?

Group Theory

Group theory is the branch of mathematics dealing with symmetry, and Rubik’s cube is replete with symmetries. Even before twisting any faces, we can orient the cube in 24 ways: there are six choices for the top face and, given this, four for the front. Symmetries such as these allow us to reduce drastically the search space, or cube group, when seeking a solution.

The size of the Rubik’s cube group is truly enormous: there are over 43 quintillion different positions (43 followed by eighteen zeros), so a brute-force search for solutions to every possible scrambled position is impractical. Several systematic strategies, or solution algorithms, have been devised. These are fool-proof and robust, but are generally far from optimal, requiring typically between 50 and 100 moves.

Minimum Number of Moves

The challenge is to find the minimum value N such that any position can be unscrambled in at most N moves. The approach has been to squeeze N between lower and upper bounds and see if we can make these bounds equal. A lower bound is provided by the “superflip” position – all cubies in position, corners correctly oriented and orientation of the edges reversed. The superflip position cannot be solved in fewer than 20 moves, so 20 is a lower bound for N.

Superflip position: all cubies in position, corners correctly oriented and edges reversed.

Upper bounds for N are provided by the solution strategies. An early method devised by David Singmaster needed 227 moves. Later, Morwen Thistlethwaite used group theory to devise an algorithm requiring 52 moves. After many subsequent improvements, Tomas Rokicki showed, in July 2010, that the upper bound is 20. Rokicki used symmetry arguments to reduce the search space and then divided up the problem so that different parts could be solved on different computers. Since this upper bound equals the lower bound, the number N must be 20.

Faster and Faster Still

While a solution from any starting position in at most 20 moves is known to exist, no practical method is known that can be used by a human to unscramble the cube in 20 turns. The best general algorithms require at least twice as many moves as this, and cube-lovers continue the quest for faster solution methods

Recently, there has been an upsurge of interest in Rubik’s cube, with a focus on speed-cubing. Modern cubes have smooth bearings: the faces can be turned at a touch of the finger, and one-handed solving is feasible. The World Cubing Association sanctions hundreds of tournaments each year. Better cubes, faster algorithms and more finger-tricks have brought the world record down to an astounding 5.55 seconds and a robot has been built that solves the puzzle in under 5 seconds.

Sources

Dana Mackenzie, 2013: Mathematicians do the twist. In What’s happening in the mathematical sciences. Volume 9, pp 68-83.

Rubik’s Cube World Records.

*        *        *

Peter Lynch’s book about walking around the coastal counties of Ireland is now available as an ebook (at a very low price!). For more information and photographs go to http://www.ramblingroundireland.com/