上帝之数

还原任意打乱的魔方所需要的最少步数

上帝之数指还原一个任意打乱的魔方所需要的最少步数。三阶魔方有43,252,003,274,489,856,000（约合4.3×10的19次方）种不同的可能组合状态，但它都能在20步之内还原（最多20步）。这个20，便是（三阶魔方的）上帝之数。

简介

将任意三阶魔方打乱后，最小还原步数究竟是多少？这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家近日利用计算机破解了这一谜团，他们证明任意组合的魔方（三阶魔方有43,252,003,274,489,856,000(约合4.3×10的19次方)种不同的可能组合状态）均可以在20步之内还原。因而，上帝之数=20

具体结果

该团队给出了各种步数的状态总数：

注：该团队还没有计算出后5种的确切数，不过一直在计算。他们会把结果发布在网站上，当然我们也会更新。

最乱状态

所谓最乱状态，就是在和其他状态相比时他的最少步骤步数最多的状态。该团队现在已经给出了部分最乱状态并且给出了打乱公式。需要说明的是在还原得到的某个最乱状态时，不用反着做打乱公式，只需要把公式从头再做一遍就可以了（道理就是该操作的循环的阶是2）。下面列举几个公式：

注：公式中的3表示该面转270°，其实就是逆时针，但是该团队用的是这种表示方式（可能是研究需要，比如数学建模，后边括号中为一般表示方式）

还有一种需要20步的情况与人们的普通感觉不一样。我们总是觉得每个面在正确位置的块越少需要步数越多。但是按照这个公式打乱：RLU2FU'DF2R2B2LU2F'B'UR2DF2UR2U。你会发现8个角块全部正确，棱块位置正确，但是方向反了，这是Michael Reid于1995年发现的一种状态，因为有了这个状态上帝之数的下限在1995年确定为不小于20.

寻找上帝之数

1992 年，德国数学家科先巴(H. Kociemba) 提出了一种寻找魔方复原方法的新思路。他发现，在魔方的基本转动方式中，有一部分可以自成系列，通过这部分转动可以形成将近 200 亿种颜色组合。利用这 200 亿种组合，科先巴将魔方的复原问题分解成了两个步骤：第一步是将任意一种颜色组合转变为那 200 亿种组合之一，第二步则是将那 200 亿种组合复原。如果我们把魔方复原比作是让一条汪洋大海中的小船驶往一个固定的目的地，那么科先巴提出的那两百亿种颜色组合就好比是一片特殊的水域 - 一片比那个固定地点大了 200 亿倍的特殊水域。他提出的两个步骤就好比是让小船首先驶往那片特殊水域，然后从那里驶往那个固定的目的地。在汪洋大海中寻找一片巨大的特殊水域，显然要比直接寻找那个小小的目的地容易得多，这就是科先巴的新思路的优越之处。但即便如此，要用科先巴的方法对 “上帝之数” 进行估算仍不是一件容易的事。尤其是，要想进行快速的计算，最好是将复原那 200 亿种颜色组合的最少转动次数 (这相当于是那片 “特殊水域” 的地图) 存储在计算机的内存中，这大约需要 300 兆的内存。 300 兆在今天看来是一个不太大的数目，但在科先巴提出新思路的那年，普通机器的内存连它的十分之一都远远不到。因此直到三年后，才有人利用科先巴的方法给出了第一个估算结果。此人名叫里德(M. Reid)，是美国中佛罗里达大学(Unversity of Central Florida) 的数学家。 1995 年，里德通过计算发现，最多经过 12 次转动，就可以将魔方的任意一种颜色组合变为科先巴那 200 亿种组合之一；而最多经过 18 次转动，就可以将那 200 亿种组合中的任意一种复原。这表明，最多经过 12+18=30 次转动，就可以将魔方的任意一种颜色组合复原。

这些计算结果表明， “上帝之数” 不会超过 26。但是，所有这些计算的最大优点 - 即利用科先巴的那片 “特殊水域” - 同时也是它们最致命的弱点，因为它们给出的复原方法都必须经过那片特殊水域。可事实上，很多颜色组合的最佳复原方法根本就不经过那片特殊水域，比如紧邻目的地，却恰好不在特殊水域中的任何小船，显然没必要故意从那片特殊水域绕一下才前往目的地。因此，用科先巴的思路得到的复原方法未必是最佳的，由此对 “上帝之数” 所做的估计也极有可能是高估。

