<h2>original link:</h2>http://arxivblog.com/?p=332<br><p><a href="http://arxivblog.com/wp-content/uploads/2008/03/s-cube.jpg" title="Rubik’s cube"><br></a></p>
<p>Last year, a couple of fellas at Northeastern University with a bit
of spare time on their hands proved that any configuration of a Rubik’s
cube could be solved in a maximum of 26 moves.</p>
<p>Now Tomas Rokicki, a Stanford-trained mathematician, has gone one
better. He’s shown that there are no configurations that can be solved
in 26 moves, thereby lowering the limit to 25.</p>
<p>Rokicki’s proof is a neat piece of computer science. He’s used the
symmetry of the cube to study transformations of the cube in sets,
rather than as individual moves. This allows him to separate the “cube
space” into 2 billion sets each containing 20 billion elements. He then
shows that a large number of these sets are essentially equivalent to
other sets and so can be ignored.</p>
<p>Even then, to crunch through the remaining sets, he needed a
workstation with 8GB of memory and around 1500 hours of time on a Q6600
CPU running at 1.6GHz.</p>
<p>But Rokicki isn’t finished there. He is already number-crunching his
way to a new bound of 24 moves, a task he thinks will take several CPU
months. And presumably after that, 23 beckons.</p>
<p>Where is this likely to finish? A number of configurations are known
that can be solved in 20 moves but it’s also known that there are no
configurations that can be solved in 21 moves.</p>
<p>So 20 looks like a good number to aim at although that will still be
an upper limit. No news yet on whether 20 might also be the lower
limit, which would give the answer a satisfying symmetry.</p>
<p>What this problem is crying out for is a kindly set theorist who can
prove exactly what the upper and lower limits should be without
recourse to a few years of CPU time (although it may take a few years
of brain time). Any takers?</p>作者: hm123123 时间: 2008-3-31 11:46:46
看不懂啊~~~~~~~~~作者: 左佐 时间: 2008-3-31 12:14:16
who can tell me what is the meaning？作者: rockboy1991 时间: 2008-3-31 12:26:56
看不动!~~Can you spenk chinese作者: bfans2004 时间: 2008-3-31 12:35:48