Supercomputer takes on Rubik's Cube

by Paul Jay, CBCNews.ca

The Rubik's Cube was never my bag growing up, but clearly, some people still remain devoted to solving the seemingly simple yet surprisingly complex puzzle game in as few moves as possible.

How many moves is that you ask? A pair of researchers at Northeastern University in Boston say they've come closer to the answer, proving that a Rubik's Cube can be solved in 26 moves or fewer.

The two announced their findings two and a half weeks ago at the International Symposium on Symbolic and Algebraic Computation hosted by the University of Waterloo.

As the BBC reports, the two had to figure out a way to go through the potential 43 billion billion possible cube positions - a task too daunting even for today's supercomputers. So instead they programmed the computer to arrive at one of 15,000 half-solved solutions they knew could be solved with a few extra moves.

That gave the computer a more manageable database to work with - though it still took the computer 8000 hours - and in the end the computer was able to solve all of the positions in 26 moves or less.

It's not the final word on the subject, however, as the two suggest the actual minimum number of moves to solve all positions - which has been dubbed 'God's number' - is probably lower.

You can read the actual pdf of the report here.