26步之內解魔術方塊 - 魔術方塊

作者: wildmb (Styrofoam) 看板: wildmb
標題: 26步之內解魔術方塊
時間: Wed Aug 22 01:09:08 2007


http://www.sciencenews.org/articles/20070811/mathtrek.asp

Cracking the Cube
Solving Rubik's Cube gets one move quicker
Julie J. Rehmeyer

Daniel Kunkle can solve a Rubik's Cube in 26 moves. Or at least his computer
can.

Kunkle, a computer scientist at Northeastern University in Boston, has proved
that 26 moves are enough to solve any Rubik's Cube, no matter how scrambled.
That's one move below the previous record. In the process of cracking the
cube, he developed algorithms that can be useful for problems as disparate as
scheduling air flights and determining how proteins will fold.

Rubik's Cube has approximately 43 quintillion possible configurations. Even a
supercomputer can't search through every possible configuration to find the
quickest way to unscramble a given starting arrangement in a reasonable
amount of time. So Kunkle and his advisor Gene Cooperman developed some
clever mathematical and computational strategies to make the puzzle more
manageable.

Kunkle and Cooperman started by applying various mathematical tricks. If each
side of the cube is one color, the puzzle is solved regardless of which color
is on which side. By considering configurations to be equivalent if they
differ only in having two colors interchanged, the computer scientists
managed to reduce the number of truly distinct configurations to just over a
quintillion.

Next, they looked at a simpler problem: they considered only configurations
that could be solved by twisting facelets through half-turns only, with no
quarter-turns. Only about 15,000 of the quintillion configurations can be
solved in this way. A standard PC can find the shortest way to unscramble
each of this relatively small number of configurations in less than a day,
simply by searching through all possible moves. The team found that any
puzzle in one of those special configurations could be solved in 13 moves or
fewer.

Then they figured out how many steps are required to turn any random
configuration into one of the 15,000 special configurations. To do this, they
first classified the configurations into sets, each containing configurations
that can be transformed among themselves using only half-turns. These sets
were constructed in such a way that a series of moves that gets from one
member of any set to one of the special configurations will also turn any
other member of the set into a special configuration. They ended up with 1.4
trillion of these sets, so they now had only 1.4 trillion problems to solve—
far fewer than the original 43 quintillion, but still a formidable number.

Now they put a supercomputer on the job and applied clever computational
strategies to speed up the search. Because it takes computers a very long
time to search for information stored on a hard drive, Kunkle and Cooperman
developed ways to store the information in precisely the order the computer
would later need it. That way, the computer could read the information off
the drive without searching for it.

"These kinds of techniques can be applied to any combinatorial problem that
you want to solve," Kunkle says. He points to checkers, chess, scheduling of
air flights, and protein folding as examples. A somewhat similar set of
computational techniques was recently used to find the best strategies for
playing checkers (SN: 7/21/07, p. 36).

After 63 hours of calculation, the supercomputer found that it took no more
than 16 steps to turn any random configuration into a special configuration
that can be solved using only half-turns. And since those special puzzles can
be solved in no more than 13 steps, this approach showed that 29 steps were
enough to solve any Rubik's Cube.

But this answer wasn't good enough to set a new record. Last year, Silviu
Radu of the Lund Institute of Technology in Sweden showed that any Rubik's
Cube can be solved in no more than 27 steps. Kunkle and Cooperman realized
that to set a new record, they would need to eliminate three steps.

Their existing method had established that all but about 80 million sets of
configurations could be solved in 26 steps or fewer. By searching through all
possible moves starting from those relatively few configurations, they
succeeded in finding a solution for each one that took 26 steps or fewer.

They presented their result July 29 at the International Symposium on
Symbolic and Algebraic Computation in Waterloo, Ontario.

Kunkle and Cooperman now hope to knock the maximum number of steps down to
25. They think they can use their brute-force search method on all of the
configurations that require 26 steps to find a quicker way to solve them.

Even if they manage this feat, however, it will probably leave room for
improvement. Most researchers believe that just 20 steps are enough to solve
any Rubik's Cube, but no one has proved it yet.

--

興趣：收集各種魔術方塊~
http://shr.homeip.net/gallery/Cube

魔術方塊時距測量網頁
http://rubiks.tw/timer

--