Every Rubik's solution found

Every Rubik's solution found

WASHINGTON - 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, and showed it can always be solved in 20 moves or
less.

The study is just the latest attempt by Rubik's enthusiasts to figure
out the secrets of the cube, which has proven to be altogether far more
complicated that its jaunty colours might suggest.

At the crux of the quest has been a bid to determine the lowest number
of moves required to get the cube from any given muddled configuration
to the colour-aligned solution.

'Every solver of the Cube uses an algorithm, which is a sequence of
steps for solving the Cube,' said the team of mathematicians, who
include Morley Davidson of Ohio's Kent State University, Google engineer
John Dethridge, German math teacher Herbert Kociemba and Tomas Rokicki,
a California programmer. 'There are many different algorithms, varying
in complexity and number of moves required, but those that can be
memorized by a mortal typically require more than forty moves.' 'One may
suppose God would use a much more efficient algorithm, one that always
uses the shortest sequence of moves; this is known as God's Algorithm.

The number of moves this algorithm would take in the worst case is
called God's Number. At long last, God's Number has been shown to be
20.' The research, published online, ends a 30-year search for the most
efficient way to correctly align the 26 coloured cubes that make up Erno
Rubrik's 1974 invention.

'It took fifteen years after the introduction of the Cube to find the
first position that provably requires 20 moves to solve,' the team said.
'It is appropriate that fifteen years after that, we prove that twenty
moves suffice for all position.' Using computers lent to them by Google
- the company won't disclose how many or how powerful they are - the
team crunched through billions of Cube positions, solving each one over
a period of 'just a few weeks.' 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. -- AFP

--
http://www.fastmail.fm - Accessible with your email software
or over the web