August 11, 2010

Rubik’s Cube Solvable In 20 Steps Or Less

Supercomputers have determined that a Rubik's Cube can be solved in 20 moves or less from any position.

The international team used a bank of supercomputers at Google to help solve the 30-year quest to find the minimum number of moves needed to solve each of the billions of configurations. 

"We now know for certain that the magic number is 20," Professor Morley Davidson, a mathematician from Kent State University, told BBC News.

The results show that there are about 100 million starting positions that can be solved in 20 moves.

However, the majority of solutions can be solved in just between 15 and 19 moves.

Davidson told BBC that the number was "pure religion" because nobody had managed to crunch their way through all the possible 43,353,003,274,489,856,000 positions.

"We were secretly hoping in our tests that there would be one that required 21," he said.

The researchers split all of the possibilities into 2.2 billion groups, each containing 20 billion positions, in order to try and crack the Rubik's Cube code.

Davidson said it would have been "completely hopeless" to try and compute all the groups.  They reduced it by spotting duplicates and using symmetry to spot other similar combinations in order to make it more manageable.

The team managed to reduce the number to 56 million sets of 20 billion combinations.

Each combination took a "good PC 20 to 30 seconds to sort," Davidson told BBC.

The team then processed the batches on a supercomputer.

"Then Google stepped forward and offered to run the computation," he told BBC.

"We still don't know what machinery they used."

He said that the probability of there being a combination that required over 20 moves to solve "dropped into the very low digits," as the exercise went on.

Davidson and his team said they were convinced the problem had been solved and that the number of moves for the Rubik's Cube was 20 at the most.

"It's come full circle for me," he said. "Rubik's Cube was an icon of the 80s when I was growing up and was the reason I went into mathematics."

The initial results of the exercise had already been published online and Davidson said their method has now been submitted to peer-reviewed journals. 

"People are welcome to verify the code," he said. "You could check it on a small supercomputer."

Emö Rubik invited the Rubik's Cube in 1974 in Budapest as w rocking model of 3D geometry. 

Anssi Vanhala of Finland holds the record for solving the Cube by using feet in just 36.72 seconds.  Halyan Zhuang of China can solve it blindfolded in 30.94 seconds.


On the Net: