(zz)最新结果: 25步可以还原任意魔方

sokoban

Rubik's Cube -- 25 Moves or Less Tomas Rokicki (arxiv.org/abs/0803.3435): How many moves does it take to solve Rubik's Cube? Positions are known that require 20 moves, and it has already been shown that there are no positions that require 27 or more moves; this is a surprisingly large gap. This paper describes a program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second. We use this program, along with some new ideas and incremental improvements in other techniques, to show that there is no position that requires 26 moves.
论文可以在
http://arxiv.org/abs/0803.3435 下载

此文翻译见

http://bbs.mf8-china.com/viewthread.php?tid=20319

感谢R'cube的辛勤翻译

[ 本帖最后由 sokoban 于 2009-1-20 00:32 编辑 ]

sokoban

Twenty-Five Moves Suffice for Rubik's Cube 0803.3435v1.pdf (142.17 KB, 下载次数: 89)

2008-4-25 22:29:32 上传

下载次数: 89

sokoban

总的意思是说: 大量事实表明,3阶魔方的任何一种状态可以在20步内还原.

但是由于魔方的状态太多了,无法用程序穷尽计算所有状态. 只能用近似算法和其他技巧证明25步足够了.