魔方最少还原的问题？
1.在全世界都受欢迎的玩具
1974年春，鲁比克(恩斯特？Rubik)有一个有趣的想法，就是设计一个教学工具，帮助学生直观地理解空间几何中的各种旋转。他想了想，决定做一个由小方块组成的3×3×3的立方体，每个面都可以随意旋转。这样的立方体可以方便地演示各种空间旋转。
这个想法虽然好，但是在实践中面临一个棘手的问题，就是如何让这样一个立方体的各个面随意旋转？鲁比克尝试了很多想法，比如用磁铁或者橡皮筋把小方块连接起来，但是都失败了。那年夏天的一个下午，他正在多瑙河边乘凉，目光不经意间落在了河边的鹅卵石上。突然，一个新的想法闪过他的脑海:用类似鹅卵石表面的圆形表面来处理立方体的内部结构。这个新想法成功了，rubik很快完成了自己的设计，并向匈牙利专利局申请了专利。这个设计就是大家熟悉的魔方，也叫魔方。
6年后，由一位匈牙利商人兼业余数学家领导的魔方(rubik's Rubik's Cube)进入西欧和美国市场，并以惊人的速度成为风靡全球的时尚玩具。之后的25年，魔方销量突破3亿。魔方的玩家中，既有牙牙学语的孩子，也有跨国公司的老板。魔方虽然没有像鲁比克设想的那样成为空间几何的教学工具，但却成为了历史上最畅销的玩具。
畅销魔方的魔力在于它惊人的颜色组合数量。一个魔方出厂时，每一面都有颜色，总共有6种颜色。但是这些颜色被打乱后，可以形成的组合数量高达4325亿个。如果我们把这些组合中的每一个都做成一个魔方，这些魔方就可以从地球到250光年外的遥远星空排列在一起——也就是说，如果我们把一盏灯放在这样一排魔方的一端，光要250年才能照到另一端！如果一个勤奋的玩家想尝试所有的组合，即使不吃不喝不睡，每秒也要10个不同的组合才能得到(作为对比，我们的宇宙目前还不到14亿岁)。相比于这样的组合数字，平日里广告商常用的“几千”、“几亿”、“几十亿”这些虚张声势、忽悠客户的形容词，都成了难得的谦虚。我们可以有把握地说，即使一个人从BIGBANG开始玩魔方，也几乎没有希望还原一个颜色被打乱的魔方。
2.魔方和“神数”
魔方的玩家很多，相互之间有竞争是很自然的。从1981开始，魔方爱好者开始举办世界范围的魔方比赛，从而创造自己的世界纪录。这个记录不断被刷新。截止到2013，还原魔方的最快纪录已经达到了惊人的5.55秒。当然，单个恢复的记录是有一定偶然性的。为了减少这种偶然性，从2003年开始，魔方比赛的冠军由多次回收的平均分来决定。到2013，这个平均成绩的世界纪录是6.54秒。这些记录的出现说明，魔方虽然有天文数字的颜色组合，但只要掌握了窍门，还原任何给定的颜色组合所需的旋转次数很可能并不多。
那么，至少要转多少圈才能保证无论什么颜色组合都能还原呢？这个问题引起了许多人的兴趣，尤其是数学家。恢复任何组合所需的最小旋转数被数学家们戏称为“神数”，而魔方这个玩具界的宠儿也因为这个“神数”一举入侵了学术界。
研究“神数”，当然要先研究魔方的还原方法。在玩魔方的过程中，人们早就知道还原任何给定的颜色组合都是很容易的，这一点已经被无数玩家的优秀记录所证明。而魔方玩家使用的还原方法，虽然人脑很容易掌握，但并没有最少的旋转次数，所以对寻找“神数”没有帮助。寻找旋转次数最少的方法是一道数学难题。当然，这个问题对于数学家来说并不难。早在90年代中期，人们就有了实用的算法，可以在平均约15分钟的时间内，找出还原给定颜色组合的最小旋转数。从理论上讲，如果有人能为每种颜色组合找到这样的最小圈数，那么最大的圈数无疑就是“神数”。但遗憾的是，“4325亿”这个庞大的数字成了人们窥视神数的绊脚石。如果采用上面提到的算法，以上面提到的速度进行搜索，即使同时使用1亿台计算机，也需要654.38+00万年以上才能完成。
看来蛮力是行不通的，于是数学家转而从事他们的老本行:数学。从数学的角度来看，魔方的颜色组合虽然千变万化，但实际上是由一系列的基本运算产生的，也就是旋转，而那些运算也有几个非常简单的特点，比如任何运算都有一个相反的运算(比如与顺时针旋转相反的运算就是逆时针旋转)。对于这样的运算，数学家们的“武器库中”有一个非常有效的工具来应对。这个工具叫群论，出现在魔方出现的140多年前。据说德国数学家戴维·希尔伯特曾经说过，学习群论的关键是选择一个好的例子。自从魔方问世以来，数学家们通过魔方写了几本关于群论的书。所以魔方虽然没有成为空间几何的教学工具，但一定程度上可以作为学习群论的“好榜样”。
对于魔方的研究，群论有一个很重要的优势，就是可以充分利用魔方的对称性。我们前面提到“4325亿”这个庞大的数字时，其实有一个疏漏，就是没有考虑魔方作为立方体的对称性。因此，4325亿种颜色组合中有许多实际上是完全相同的，只是从不同的角度看它们——例如，用不同的面朝上或通过镜子看它们。所以“4325亿”这个令人望而生畏的数字，其实是“掺水的猪肉”。那么，这种“猪肉”中有百分之几的“水”呢？说出来吓唬大家:占了将近99%！换句话说，数学家仅通过对称性就可以将魔方的颜色组合减少两个数量级。
但降低两个数量级仍然远远不足以找到“神数”，因为那不过是把前面提到的654.38+00万年的时间降低到654.38+00万年。对于解决一个数学问题来说，654.38+百万年显然太长了，我们也不指望有人会用一亿台计算机来计算神的数量。数学家虽然聪明，但在其他方面不一定富有。也许他们真正能使用的是他们桌上的电脑。所以，为了找到“神数”，人们需要更多别出心裁的想法。幸运的是，群论工具的力量远没有被用来分析像立方体的对称性这样明显的东西。在它的帮助下，更巧妙的想法很快出现了。
3.寻找“上帝之数”
1992年，德国数学家H. Kochiemba提出了一个新的想法，寻找恢复魔方的方法。他发现，在魔方的基本旋转模式中，有一部分可以形成自己的系列，通过这部分旋转可以形成近200亿种颜色组合。利用这200亿种颜色组合，柯贤巴将魔方的还原分解为两步:第一步，将任意颜色组合转化为那200亿种颜色组合中的一种，第二步，还原那200亿种颜色组合。如果把魔方的复原比作汪洋大海中驶向固定目的地的小船，那么柯贤八提出的200亿种颜色组合就像一个特殊的水域——比那个固定目的地大200亿倍的特殊水域。他提出的两步，就好比让船先驶向那个特殊的水域，再从那里驶向那个固定的目的地。在汪洋大海中找到一个巨大的特殊水域，显然要比直接找到那个小小的目的地容易得多，这也是科善巴新创意的巧妙之处。
即便如此，以柯贤八的新思想，估计“神数”也不容易。特别是为了快速计算，最好在计算机的内存中存储恢复200亿种颜色组合(这相当于那个特殊水域的“地图”)的最少旋转数，大约需要300兆内存。300万亿在今天并不是一个很大的数字，但在科善巴提出新思想的时代，普通电脑的内存远不及它的十分之一。所以直到三年后，才有人用柯贤八的新思想给出了第一个估算结果。他叫迈克尔·里德，是美国中佛罗里达大学的数学家。在1995中，Reid通过计算发现，魔方的任何颜色组合，最多经过12次旋转，就可以转化为Koshenba新思路中的200亿种颜色组合之一。最多18次旋转后，可以恢复200亿种颜色组合中的任意一种。这说明魔方的任何颜色组合最多旋转12+18=30次就可以恢复。
得到上述结果后，里德很快改进了自己的估计，将结果从30个减少到29个，这说明“神”的数量不会超过29个。此后，随着计算机技术的发展，数学家们进一步完善了Reid的结果，但进展并不迅速。直到11年后的2006年，奥地利约翰尼斯·开普勒大学符号计算研究所的博士生席尔武·拉杜才把这个结果推到了27。第二年(也就是2007年)，美国东北大学的计算机科学家丹·昆克尔(Dan Kunkle)和吉恩·库珀(Gene Cooper)把这个结果推到了26。他们的工作采用了并行计算系统，使用了高达700万兆字节的存储空间，消耗了8000小时的计算时间(相当于近一年的24小时不间断计算)。
这些计算表明“神数”不会超过26。然而，所有这些计算的最大优点——即利用了科申巴新思路中的特殊水域——也是它们最致命的弱点，因为它们给出的修复方法必须经过那个特殊水域。但实际上，很多色彩组合的最佳修复方法根本不经过那个特殊的水域。例如，任何靠近目的地但不在特殊水域的船只显然不需要在前往目的地之前故意绕过特殊水域，就像中国大陆和台湾省之间的直航包机一样。因此，利用柯臣巴新思想得到的复原方法未必是最好的，对“神数”的估计也极有可能被高估。
但是，如果不引入克山坝新思路中的特殊水域，计算量又太大怎么办？数学家们决定采取一个折中的办法，那就是扩大那个特殊水体的“面积”。因为特殊水域面积越大，最佳回收路径经过的可能性就越大(当然计算量也会相应增加)。2008年，研究“神数”15年的计算机专家罗基奇，用了一种相当于把科山巴新思想中的特殊水域扩大几千倍的巧妙方法，在短短几个月内对“神数”发起了四次猛烈的攻击，把它的估计值从25降低到22——这就是本文开头提到的人正在研究的东西。Rokic的计算得到了电影特效制作公司Sony Pictures Imageworks的支持，该公司曾为《蜘蛛侠》等著名电影制作特效，并为Rokic提供了相当于50年不间断计算的计算机资源。
由此我们进一步知道“神的数量”一定不能超过22。不过，虽然Rokic在克贤巴的新思路中大大扩展了特殊水域，但还是有一些不经过那个特殊水域的颜色组合的最佳还原方法。所以“神数”很可能小于22。那么，多少钱？种种迹象表明，很有可能是20。这是因为人们多年来的所有努力中，从来没有遇到过任何一种颜色组合必须经过20转以上才能还原，包括Rokic直接计算出的约4000万亿种颜色组合，可见“神”的数量很可能不超过20种；另一方面，人们找到了上万种颜色组合，必须经过20转才能还原，可见“神数”不能少于20。结合这两个方面，数学家们普遍认为“神数”的真实值是20。
2010年8月，这个游戏和数学交织而成的神秘“神数”终于水落石出:研究“神数”的“老手”柯贤巴和“菜鸟”罗基奇，以及另外两位合作者——莫利·戴维森和约翰·迪特里希——公布了他们对“神数”的看法，他们的证明由谷歌提供，相当于英特尔四核处理器35年不间断计算所需的计算机资源。
所以，现在我们可以用数学特有的确定性来宣布“神之数”的数值，那就是:20。