Let’s twist again: how to solve the Rubik’s cube

How many twists are needed to unscramble an arbitrary position?

Rubik’s cube: better cubes, faster algorithms and more finger-tricks have brought the world record down to a 5.55 seconds

Rubik’s cube: better cubes, faster algorithms and more finger-tricks have brought the world record down to a 5.55 seconds

 

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

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
GO BACK
Error Image
The account details entered are not currently associated with an Irish Times subscription. Please subscribe to sign in to comment.
Comment Sign In

Forgot password?
The Irish Times Logo
Thank you
You should receive instructions for resetting your password. When you have reset your password, you can Sign In.
The Irish Times Logo
Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.
Screen Name Selection

Hello

Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
Forgot Password
Please enter your email address so we can send you a link to reset your password.

Sign In

Your Comments
We reserve the right to remove any content at any time from this Community, including without limitation if it violates the Community Standards. We ask that you report content that you in good faith believe violates the above rules by clicking the Flag link next to the offending comment or by filling out this form. New comments are only accepted for 3 days from the date of publication.