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 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 more than 43 quintillion different positions (that’s a 43 followed by 18 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 foolproof and robust, but are generally far from optimal, requiring typically between 50 and 100 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.
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.
Quest for faster methods
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 five seconds.
Peter Lynch is professor of meteorology at University College Dublin. He blogs at
thatsmaths.com
. His book
Rambling Round Ireland
is now available as an ebook on amazon.com