[an error occurred while processing this directive]
BBC News
watch One-Minute World News
Last Updated: Thursday, 16 August 2007, 09:33 GMT 10:33 UK
Super solution for Rubik's cube
Rubik's cube, BBC
Rubik's cube has foxed people since the early 1980s
The ultimate solution to the Rubik's cube has come closer thanks to hours of number crunching on a supercomputer.

The research has proved that a Rubik's cube can be returned to its original state in no more than 26 moves.

The supercomputer took 63 hours to crank out the proof which goes one better than the previous best solution.

The two computer scientists behind the research project believe that with more work they could push the move count even lower.

Cube crunching

It took some smart thinking by graduate student Daniel Kunkle and Gene Cooperman from Northeastern University in Boston to come up with the proof because cranking through the 43 billion billion possible Rubik's cube positions would take too long even for a supercomputer.

Instead, the scientists used a two-step technique in their calculations.

Initially, they programmed the supercomputer to arrive at one of 15,000 half-solved solutions. They knew they could fully solve any of these 15,000 cubes with a few extra moves.

The results showed that any disordered cube could be fully solved in a maximum of 29 moves, but that most cubes took 26 moves or fewer.

The researchers then focused on the small number of "problem" configurations that required more than 26 moves.

Because there were so few "problem" configurations, the researchers could use the supercomputer to search for the best way to fully solve these cubes.

As it turned out the supercomputer was able to fully solve all of these special cases in fewer than 26 moves.

The study brings scientists one step closer to finding the so-called "God's Number" which is the minimum number of moves needed to solve any disordered Rubik's cube.

It is so named because God would only need the smallest number of moves to solve a cube. Theoretical work suggests that God's Number is in the "low 20s".

Mr Dunkle and Mr Cooperman announced their findings at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario.




SEE ALSO
The puzzling popularity of Su Doku
22 Apr 05 |  Magazine
Museum hosts mental masterclass
10 Sep 06 |  London
Supercomputer steps up the pace
27 Jun 07 |  Technology
Mouse brain simulated on computer
27 Apr 07 |  Technology
248-dimension maths puzzle solved
19 Mar 07 |  Science/Nature
Putting electronics in a spin
08 Aug 07 |  Technology

RELATED INTERNET LINKS
The BBC is not responsible for the content of external internet sites



FEATURES, VIEWS, ANALYSIS
Has China's housing bubble burst?
How the world's oldest clove tree defied an empire
Why Royal Ballet principal Sergei Polunin quit

PRODUCTS & SERVICES

Americas Africa Europe Middle East South Asia Asia Pacific