在美国宾夕法尼亚州Doylestown举办的“世界魔方协会(WCA)官方挑战赛”上,一位名叫Collin Burns的年轻人创下了5.25秒的新世界纪录。现在许多中小学兴趣课都会安排魔方大赛。魔方大概是现在最有影响力的智力游戏了，它是一个3×3×3的正方体，初始状态下每个面的9个方格都涂上同样颜色，6个面一共6种颜色。
大概一年前，Google的一帮人验证了任意拧乱的魔方可以在20步内复原。但是，一般人要在20步内复原任意魔方的话，就要记住一个硕大无比的表格（大约8EB，一EB大约是一百万TB），这东西只有拥有全知全能的上帝及其类似物（比如说团长、春哥或者高斯）才能做到，所以20这个数又被称为魔方的“上帝之数”。
魔方当然不只有一种。原版的魔方是3阶的，也就是3×3×3的立方体。我们可以扩展到4阶（4×4×4），5阶，一直到7阶，甚至有人目击过11阶的魔方。魔方的阶数越大，解起来也越复杂，需要的步数也越多，它们的上帝之数也越大而且越难计算。
现在，一帮在MIT的由Erik Demaine领衔的数学家，竟然说他们找到了任意阶数魔方的上帝之数，而且还给出了一个复原的算法，需要的步数与上帝之数相差不远！我们现在就来看个究竟。
怎么转都转不出那24个陷阱
初看起来，魔方每个面可以拧得千变万化，让人无从捉摸。然而对于魔方面上涂色的小方块来说，它们可去的地方并不多（假设我们能做的操作就是将魔方的某排拧动90度）.
由24个位置组成的一个位置群
无论魔方被如何拧动，图中所示的小色块一共只能到达最多24个位置。我们把这些位置称作一个位置群。一个n阶的魔方，不算边角上的色块，只有大约(n-2)²/4个位置群。这些位置群都是相互独立的。要复原魔方，就相当于要将所有位置群复原。
Demaine从玩魔方的人们那里了解到，有标准的手法可以单单将一个位置群内的小色块复原，而不影响别的位置群的色块。这就是为什么我们说这些位置群是独立的。而因为每个位置群内色块的数目都是固定的（不多于24个），所以要复原一个位置群里的所有色块，只需要固定步数的操作。这些知识，魔方社区早就一清二楚。
但是，如果单靠这种方法来解n阶魔方的话，因为至少有(n-2)²/4个位置群，所以用这种方法复原魔方需要的步数大约与n²成正比。有没有可能用更少的步数复原魔方呢？复原所有魔方的步数有没有下限呢？
上帝之数不能太小
为了方便，我们记n阶魔方的上帝之数为D(n)。他们首先证明了，对于足够大的n，D(n)不能太小，至少是c×n²/ln(n)，其中c是一个常数。这个计算并不太难，我们就一起来试试看。对于足够大的n，我们大约有n²/4个位置群，它们各自有24个不同位置的小色块。在这24个色块中，6种颜色分别各有4个，这是初始状态决定的。用一点简单的组合知识就可以知道，我们一共有(24!)/(4!)⁶种方法打乱一个位置群中的色块。因为位置群之间是独立的，所以魔方至少有 (24!)/(4!)⁶ (n-2)²/4 种不同的打乱方式（还没算边角排列的各种可能性）。
由上帝之数的定义，我们可以在D(n)步内将任意魔方复原。如果我们将这些复原的步骤倒过来操作，这其实就意味着我们可以用至多D(n)步将魔方打乱到所有可能的打乱方式。每一步我们有(6n+1)种操作，每次操作就是将某一排拧上90度，另外复原后举起魔方炫耀然后被打倒在地踩上一万只脚也算一次操作，可以爬起来然后多次重复这项操作。所以魔方至多有 (6n+1) D(n) 种打乱方式，因为某些系列操作会导致同样的打乱结果。
我们就有了以下的不等式：
从这个不等式我们可以得到：
当n趋向于无穷大的时候，上面那个看起来很复杂的量就跟 c×n²/ln(n) 差不多了，其中c大约是35.7164。
可能我们做不到在 c×n²/ln(n) 步内还原任意的n阶魔方，但是能不能提出一种方法，即使还原的步数稍多一点，但是起码增长速度跟 n²/ln(n) 一样呢？
互搭便车的暴力复原方法
可能是经济危机中人们的各种节俭方式（拼车之类的）启发了Demaine，他想，虽然位置群之间是相互独立的，但是也许可以将不同位置群的复原操作兼并起来，一次拧动同时解决多个位置群的问题。如果说原来的复原方法是每个位置群各自为政，各自拥有一条复原线路的话，Demaine他们的方法就相当于建起了一条公交线路，一次将多个位置群送到彼岸。
利用这个方法，他们给出了一个算法，可以在c'×n²/ln(n)步内还原任意的n阶魔方。在这里c'是另一个常数，它比c大得多。
在一些必要的预处理（比如说先解决边角问题）后，Demaine他们将魔方的所有位置群大约平均地分成n/4份，通过巧妙地应用上面的引理，使每次中枪的都是固定的几个位置群。当所有其它的位置群都被复原后，剩下满身弹孔（认识QB的同学请自行脑补）的“中枪专用位置群”数目也不多，可以用传统的方法一个一个解决。整个过程所需要的步数，恰好差不多正比于 n²/ln(n) ，与最优的可能性只差一个乘法常数。这种过于暴力的方法，也是使常数c'变得很大的原因之一。
这个结果在魔方界也引起了不少人的兴趣。据某些魔方高手所言，Demaine他们的“差一个常数最优”的算法过程，对他们探索解高阶魔方的快速方法相当有启发，只是观摩已经满足不了他们了。
讲了这么概念性的东西，最重要的还需要同学动手实践哦。你能在多长时间内还原魔方呢？
大概一年前，Google的一帮人验证了任意拧乱的魔方可以在20步内复原。但是，一般人要在20步内复原任意魔方的话，就要记住一个硕大无比的表格（大约8EB，一EB大约是一百万TB），这东西只有拥有全知全能的上帝及其类似物（比如说团长、春哥或者高斯）才能做到，所以20这个数又被称为魔方的“上帝之数”。
魔方当然不只有一种。原版的魔方是3阶的，也就是3×3×3的立方体。我们可以扩展到4阶（4×4×4），5阶，一直到7阶，甚至有人目击过11阶的魔方。魔方的阶数越大，解起来也越复杂，需要的步数也越多，它们的上帝之数也越大而且越难计算。
现在，一帮在MIT的由Erik Demaine领衔的数学家，竟然说他们找到了任意阶数魔方的上帝之数，而且还给出了一个复原的算法，需要的步数与上帝之数相差不远！我们现在就来看个究竟。
怎么转都转不出那24个陷阱
初看起来，魔方每个面可以拧得千变万化，让人无从捉摸。然而对于魔方面上涂色的小方块来说，它们可去的地方并不多（假设我们能做的操作就是将魔方的某排拧动90度）.
由24个位置组成的一个位置群
无论魔方被如何拧动，图中所示的小色块一共只能到达最多24个位置。我们把这些位置称作一个位置群。一个n阶的魔方，不算边角上的色块，只有大约(n-2)²/4个位置群。这些位置群都是相互独立的。要复原魔方，就相当于要将所有位置群复原。
Demaine从玩魔方的人们那里了解到，有标准的手法可以单单将一个位置群内的小色块复原，而不影响别的位置群的色块。这就是为什么我们说这些位置群是独立的。而因为每个位置群内色块的数目都是固定的（不多于24个），所以要复原一个位置群里的所有色块，只需要固定步数的操作。这些知识，魔方社区早就一清二楚。
但是，如果单靠这种方法来解n阶魔方的话，因为至少有(n-2)²/4个位置群，所以用这种方法复原魔方需要的步数大约与n²成正比。有没有可能用更少的步数复原魔方呢？复原所有魔方的步数有没有下限呢？
上帝之数不能太小
为了方便，我们记n阶魔方的上帝之数为D(n)。他们首先证明了，对于足够大的n，D(n)不能太小，至少是c×n²/ln(n)，其中c是一个常数。这个计算并不太难，我们就一起来试试看。对于足够大的n，我们大约有n²/4个位置群，它们各自有24个不同位置的小色块。在这24个色块中，6种颜色分别各有4个，这是初始状态决定的。用一点简单的组合知识就可以知道，我们一共有(24!)/(4!)⁶种方法打乱一个位置群中的色块。因为位置群之间是独立的，所以魔方至少有 (24!)/(4!)⁶ (n-2)²/4 种不同的打乱方式（还没算边角排列的各种可能性）。
由上帝之数的定义，我们可以在D(n)步内将任意魔方复原。如果我们将这些复原的步骤倒过来操作，这其实就意味着我们可以用至多D(n)步将魔方打乱到所有可能的打乱方式。每一步我们有(6n+1)种操作，每次操作就是将某一排拧上90度，另外复原后举起魔方炫耀然后被打倒在地踩上一万只脚也算一次操作，可以爬起来然后多次重复这项操作。所以魔方至多有 (6n+1) D(n) 种打乱方式，因为某些系列操作会导致同样的打乱结果。
我们就有了以下的不等式：
从这个不等式我们可以得到：
当n趋向于无穷大的时候，上面那个看起来很复杂的量就跟 c×n²/ln(n) 差不多了，其中c大约是35.7164。
可能我们做不到在 c×n²/ln(n) 步内还原任意的n阶魔方，但是能不能提出一种方法，即使还原的步数稍多一点，但是起码增长速度跟 n²/ln(n) 一样呢？
互搭便车的暴力复原方法
可能是经济危机中人们的各种节俭方式（拼车之类的）启发了Demaine，他想，虽然位置群之间是相互独立的，但是也许可以将不同位置群的复原操作兼并起来，一次拧动同时解决多个位置群的问题。如果说原来的复原方法是每个位置群各自为政，各自拥有一条复原线路的话，Demaine他们的方法就相当于建起了一条公交线路，一次将多个位置群送到彼岸。
利用这个方法，他们给出了一个算法，可以在c'×n²/ln(n)步内还原任意的n阶魔方。在这里c'是另一个常数，它比c大得多。
在一些必要的预处理（比如说先解决边角问题）后，Demaine他们将魔方的所有位置群大约平均地分成n/4份，通过巧妙地应用上面的引理，使每次中枪的都是固定的几个位置群。当所有其它的位置群都被复原后，剩下满身弹孔（认识QB的同学请自行脑补）的“中枪专用位置群”数目也不多，可以用传统的方法一个一个解决。整个过程所需要的步数，恰好差不多正比于 n²/ln(n) ，与最优的可能性只差一个乘法常数。这种过于暴力的方法，也是使常数c'变得很大的原因之一。
这个结果在魔方界也引起了不少人的兴趣。据某些魔方高手所言，Demaine他们的“差一个常数最优”的算法过程，对他们探索解高阶魔方的快速方法相当有启发，只是观摩已经满足不了他们了。
讲了这么概念性的东西，最重要的还需要同学动手实践哦。你能在多长时间内还原魔方呢？
