The Hindu : Front Page : Computer tackles Rubik’s cube enigma

Online edition of India's National Newspaper
Saturday, Aug 18, 2007
ePaper

Front Page

Front Page

Computer tackles Rubik’s cube enigma

London: It is the holy grail for puzzle-lovers around the world. A task that has thwarted the greatest minds for generations. But the ultimate solution to the Rubik’s cube may be within grasp.

A supercomputer has been working without pause to provide conclusive evidence that the cube can be returned to its original state in no more than 26 moves.

In 63 hours

The computer took 63 hours to provide the proof, which goes one better than the previous best solution. But the two computer scientists behind the research project, Daniel Kunkle and Gene Cooperman from Northeastern University in Boston, Massachusetts, are not content to rest on their laurels. They are confident that with more hard graft they can move the count still lower.

The computer may be clever but the two men have proved that the human brain is still a match for its electronic counterpart.

They realised that calculating the 43 billion possible Rubik’s cube positions would take even the most super of computers far too long.

Two-step technique

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

They initially programmed the supercomputer to arrive at one of 15,000 half-solved solutions, aware that they could fully solve any of these 15,000 cubes with just a few extra moves. The results of the comprehensive research revealed that any cube — no matter how disordered — could be fully solved in a maximum of 29 moves, but most cubes could perfectly be ordered in 26 moves or fewer.

The researchers then focused on the small number of stubborn “problem” cubes that required more than 26 moves. Which is when their electronic friend stepped in.

The computer was able to fully solve all the special cases in fewer than 26 moves. The scientists know that this most recent development brings them one step closer to discovering the so-called “God’s Number” — the minimum number of moves needed to solve any Rubik’s cube.

The coveted mathematical prize is thus named because only God would need the smallest number of moves to solve a cube.

Extensive theoretical research 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. — © Guardian Newspapers Limited, 2007

Printer friendly page
Send this article to Friends by E-Mail

Front Page