## 2.10.2011

### Rubik Cube puzzle game and the race to solve it in minimum time

According to Erno Rubik, founder of the Rubik’s cube:

“A good puzzle, it's a fair thing. Nobody is lying. It's very clear, and the problem depends just on you”

Firstly, it would be better to give the introduction of the Rubik’s cube to the novice. The Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture ErnÅ‘ Rubik. Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toys in 1980.This has won the German game of the years award. Almost 350 million Rubik’s cubes have been sold as of January, 2009, making it the world's top-selling puzzle game. By "God," I mean Morley Davidson, John Dethridge, Herbert Kociemba, Tomas Rokicki and about 35 CPU-years. The long-sought magic number of moves to solve the Rubik’s cube puzzle from any position is determined.

An international team of researchers using computer time lent to them by Google has found every way the popular Rubik's Cube puzzle can be solved. The study is just one of the plethoras of attempts by Rubik's enthusiasts to figure out the mysteries of the cube, which has proven to be altogether far more complicated that its debonair colors might suggest. The study builds on the work of a veritable pantheon of Rubik's researchers, starting with Morwen Thistlethwaite who in 1981 showed 52 moves were sufficient to reach the solution from any given Cube position.

Ever since Erno Rubik conceived the Rubik's Cube in 1974, math-minded enthusiasts have been trying to find the most efficient number of moves required to solve the 3x3 Rubik's Cube in any script, which they refer to as "God's Algorithm".  And in God's Algorithm, the maximum number of moves for the worst case scenario has finally been solved—"God's Number" is 20.

The minimum number of moves reduced to 42 by the period of 1992 and by 2005 this number reduced to 28 but still the enthusiasts were looking for the perfect minimum solution which was termed as God’s Number and it was believed that no less than God’s algorithm would be able to solve it.

There are exactly 43,252,003,274,489,856,000 permutations of Rubik’s cube which is an unimaginable number to solve out. Any one of the movement pattern out of 43,252,003,274,489,856,000 permutations can be used to make up the cube. It was really challenging to define the number of moves required to cover any of the arrangement to make up the cube.

So, how did a Google engineer, a Kent State mathematician, a German math teacher and a Californian programmer crack the code?

According to them,

“We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each. We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering. We did not find optimal solutions to each position, but instead only solutions of length 20 or less. We wrote a program that solved a single set in about 20 seconds of time. We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets”.

The "Superflip" (left) was the first position ever found with 20 moves.

"It took fifteen years after the introduction of the Cube to find the first position that irrefutably requires twenty moves to solve; it is appropriate that fifteen years after that, we prove that twenty moves suffice for all positions."

If anybody is still in a condition of disbelief, the team of researchers has their own website to give a detailed analysis of how they did it including the history of God’s number.