Rubik’s cube proof cut to 25 moves

liukaipeng

<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

看不懂啊~~~~~~~~~

左佐

who can tell me what is the meaning？

rockboy1991

看不动!~~Can you spenk chinese

Pakhang

嗯，应该是这个意思，能25步内还原了

noski

离最终答案越来越近了。。

pengw

如果能用中文给出一个完整的推导，可能令人信服。总体感觉，主观结论多于推导，且无实例支持。用英文，有点打马虎之嫌

[ 本帖最后由 pengw 于 2008-4-29 08:56 编辑 ]

Cielo

这篇英文文章基本啥都没说。唯一理论的部分就是说他把所有的状态分成了若干个集合，由对称性某些集合里的状态就可以忽略了。这样就只需考虑剩下的那些集合里的状态了。<br>由于数量巨大，所以主要就是用很先进的电脑花很长时间算……<br>