可是，如果不引进科先巴的特殊水域，计算量又实在太大，怎么办呢？数学家们决定采取折衷的手段，即扩大那片特殊水域的 “面积”，因为特殊水域越大，最佳复原路径恰好经过它的可能性也就越大 (当然，计算量也会有相应的增加)。 2008 年，研究 “上帝之数” 长达 15 年之久的计算机高手罗基奇 (T. Rokicki) 运用了相当于将科先巴的特殊水域扩大几千倍的巧妙方法，在短短几个月的时间内对 “上帝之数” 连续发动了四次猛烈攻击，将它的估计值从 25 一直压缩到了 22。这是当时全世界范围内的最佳结果。罗基奇的计算得到了电影特效制作商索尼影像 (Sony Pictures Imageworks) 的支持，这家曾为 “蜘蛛人” 等著名影片制作特效的公司向罗基奇提供了相当于 50 年不停歇计算所需的计算机资源。

与此同时，科学家们发现了一种已知的最混乱状态——superflip。在Superflip这种状态中，每个魔块的位置都是对的，除了每个棱块都是翻转反向的。这种形态已被证明不可能用小于20种方法还原，因此上帝之数一定大于等于20，也有不少的研究人员预测，上帝之数就是20。

2010年7月，美国加利福尼亚州科学家征用到了更加强大的资源——谷歌旧金山总部的超级主脑计算机。随着程序的精简和设备的提升，这量配置惊人的计算机破解了这一谜团。研究人员利用计算机，用枚举法验证了每一种情况，证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20。

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

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

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

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

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

魔方与数学

1974 年春天，匈牙利布达佩斯应用艺术学院(Budapest College of Applied Arts) 的建筑学教授鲁比克(E. Rubik) 萌生了一个有趣的念头，他想设计一个教学工具来帮助学生直观地理解空间几何的各种转动。经过思考，他决定制作一个由一些小方块组成的，各个面能随意转动的 3×3×3 的立方体。这样的立方体可以很方便地演示各种空间转动。

随后魔方风靡全球，其原因最大的魔力就在于其数目惊人的颜色组合。一个魔方出厂时每个面各有一种颜色，总共有六种颜色，（一般为：黄、白、绿、蓝、红、橙）但这些颜色被打乱后，所能形成的组合数却多达 4325 亿亿个（注意确实是两个亿字）。如果我们将这些组合中的每一种都做成一个魔方，这些魔方排在一起，可以从地球一直排到 250 光年外的遥远星空。也就是说，如果我们在这样一排魔方的一端点上一盏灯，那灯光要在 250 年后才能照到另一端。如果哪位勤勉的玩家想要尝试所有的组合，哪怕他不吃、不喝、不睡，每秒钟转出十种不同的组合，也要花 1500 亿年的时间才能如愿 (作为比较，我们的宇宙目前还不到 140 亿岁)。与这样的组合数相比，广告商们常用的 “成千上万”、 “数以亿计”、 “数以十亿计” 等平日里虚张声势、忽悠顾客的形容词反倒变成了难得的谦虚。我们可以很有把握地说，假如不掌握诀窍地随意乱转，一个人哪怕从宇宙大爆炸之初就开始玩魔方，也几乎没有任何希望将一个色彩被打乱的魔方复原。

魔方与上帝之数

魔方的玩家多了，相互间的比赛自然是少不了的。自 1981 年起，魔方爱好者们开始举办世界性的魔方大赛，从而开始缔造自己的世界纪录。这一纪录被不断地刷新着，到本文写作之时为止，复原魔方的最快纪录 - 如我们在本文开头提到的 - 已经达到了令人吃惊的 3.47秒。当然，单次复原的纪录存在一定的偶然性，为了减少这种偶然性，自 2003 年起，魔方大赛的冠军改由多次复原的平均成绩来决定，目前这一平均成绩的世界纪录为 5.80秒。这些记录的出现，表明魔方虽有天文数字般的颜色组合，但只要掌握窍门，将任何一种组合复原所需的转动次数却并不多。

