一年前，谷歌告訴我們任意擰亂的魔方可以在20步內復原，這個20，也叫做上帝之數。當然，那只是對于3階的魔方來說的。最近，一幫MIT的數學家說，他們找到了一種通用算法，可以找到任意階魔方的上帝之數。那么，他們是怎么做到的呢？
魔方大概是現在最有影響力的智力游戲了，它是一個3×3×3的正方體，初始狀態(tài)下每個面的9個方格都涂上同樣顏色，6個面一共6種顏色。作為一個智力游戲，它的目標就是將任意擰亂的魔方盡快還原為每面所有小方格同色的初始狀態(tài)。為了贏得比賽，大家都致力于找到更快的魔方復原方法。
大概一年前，Google的一幫人驗證了任意擰亂的魔方可以在20步內復原。但是，一般人要在20步內復原任意魔方的話，就要記住一個碩大無比的表格（大約8EB，一EB大約是一百萬TB），這東西只有擁有全知全能的上帝及其類似物（比如說團長、春哥或者高斯）才能做到，所以20這個數又被稱為魔方的“上帝之數”。
?
魔方當然不只有一種。最簡單的變化方法就是將魔方的“邊長”（或者叫階數）變大。原版的魔方是3階的，也就是3×3×3的立方體。我們可以擴展到4階（4×4×4），5階，一直到7階，甚至有人目擊過11階的魔方。魔方的階數越大，解起來也越復雜，需要的步數也越多，它們的上帝之數也越大而且越難計算。
現在，一幫在MIT的由Erik Demaine領銜的數學家，竟然說他們找到了任意階數魔方的上帝之數，而且還給出了一個復原的算法，需要的步數與上帝之數相差不遠！我們現在就來看個究竟。
怎么轉都轉不出那24個陷阱
?
?
由24個位置組成的一個位置群
無論魔方被如何擰動，圖中所示的小色塊一共只能到達最多24個位置。我們把這些位置稱作一個位置群。一個n階的魔方，不算邊角上的色塊，只有大約(n-2)2/4個位置群。這些位置群都是相互獨立的。要復原魔方，就相當于要將所有位置群復原。
Demaine從玩魔方的人們那里了解到，有標準的手法可以單單將一個位置群內的小色塊復原，而不影響別的位置群的色塊。這就是為什么我們說這些位置群是獨立的。而因為每個位置群內色塊的數目都是固定的（不多于24個），所以要復原一個位置群里的所有色塊，只需要固定步數的操作。這些知識，魔方社區(qū)早就一清二楚。
但是，如果單靠這種方法來解n階魔方的話，因為至少有(n-2)2/4個位置群，所以用這種方法復原魔方需要的步數大約與n2成正比。有沒有可能用更少的步數復原魔方呢？復原所有魔方的步數有沒有下限呢？
上帝之數不能太小
?
對于足夠大的n，我們大約有n2/4個位置群，它們各自有24個不同位置的小色塊。在這24個色塊中，6種顏色分別各有4個，這是初始狀態(tài)決定的。用一點簡單的組合知識就可以知道，我們一共有(24!)/(4!)?種方法打亂一個位置群中的色塊。因為位置群之間是獨立的，所以魔方至少有 (24!)/(4!)? (n-2)2/4 種不同的打亂方式（還沒算邊角排列的各種可能性）。
由上帝之數的定義，我們可以在D(n)步內將任意魔方復原。如果我們將這些復原的步驟倒過來操作，這其實就意味著我們可以用至多D(n)步將魔方打亂到所有可能的打亂方式。每一步我們有(6n 1)種操作，每次操作就是將某一排擰上90度，另外復原后舉起魔方炫耀然后被打倒在地踩上一萬只腳也算一次操作，可以爬起來然后多次重復這項操作。所以魔方至多有 (6n 1) D(n) 種打亂方式，因為某些系列操作會導致同樣的打亂結果。
我們就有了以下的不等式：
?
從這個不等式我們可以得到：
當n趨向于無窮大的時候，上面那個看起來很復雜的量就跟 c×n2/ln(n) 差不多了，其中c大約是35.7164。
可能我們做不到在 c×n2/ln(n) 步內還原任意的n階魔方，但是能不能提出一種方法，即使還原的步數稍多一點，但是起碼增長速度跟 n2/ln(n) 一樣呢？
互搭便車的暴力復原方法
可能是經濟危機中人們的各種節(jié)儉方式（拼車之類的）啟發(fā)了Demaine，他想，雖然位置群之間是相互獨立的，但是也許可以將不同位置群的復原操作兼并起來，一次擰動同時解決多個位置群的問題。如果說原來的復原方法是每個位置群各自為政，各自擁有一條復原線路的話，Demaine他們的方法就相當于建起了一條公交線路，一次將多個位置群送到彼岸。
利用這個方法，他們給出了一個算法，可以在c'×n2/ln(n)步內還原任意的n階魔方。在這里c'是另一個常數，它比c大得多。
本來筆者想在這里描述一下證明過程，但無奈這個證明過于暴力，打上R-18也不為過，所以筆者也不好說太細，想詳細觀賞的重口味同學請上 arXiv 看現場。這里筆者只能寫意地描繪一下。
證明過程中最重要的引理之一是，對于某些特定的k×m個位置群，要復原它們中被打亂方式相同的位置群，按照傳統(tǒng)的方法平均需要的步數正比于k×m，但我們可以建一條公交線路，只用正比于(m k)的步數就可以將這些位置群一下子全部解決，代價是一些別的位置群“躺著也中槍”，不知不覺就被改變了。
然后，在一些必要的預處理（比如說先解決邊角問題）后，Demaine他們將魔方的所有位置群大約平均地分成n/4份，通過巧妙地應用上面的引理，使每次中槍的都是固定的幾個位置群。當所有其它的位置群都被復原后，剩下滿身彈孔（認識QB的同學請自行腦補）的“中槍專用位置群”數目也不多，可以用傳統(tǒng)的方法一個一個解決。整個過程所需要的步數，恰好差不多正比于 n2/ln(n) ，與最優(yōu)的可能性只差一個乘法常數。這種過于暴力的方法，也是使常數c'變得很大的原因之一。
步步逼近上帝之數
?
可能你會說筆者太坑爹，那些常規(guī)方法需要的步數，增長趨勢也只是 n2，也就是說最多是另一個常數乘以 n2。我們現在這么費勁也就是削下來了一個 ln(n) 的因子，這個看起來沒什么用啊。
但不要小看 ln(n)。常數畢竟是常數，它是不會變的，但是 ln(n) 可以無限增長。當 n 不斷增長，總有一天 ln(n) 會比任何常數都要大，n2 會比 n2/ln(n) 大得多。
那么，Demaine他們的工作意義是什么呢？他們其實證明了任意 n 階魔方的上帝之數 D(n) 的增長趨勢與 n2/ln(n) 是一樣的。更具體地說，盡管我們現在仍然不知道D(n)的具體表達式（可能永遠也不會知道），但它必定在 c×n2/ln(n) 和 c'×n2/ln(n) 之間。用數學的語言來說，我們第一次確定了任意n階魔方上帝之數的階，第一次將它困在了一個區(qū)間里。這是萬里長征第一步，之后我們可以進行更精細的分析，縮短兩個常數的距離，更好地確定上帝之數的位置。這也是Demaine他們下一步打算做的事情。
這個結果在魔方界也引起了不少人的興趣。據某些魔方高手所言，Demaine他們的“差一個常數最優(yōu)”的算法過程，對他們探索解高階魔方的快速方法相當有啟發(fā)，只是觀摩已經滿足不了他們了