在所有益智游戏中，魔方是当之无愧的王者。魔方从发明至今已风魔全球三十多年，人们却一直乐此不疲，不断探索魔方提出的问题。
魔方是人类发明的所有益智游戏中的佼佼者。首先，其他任何游戏都没能吸引如此多的关注，引来众人发表诸多相关文章和书籍，讨论其中奥妙。其次，魔方颇具难度，数百万人开展各种竞赛，屡创壮举……这些成就愈显奇特，甚至接近疯狂。同时，魔方启发了数百种机械益智游戏，衍生游戏往往和魔方一样惊人。现在，我们也可以在电脑上进行模拟操作。最后，三十年来，最复杂形态的问题一直无解，唯有强大的计算机网络或许才能最终将之破解。
我们还会细谈这四个话题，尤其要讲讲已经证实的结论：在任何情况下，20 步足以将魔方不同颜色的 6 个面还原。
巧妙的机械结构
在 1980 年 8 月出版的法国《为了科学》（Pour la Science）杂志第 34 期里，埃马努埃尔·哈伯斯塔特发表了题为“匈牙利方块及群理论”（Le cube hongrois et la théorie des groups）的文章，在其中描述了魔方，并基于魔方数学结构分析提出一种还原魔方的实用方法。
这篇文章让魔方在法国风靡一时，而人们对魔方的痴迷早已快速席卷世界各地。
回溯到此前六年，雕塑家及建筑学教授埃尔诺·鲁比克发明了由 26 个通过巧妙机械结构相连的小方块组成的魔方。魔方各面由 9 个方块（3×3）构成，每面均可绕着平行于棱且经过面中点的轴旋转。这本该是一个完整的 3×3×3 立方体，但中心位置的方块却替换为转轴系统，使整体既相互连接，又能转动。魔方处在初始形态时，各面都仅有一种颜色，总共是蓝、红、橙、绿、黄、白六种。把魔方各面拧几下，不同颜色的方块被打乱，问题就是怎样将魔方还原到初始形态。
试着摆弄几下，我们就能理解这个益智游戏结构的一些基本要素。
每个面的中心块绕着自身旋转，位置不变。它们决定着每个面的颜色，可以准确地表示立方体的方向。
角块一共有 8 个，一直在顶点位置。每个角块有 3 个颜色不同的可见面，考虑魔方每个面中心块的颜色，可以准确判定一个角块在魔方还原后所处的位置。
剩下 12 个就是棱中间的棱块。每个棱块有两种不同颜色的可见面，和角块一样，可以准确判定棱块在最终形态中所处的位置。
1魔方的最难形态，为了证明 20 步总能足以将魔方还原，人们在运算过程中得出这种极致形态。图中将 20 个还原步骤一一画出。你可以照着图反向操作，给自称魔方高手的亲朋好友出个难题。
还原魔方看起来简单，实际却是块难啃的骨头。魔方一旦被打乱，在没有任何帮助或从未对魔方背后的数学问题进行过深入研究的情况下，任凭怎么努力也不可能将它还原。这个游戏实在太难了，它能大受欢迎也耐人寻味。
自 1977 年第一批魔方在匈牙利上市以来，大约有 3 亿 5 千万个魔方被生产和销售。魔方打败各类益智游戏，成为各历史阶段的销量冠军——唯一的例外也许是Taquin（也叫作“15 块拼图”）。自 1879 年问世以来，Taquin 游戏衍生出数千种不同版本，我们无法统计到底一共制造、销售了多少。尽管魔方被造假者无耻地剽窃、复制，魔方还是为其发明者埃尔诺·鲁比克收获了财富和荣誉，让他可以在后半生专心发明并制作其他益智游戏。
人们围绕魔方的构造理论和解答方法出版和发表了众多书籍和文章。在互联网上也有大量专门讲解魔方的网页。每年涌现的大量文献可追溯到 20 世纪 80 年代，那时，人们对魔方的热情几近狂热。乔治·赫尔姆斯编纂的文献收录了 22 种语言的 719 篇文章。1979 年有 14 篇著作发表、1980 年 52 篇、1981 年 174 篇、1982 年 70 篇、1983 年 15 篇。詹姆斯·诺斯的著作《魔方的简单解法》（The Simple Solution to Rubik's Cube）是 1982 年 1 月全球销量最大的图书，在畅销书排行榜上停留三年之久，总共卖出了逾六百万册。另有多本魔方书籍的销量都超过了百万册。
世界各地都在举办魔方竞赛。世界魔方协会（WCA）为众多比赛提供赞助。
最厉害的魔方玩家不到 10 秒就能还原 3×3×3 魔方。有一点要说清楚，世界魔方协会的规则允许在开始拧魔方之前先观察 15 秒。15 岁的澳大利亚冠军菲利克斯·曾姆丹格斯平均用 8.5 秒就能将魔方还原。他也能解决更难的 4×4×4 魔方，平均耗时 42 秒；还有极难的5×5×5魔方，平均耗时 68 秒。
有些记录没那么正规，但也成为了经典战绩，像体育竞赛纪录一样不断被刷新。2010 年的单手拧魔方冠军用时 14.7 秒。脚拧魔方冠军用时 42 秒。2008 年 11 月 16 日，米兰·巴提克用不到 24 小时的时间复原了 4786 个魔方，打破之前 3505 个魔方的纪录。值得一提的是，巴提克连续 24 小时成功保持了每个魔方平均耗时 18.05 秒的惊人速度！
2魔方主义画派：这些画作由 9 种像素块构成，艺术家用足够多的魔方，将 其一面拧成不同颜色的 9 个像素块，用 6 种颜色耐心拼成整幅作品。类似作品 可以在www.space-invaders.com/archives.html看到。
魔方盲拧更加不可思议。玩家对魔方进行观察之后，蒙上眼睛拧转魔方。2010 年的盲拧冠军庄海燕包括观察步骤的整个操作过程只用了 31 秒。盲拧魔方数量的世界纪录属于印度尼西亚人穆哈默德·伊里勒·凯鲁·阿纳姆。2010 年，他在观察魔方后蒙上眼睛，于规定的一小时内逐一还原了 16 个魔方。
最年轻的魔方玩家在成绩被认可时只有 4 岁。年纪最大的玩家高龄 88 岁。魔方盲拧的难度更大，玩家年龄纪录分别是 10 岁和 60 岁。
玩魔方的成就感在于把玩时体验到的乐趣。仅由磁铁吸在一起的八方块立方体益智游戏比魔方还早几年诞生，它与魔方类似，却更为简单。磁铁吸附的方块很容易被拆下，而非只能转动变换位置，因此，玩家可以投机取巧，游戏也未能引起轰动。魔方的天才创意在于机械创新，而非数学创意。
在魔方各类卓然出众的变体中，空心魔方堪称奇迹。空心魔方的外观和转动方式与魔方相同，只是魔方用于运转的所有构件都消失了：立方体中心和每个面的中心都是空的，仅剩下 8 个角块和 12 个棱块，就能完全像魔方那样移动（参见下图）。缔造魔方神话的精巧机械结构就这样被超越了！如果你想尝试研究魔方的各种变体，且不想一一购买，可以通过网上的免费小程序就模拟操作（特别推荐：www.randelshofer.ch/rubik/index.html）。
数一数还原魔方的步骤
很容易看出，15 步不足以将任意形态的魔方恢复原状。魔方的6个面都可以转动 90 度、180 度或 270 度，因此，魔方每转动一次（一个面的旋转）共有 18 种选择。转动一次可以变出 18 个形态，转动两次，最多可以变出 18×18 ＝ 182个不同的形态，依次类推。如果最多转动 15 次，可变出的不同形态数目小于或等于：18+182+183+184+…+1815=7.1435×1018。
不过，这一数字却小于魔方可变出的形态总数，即 4.3×1019。所以，如果最多只转动 15 次，我们无法变出所有可能形态。如果魔方处于一个无法只用 15 步拧成的形态，恐怕需要至少转动 16 步才能还原。进一步推理指出，某些形态需要至少 17 步还原。
能将魔方还原已经很不错，如果能用最少的转动步数将魔方还原，就更好了……当然，难度也更大。世界魔方协会设立了一个竞赛，衡量参赛者们节省转动步骤的能力，规则如下：
(a) 参赛者有一小时时间观察并仔细研究被打乱的魔方，必要时，可以借助铅笔、纸张、三个辅助魔方和有颜色的小胶条；
(b) 一小时后，参赛者将自己找到的最优转动步骤按标准记录方法写下来。
解法的长度即面的转动次数，一次转动也可以是四分之一圈或者半圈。2010 的冠军是匈牙利人伊斯特万·柯察——看看！又是匈牙利人！他用 22 步转动还原了试题中打乱的魔方。值得注意的是，这个数字确实已经很小了。书籍或各种网页里介绍的魔方还原方法大约需要 60 步，一些更难学的最佳方法也要 30 步。柯察取得 22 步的优异成绩，并不是因为 2010 年的题目碰巧简单。2009 年，该项竞赛的冠军也用了 22 步，2011 年的纪录是 25 步，2012 年为 20 步，2013 年为 21 步。参赛者在不断进步，随之也出现一个问题：能否总用 22 步或者更少的步数还原魔方？更确切地说，顶级参赛者面对最坏情况时要转动多少步？
当纯理论遇上实际困难
长久以来，人们怀疑终极答案是 20 步。2010 年 7 月，该结论被证实确凿。魔方转动步数的研究可以归结为某些数学群的研究，所以，我们曾认为依靠不断完善的数学知识能揭开谜底。我们所研究的魔方结构不包含任何随意性。这和国际象棋的例子恰恰相反。国际象棋拥有复杂的规则，可能出现的棋局图像十分繁复难懂。在这里，我们用图来表示魔方问题的结构（参见“魔方的图论”），并用十分简单的几何元素加以定义。对数学家来说，这似乎是比较理想的状态，他们可以尽情施展才华，依赖群、群的分类、群的分解等数学知识得出答案。然而，没有得出任何结果，纯理论方法最终被证明是不可行的！
4. 魔方的图论
我们将魔方所有可能形态用图示表达出来。图的节点是4.3×1019种可能的形态，若两个形态可以通过魔方一个面的一次旋转相互转化，相应两个节点由一条弧连接。
我们无法完整呈现这幅图。魔方图具有高度的对称性，因为所有节点都相互等价，与立方体顶点图的情况相似。寻找还原魔方最优转动步骤就转化为如何在该图中找到最短路径。寻找还原最难形态所需的最多转动步数等价于寻找距初始形态最远的形态，基于本图的对称性，问题又转化为寻找图的直径，即图中两个节点之间的最大距离。
由于图太大，在图中无法直接应用一般算法（计算最短路径和直径，等等），即便使用强大的计算机网络也是如此。通过改造算法并尽可能利用图的特殊性质，才能算出图的直径。
研究者们采用了如下想法：为了计算A和B两个位置之间的一条短路径，可以选取距A不太远的形态C，然后找出A和C之间的最短路径以及B和C之间的最短路径。将这两条最短路径相连，未必能得出A和B之间的最短路径，但已能得出足够好的结果。另外，通过变换C，能基本确定A和B之间的最短路径。
对魔方图直径问题的研究已有三十年之久，却进展缓慢，直到2010年7月才证明直径等于20。为了感受一下进展速度，让我们回顾一下关键日期、证明者姓名及其得出的直径：1981年7月摩温·希斯特斯维特得出52，1993年4月汉斯·克鲁斯特曼得出42，1992年5月迈克尔·瑞德得出39，1992年5月迪克·温特得出37，1995年1月迈克尔·瑞德又得出小于29且大于20，1995年12月斯尔夫·拉度得出28，2006年4月斯尔夫·拉度又得出27，2007年5月丹·康克勒得出26，2008年3月托马斯·洛基奇又得出23，2008年8月进一步得出22，2010年7月托马斯·洛基奇、赫伯特·科辛巴、莫雷·戴维森和约翰·戴斯里奇最终证明直径等于20。
伴随最后一个结果的诞生，人们得出下面的列表，指出了与初始形态相距给定距离的节点数量。列表中最后几行是近似结果。
20 步，这个答案最终通过一系列算法的拓展研究才得以证实，前后历时二十年。人们必须借助强大的运算能力才能修成正果，相当于一台台式电脑不间断工作 35 年。研究人员动员业界巨头谷歌公司出借一批计算机，花了几周时间才完成运算。
打乱魔方可以得到的形态数量是 4300 亿亿。除了转动，如果将魔方拆卸再随意重组，形态数量就会翻 12 倍，那么，仅有十二分之一的概率能将魔方还原。魔方的这一性质和 Taquin 游戏类似：将 Taquin 拆卸并随意拼回图形，只有二分之一的概率能找回初始位置。
我们可以逐一处理 4.3×1019个可能形态，找到最佳转动步骤将魔方还原。赫伯特·科辛巴自 1992 年就开始研究这个问题，并找出了优越的算法。多亏了他，找到给定魔方形态的最少还原步骤不再是梦想。对于给定形态，强大的机器通常也需要好几秒钟才能找到最优转动步骤。采用每秒处理一个形态的算法，计算每一个形态的最优转动步骤，最终找出魔方最复杂的形态，这需要调动现今地球上存在的全部十亿台计算机一起工作 1300 多年。强使蛮力也无法给出答案。
另一个办法主张逐步处理，记住所得结果，并将其重复利用。观察一步转动能够得出的所有形态（一共 18 个），将一步转动所得形态的相关信息列出。从这些形态出发，进行下一步所有可能的转动，此后，再将两步得到全新形态的相关信息记录下来。
以相同方式继续，我们渐渐记录下达到所有可能形态的最短路径信息（因为，当我们第一次生成一个形态时，不可能有更短的转动步骤来得到它）。当最新一步计算无法再产生新形态时，终止算法。我们确信，能够得到所有最短路径的长度，同时，找到所需还原步骤最多的魔方形态。
理论上，这个方法更好地利用了已逐步保存的计算结果，比上一个方法速度更快。然而，由于信息存储量过大，此法依然不可行。想要完成刚刚描述的算法，逐步计算所有最短路径，所需存储量是地球上所有计算机硬盘的存储量总和，数量级为 1021字节！
算法的功劳
在过多运算和过大存储之间，必须找一个折中的办法。托马斯·洛基奇、科辛巴、莫雷·戴维森和约翰·戴斯里奇找到一个办法，证明了 20 步就是将魔方从最复杂形态还原所需的转动步数。他们通过长期研究和一系列改进措施，希望限制问题的复杂性，同时，利用一台现代化计算机的存储和计算能力，确保绝不超出当今技术的极限。
3魔方最经典的变体是 2×2×2 魔方、4×4×4 魔方的复仇、5×5×5 教授魔方。这些都是世界魔方协会的竞赛项目。2008 年上市的 6×6×6 魔方和 7×7×7 魔方体积最大。2×2×2 魔方的形态总数是 3 674 160 种，3×3×3 是 4.3×1019种，4×4×4 是 7.4×1045种，5×5×5 是 2.8×1074种，6×6×6 是 1.57×10116种，7×7×7 是 1.95×10160种。这已经超过了可见宇宙中信息量的比特数！魔方的数十种变体风靡全球，包括给视障人群的盲文版魔方。
利用问题的对称性可以略微减小运算规模。此外，将问题分解成数量众多的子问题，凭借类似上述渐进法的办法，一台计算机的存储能力就足以完成整体处理。于是，问题就被分解成 2 217 093 120 个子集，各自包含 19 508 428 800 种形态。再次利用对称性，所要处理的子集数量还可减少到 55 882 296 个。
最复杂情况至少需要 20 步完成，科辛巴算法的一个变体正是利用了这个信息。从 1995 年起，人们便知道少于 20 步无法还原某些形态。因此，对于给定形态，只要找到一个小于 20 步的解法，即便不是最优方法，我们就不再费力寻找更简短的路径了。
为了证明“20 步足以还原最复杂形态”，冗长的运算还得出了另外一些有趣的信息。比如，所需步数的平均值为 17.7 步。需要 20 步才能还原的复杂形态比较少见，大约有 3 亿种。这意味着，如果随机抽取，出现这种复杂形态的概率少于一千亿分之一。这些信息让我们认识到，能够用 22 步还原魔方的魔方达人已经十分接近完美境地，着实值得称赞。然而，尽管他们做出了巨大努力，经历了艰苦训练，却仍然无法发现最优的转动步骤。
曾几何时，这个有着三十余年历史的游戏向全体计算机科学家们宣战，研究者们费尽心思才解决了最复杂形态的问题。魔方也要挑战数学家。目前，面对这个简单的纯代数抽象问题，数学家们只能听任机器摆布，勉强接受一个任何数学理论家都无法质疑、却也无法手工验证的结论。
【相关图书】
作者：让-保罗·德拉耶
译者：路遥
本书揭开趣味游戏、艺术设计和日常生活中的数学密码，通过新颖话题和精美图示展现算术与几何中隐藏的妙趣，从最简单的数学原理走入算法的精彩世界，展现算法破解数学谜题的无穷威力。本书适合所有数学爱好者阅读。
【作者简介】
让-保罗·德拉耶 | Jean-Paul Delahaye
法国数学家和计算机科学家，数学科普作家，现任法国里尔科技大学计算机技术教授，法国国家科学研究院（CNR）计算机基础科学实验室研究员，主要研究逻辑编程、偶然性和游戏的算法原理。