那么，最少需要多少次转动，才能确保无论什么样的颜色组合都能被复原呢？这个问题引起了很多人，尤其是数学家的兴趣。这个复原任意组合所需的最少转动次数被数学家们戏称为 “上帝之数” (God's number)，而魔方这个玩具世界的宠儿则由于这个 “上帝之数” 一举侵入了学术界。

要研究 “上帝之数”，首先当然要研究魔方的复原方法。在玩魔方的过程中，人们早就知道，将任意一种给定的颜色组合复原都是很容易的，这一点已由玩家们的无数杰出纪录所示范。不过魔方玩家们所用的复原方法是便于人脑掌握的方法，却不是转动次数最少的，因此无助于寻找 “上帝之数”。寻找转动次数最少的方法是一个有一定难度的数学问题。当然，这个问题是难不倒数学家的。早在二十世纪九十年代中期，人们就有了较实用的算法，可以用平均十五分钟左右的时间找出复原一种给定颜色组合的最少转动次数。从理论上讲，如果有人能对每一种颜色组合都找出这样的最少转动次数，那么这些转动次数中最大的一个无疑就是 “上帝之数”。但可惜的是， 4325 亿亿这个巨大的数字成为了人们窥视 “上帝之数” 的拦路虎。如果采用上面提到的算法，哪怕用一亿台机器同时计算，也要超过一千万年的时间才能完成。

看来蛮干是行不通的，数学家们于是便求助于他们的老本行：数学。从数学的角度看，魔方的颜色组合虽然千变万化，其实都是由一系列基本的操作 (即转动) 产生的，而且那些操作还具有几个非常简单的特点，比如任何一个操作都有一个相反的操作 (比如与顺时针转动相反的操作就是逆时针转动)。对于这样的操作，数学家们的军火库中有一种非常有效的工具来对付它，这工具叫做群论 (group theory)，它早在魔方问世之前一百四十多年就已出现了。据说德国数学大师希尔伯特(D. Hilbert) 曾经表示，学习群论的窍门就是选取一个好的例子。自魔方问世以来，数学家们已经写出了好几本通过魔方讲述群论的书。因此，魔方虽未成为空间几何的教学工具，却在一定程度上可以作为学习群论的 “好的例子”。

对魔方研究来说，群论有一个非常重要的优点，就是它可以充分利用魔方的对称性。我们前面提到 4325 亿亿这个巨大数字时，其实有一个疏漏，那就是并未考虑到魔方作为一个立方体所具有的对称性。由此导致的结果，是那 4325 亿亿种颜色组合中有很多其实是完全相同的，只是从不同的角度去看 (比如让不同的面朝上或者通过镜子去看) 而已。因此， 4325 亿亿这个令人望而生畏的数字实际上是 “注水猪肉”。那么，这 “猪肉” 中的 “水份” 占多大比例呢？说出来吓大家一跳：占了将近 99%！换句话说，仅凭对称性一项，数学家们就可以把魔方的颜色组合减少两个数量级。

但减少两个数量级对于寻找 “上帝之数” 来说还远远不够，因为那不过是将前面提到的一千万年的时间减少为了十万年。对于解决一个数学问题来说，十万年显然还是太长了，而且我们也并不指望真有人能动用一亿台计算机来计算 “上帝之数”。数学家们虽然富有智慧，但在其它方面却不见得很富有，他们真正能动用的也许只有自己书桌上的那台机器。因此为了寻找 “上帝之数”，人们还需要寻找更巧妙的思路。幸运的是，群论这一工具的威力远不只是用来分析象立方体的对称性那样显而易见的东西，在它的帮助下，新的思路很快就出现了。

革命尚未成功

目前只是找到了三阶魔方的上帝之数，但是4阶及以上，还有许多经典的异形的上帝之数还没有解决，看到三阶解决历程，可以想象找出所有魔方的上帝之数是对人类智慧的一大考验。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省