Twenty-six moves suffice for Rubik's cube
Twenty-six moves suffice for Rubik's cube
复制标题
魔方二十六步就够了
DOI：
10.1145/1277548.1277581
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
G. Cooperman
中科院分区：
文献类型：
--
作者：
D. Kunkle;G. Cooperman
自魔方出现以来，求解魔方的任何状态所需的移动次数一直是一个长期猜测的问题，已经超过25年了。这个数字有时被称为“上帝的数字”。上世纪90年代初，S产生了29的上限(在脸部转向度量中)，随后在2006年产生了27的上限。
改进后的上限为26，使用8000个CPU小时。这一结果的关键之一是魔方数学群中的一种新的快速乘法。另一个关键是使用TB级磁盘存储的高效核外(基于磁盘)并行计算。人们可以使用预计算的数据结构在几分之一秒内为特定的魔方位置产生这样的解。正在进行的工作将使用新的“蛮力逼迫”技术，以进一步缩小界限。
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 out-of-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.