35年CPU时间证实解魔方“神的步数”为20

ugmbbc发布于 2010-08-11 14:53:28|14444 次阅读 字体：大 小 打印预览


魔方作为一个经典的玩具，从1974年诞生到现在为止已经风靡全球。这种玩具的最大魅力就在于将每一面的颜色打乱之后，可以形成数目惊人的颜色组合，一个3×3×3魔方最多可以形成的组合数在理论上超过4325亿亿种。解魔方也逐渐成为了数学家们的研究项目，最少需要多少次转动可以确保无论什么样的颜色组合都能被复原？这成为了一些数学家求证的难题，而最终答案也被称为“神的步数”（God's number）。


近日有研究小组宣布，“神的步数”研究已经有了新的进展，目前这个数字被定格到20。也就是说，无论什么样组合的三阶魔方，都可以在20步以内进行还原。这个数字是使用了由Google捐赠的闲置CPU资源进行计算的，总的CPU时间约为35年。

研究者们将4325亿亿种初始组合状态分为了2,217,093,120组，然后再利用对称性集合覆盖将总状态缩小至55,882,296组，在计算机上运行的解魔方算法可以在20秒内还原一组，最后完成整个工程大约耗费了35年的CPU时间。

早在1981年的时候，“神的步数”被证明为52，在1995年降低至29，之后的每次突破都很艰难。不过这对于普通玩家来说，20步还原一个三阶魔方应该还是一件很困难的事情。