数学家破解"上帝之数" 还原任意魔方仅需要20步

尽管拥有43,252,003,274,489,856,000种不同的可能组合状态，但魔方都可以在20步内还原。

北京时间2010年8月13日消息，据国外媒体报道，相信许多人都玩过魔方，但是此前没有人知道任意组合的魔方的最小还原步数究竟是多少。这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家近日利用计算机破解了这一谜团，研究人员证明任意组合的魔方均可以在20步之内还原，“上帝之数”正式定为20。

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

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

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

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

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

 

 

注1：上文中魔方特指不带图案的3x3x3魔方，其中1步指转动某个面一下（90度，180度，270度都算1步）

注2：以上转自网络，以下原创，转载请注明出处。

 

====================答疑部分==================== 

1. 什么是上帝之数？

说到上帝之数，得从最少步还原说起。对于一个打乱的魔方，有人可能需要100步才能将它还原，有人可能需要60步，这取决于还原的步骤或算法。我们假设上帝还原魔方的时候总是用最少的步骤还原，那这时候我们就想到一个问题，上帝算法在最坏情况下需要几步才能将魔方还原（要知道魔方状态好多好多，打得不够乱的可能上帝只需要5步就还原了，那打得稍微乱一些的，恶心一些的呢）？那么这个数字就被叫做上帝之数。

 

2. 既然所有魔方都可以在20步内还原，为什么上帝之数不可能是19或者更少呢？

其实很简单，因为1995年的时候某大神就找到了一个坑爹状态（就和那堆精心构造的反例似的），通过计算机暴力搜索的办法发现，无论如何也不可能在19步内把它还原，或者说上帝还原这个坑爹状态也得20步，所以很显然上帝之数没法小于20了。

 

3. 那个什么谷歌计算机到底算了多少个状态？

其实精确值是 55,882,296 * 19,508,428,800 个状态，大约占三阶总状态数的1/40，所以其实算法上和暴力破解差得不太多，只不过，按照35CPU年算来，差不多每秒十亿个状态确实很高端霸气上档次（膜拜）。剩下39/40的状态果断用数学方法证明掉了，思路差不多是说，如果解决A类状态的步骤简单变形就能解决B类状态，那A和B类只要暴力求一个。

 

4. 每秒十亿个状态，平均求解一个状态只要1纳秒，如何做到的？

额那主要是因为现在只关心上帝之数是否是20的问题，而不关心具体某个状态的最少步数是多少。一个不是很恰当的比喻是说，比如我找到个状态，它的最少步数是17步，那么很显然这个状态边上3步以内的状态就可以直接pass掉了，反正这些个状态撑死也能在20步内搞定的，至于它们是不是能够在19步内搞定我们根本就不关心，反正它们就算能在18步内搞定，上帝之数也不会小于20（前面说过了），我就不用费那心思去算他们了。

 

答疑部分待续。。。

 

====================干货部分（随手写的，过两天试着详细化一下）====================

1. 首先将魔方状态群根据H(<U, R2, F2, D, L2, B2>)子群分解成 2,217,093,120 个右陪集，其中每个陪集中的元素个数为 19,508,428,800。

2. 利用魔方的对称性（即对于状态A及整体转动S，S^-1 A S和A同解）将陪集的个数降为 55,882,296 ，即约为总量的1/40。

3. 暴力求解每个陪集。

 

其中第三条的算法用到一些trick：

对于给定陪集 R = H * r，使用IDA*算法搜索 R 到 H 的解，则对于每个解 m 有：

r * m = h （其中 h 属于 H）

于是有：

(h' * r) * m = 1 （其中h' = h^-1）

注意到 h 属于 H 子群，所以h'也属于H，于是 h' * r 属于 H * r = R

因此，映射 H -> H * r : f(h) = h' * r 是双射

即选取R中的任何一个状态t，如果t可以在N步内访问H中的所有状态，则说明R中的所有状态可以在N步内还原。

 

实际暴力求解每个陪集的算法为

a) 首先取N=15及R中的某一个元素进行进行IDA*，即标记出可以在15步内访问到的H中的所有状态（结果保存为bitvector的形式，以节省内存）。

b) 直接对这些状态在<U, R2, F2, D, L2, B2>下转动1步（使得转动后的状态依然属于H），将新访问到的状态与15步状态合并，记为16步内可以访问到的状态（事实上16步内可以访问的状态会比标记出来的多，但IDA*的性能远低于直接转动特定状态的性能，为了证明上帝之数为20步不需要那么做）。

c) 重复上述步骤(b)四次，即得到20步内可以访问到的H中的状态的一部分（受限于IDA*，但也足够了）。

d) 此时H基本已经遍历完毕，平均还会剩下几百个状态没有遍历到，将这些状态所对应的R中的状态用二阶段算法搞定之。即证明了整个陪集中的那么多状态都可以在20步内完成。

 

对于大部分陪集，上述算法性能很高，但对于某些恶心的陪集，很有可能c完成后留下了海量没有遍历到的状态，这时候需要改进上述算法，即增加一部分16步的IDA*过程。

计算时间上，计算完a平均需要3.1秒，计算完c平均需要17.4秒，计算完d平均20秒不到，即20秒搞定一个陪集。总共55,882,296个陪集共需要35CPU年。注意到各陪集之间相互独立，上述过程可对不同陪集进行分布式并行计算，最后汇总结果。

据说利用魔方对称性将2,217,093,120个陪集降到55,882,296个并不那么容易，因为H群只是D4h对称群，直接可利用的对称性只有16种，所以采用了一种set cover的技巧。即在H群里找个对称性更强的子群，即Q（<U2, R2, F2, D2, L2, B2>，Oh的对称性），然后将Q*r的个数利用对称性降为原来的1/48左右，最后从H*r中精心寻找一些陪集，完全覆盖所有的Q*r。这么一来，只要搞定所有这些能够覆盖Q们的H，就能证明所有的Q都能在20步内搞定，即证明了所有的状态。

但是由于H比Q大太多，这个覆盖问题计算上搞不定，所以还得引入K和T群，其中K是在H基础上无视角块方向，T是在Q基础上无视角块，然后将K对T进行一个覆盖，并求解每个K所对应的好多个H，最终产生了55,882,296个不同的H（其中K覆盖T的算法还是贪心算法，所以总计算量只是原来的1/40，而不是1/48）