43,252,003,274,489,856,000 cubes
Invented by a Hungarian professor of architecture, Erno Rubik, the eponymous Rubik's Cube was an icon of the 1980s and one of the most successful of modern toys. Thirty years on, the world finally has enough computing resources to have calculated the fastest solutions.
If you have ever tried to solve Rubik's cube you will know that it only takes a few twists and turns to transform it into a random pattern of coloured squares, and a few weeks of sleepless nights and sprained wrists to get it back to its original pattern. But it was always obvious that if it was possible to create a seemingly random pattern with, say, 12 twists of the cube, it should be equally possible to solve that cube in 12 moves or less.
Mathematicians pondered the question: what is the maximum number of moves needed to solve any possible starting position? Back in 1981, Morwen B Thistlethwaite calculated that 52 was the answer. Eleven years later, Hans Kloosterman proved than no more than 42 moves were needed to solve any cube. In 2006, Silviu Radu was able to reduce the magic number to 27, and in 2008, Tomas Rocicki showed it could be as low as 22.
An alternative to mathematical analysis is to program a computer to solve the cube and have it work through all possible combinations, working out the moves needed to solve it. Solving the cube on a computer isn't difficult. There is even an iPhone app for frustrated cube owners. The problem with using the computer to find the magic number is that there are over 43 million million million possible arrangements of a Rubik's Cube and it would take one of today's desktop computers around 35 years to check each one and come up with a definitive answer. However, a team of researchers using Google's massive distributed computing network have been able to process thousands upon thousands of solutions in parallel and in just a few weeks have come up with the ultimate answer.
A tiny fraction of the possible starting positions, (a mere 300 million positions or 0.000000000007 percent) required 20 moves to solve, and all other starting positions can be solved in 19 moves or less. Who would have thought that such a small toy would require so much computational power to find the best solution?
24th August 2010
This article comes from the SKILLZONE email newsletter, published monthly since January 2008, and covering topics related to technology and the internet. All articles and artwork in the SKILLZONE newsletter are orignal content.