Rubik's Cube的中文名叫魔方，是匈牙利的Rubik教授在1974年发明的智力玩具。多年来，玩具爱好者一直探求魔方的最少的还原步数，2010年有科学研究魔方终极还原最少步数为20.

背景

研究历程

最新进展

背景

魔方作为一个经典的玩具，从1974年诞生到现在为止已经风靡全球。这种玩具的最大魅力就在于将每一面的颜色打乱之后，可以形成数目惊人的颜色组合，一个3×3×3魔方最多可以形成的组合数在理论上超过4325亿亿种。

解魔方也逐渐成为了数学家们的研究项目，最少需要多少次转动可以确保无论什么样的颜色组合都能被复原？这成为了一些数学家求证的难题，而最终答案也被称为“神的步数”（God's number）。

研究历程

早在1981年的时候，“神的步数”被证明为52，在1995年降低至29，之后的每次突破都很艰难。相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家近日利用计算机破解了这一谜团，研究人员证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20。

这支研究团队位于美国加利福尼亚州帕洛阿尔托市。科学家们通过计算机计算和证明，任意组合的魔方都可以在20步内还原。这一结果表明，大约有10万多种的起始状态恰好可以在20步内还原。

利用谷歌公司计算机强大的计算能力，研究人员检验了魔方任何可能的混乱状态(确切数字为43,252,003,274,489,856,000约合4.3×1019)。美国俄亥俄州肯特州立大学数学家莫雷-戴维德森教授也是研究人员之一，他表示，“我们现在可以肯定，这个‘上帝之数’就是20。对于我来说，我也回到了原地。魔方伴随着我成长，这也是我为什么深入研究这个数学问题的原因。这个谜团引起了人们的广泛关注，它也许是人类历史上最受欢迎的谜语了。”科学家们的初步研究成果发表于在线网站上，但戴维德森表示，他们准备将研究成果提交给杂志正式发表。

程序员托马斯-罗基花了15年的时间，致力于寻找这个谜团的答案。据罗基介绍，研究团队所采用的算法可以在1秒钟内尝试10亿种可能，此前的计算机算法1秒钟内只能处理4000种可能。

为了让问题简单化，研究团队采用了一种所谓“群论”的数学技术。他们首先将魔方所有可能的起始状态集分成22亿个集合，每个集合包含了195亿个可能的状态。集合的分配原则是这些可能的状态是如何应对一组10个可能的还原步骤。再通过魔方不同的对称性，这种分组技术使得研究团队将集合数减少到5600万个。

研究人员所采用的算法可以快速将这些还原步骤与恰当的起始点匹配起来，从而实现在20秒内处理一个集合中的195亿种可能。对于普通的家用电脑来说，以这样的速度完成整个处理任务需要大约35年时间。

最新进展

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

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

不过这对于普通玩家来说，20步还原一个三阶魔方应该还是一件很困难的事情。