Rubik's in 26 [or less]
Posted Aug16-07 at 07:47 AM by robphy
Recently, there's been a buzz about this result:
Northeastern University Researchers Solve Rubik’s Cube in 26 Moves (May 2007)
<a href="http://www.ccs.neu.edu/home/gene/papers/rubik.pdf">
Twenty-Six Moves Suffice for Rubik’s Cube (Daniel Kunkle and Gene Cooperman)</a>
<blockquote>The number of moves required to solve any state of Rubik’s cube
has been a matter of long-standing conjecture for over 25 years
— since Rubik’s cube appeared. This number is sometimes called
“God’s number”. An upper bound of 29 (in the face-turn metric)
was produced in the early 1990’s, followed by an upper bound of 27
in 2006.
An improved upper bound of 26 is produced using 8000 CPU
hours. One key to this result is a new, fast multiplication in the
mathematical group of Rubik’s cube. Another key is efficient outof-
core (disk-based) parallel computation using terabytes of disk
storage. One can use the precomputed data structures to produce
such solutions for a specific Rubik’s cube position in a fraction
of a second. Work in progress will use the new “brute-forcing”
technique to further reduce the bound.</blockquote>
If you want to try one out, here's the Rubik's Cube Simulator
http://www.ryanheise.com/cube/speed.html
Northeastern University Researchers Solve Rubik’s Cube in 26 Moves (May 2007)
<a href="http://www.ccs.neu.edu/home/gene/papers/rubik.pdf">
Twenty-Six Moves Suffice for Rubik’s Cube (Daniel Kunkle and Gene Cooperman)</a>
<blockquote>The number of moves required to solve any state of Rubik’s cube
has been a matter of long-standing conjecture for over 25 years
— since Rubik’s cube appeared. This number is sometimes called
“God’s number”. An upper bound of 29 (in the face-turn metric)
was produced in the early 1990’s, followed by an upper bound of 27
in 2006.
An improved upper bound of 26 is produced using 8000 CPU
hours. One key to this result is a new, fast multiplication in the
mathematical group of Rubik’s cube. Another key is efficient outof-
core (disk-based) parallel computation using terabytes of disk
storage. One can use the precomputed data structures to produce
such solutions for a specific Rubik’s cube position in a fraction
of a second. Work in progress will use the new “brute-forcing”
technique to further reduce the bound.</blockquote>
If you want to try one out, here's the Rubik's Cube Simulator
http://www.ryanheise.com/cube/speed.html
Total Comments 1
Comments
-
Wow! Seems to me that an upper bound of 26 moves is low, but then I didn't spend 8000 cpu hours to come to that conclusion.Posted Jun12-10 at 08:40 AM by Teddy Bears 
