魔方大概是現在最有影響力的智力遊戲了，它是一個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大得多。

本來筆者想在這裡描述一下證明過程，但無奈這個證明過于暴力，打上R-18也不為過，所以筆者也不好說太細，這裡筆者隻能寫意地描繪一下。

證明過程中最重要的引理之一是，對于某些特定的k×m個位置群，要複原它們中被打亂方式相同的位置群，按照傳統的方法平均需要的步數正比于k×m，但我們可以建一條公交線路，隻用正比于(m k)的步數就可以将這些位置群一下子全部解決，代價是一些别的位置群“躺着也中槍”，不知不覺就被改變了。

然後，在一些必要的預處理（比如說先解決邊角問題）後，Demaine他們将魔方的所有位置群大約平均地分成n/4份，通過巧妙地應用上面的引理，使每次中槍的都是固定的幾個位置群。當所有其它的位置群都被複原後，剩下滿身彈孔（認識QB的同學請自行腦補）的“中槍專用位置群”數目也不多，可以用傳統的方法一個一個解決。整個過程所需要的步數，恰好差不多正比于 n²/ln(n) ，與最優的可能性隻差一個乘法常數。這種過于暴力的方法，也是使常數c'變得很大的原因之一。

步步逼近上帝之數

可能你會說筆者太坑爹，那些常規方法需要的步數，增長趨勢也隻是 n²，也就是說最多是另一個常數乘以 n²。我們現在這麼費勁也就是削下來了一個 ln(n) 的因子，這個看起來沒什麼用啊。

但不要小看 ln(n)。常數畢竟是常數，它是不會變的，但是 ln(n) 可以無限增長。當 n 不斷增長，總有一天 ln(n) 會比任何常數都要大，n² 會比 n²/ln(n) 大得多。

那麼，Demaine他們的工作意義是什麼呢？他們其實證明了任意 n 階魔方的上帝之數 D(n) 的增長趨勢與 n²/ln(n) 是一樣的。更具體地說，盡管我們現在仍然不知道D(n)的具體表達式（可能永遠也不會知道），但它必定在 c×n²/ln(n) 和 c'×n²/ln(n) 之間。用數學的語言來說，我們第一次确定了任意n階魔方上帝之數的階，第一次将它困在了一個區間裡。這是萬裡長征第一步，之後我們可以進行更精細的分析，縮短兩個常數的距離，更好地确定上帝之數的位置。這也是Demaine他們下一步打算做的事情。

這個結果在魔方界也引起了不少人的興趣。據某些魔方高手所言，Demaine他們的“差一個常數最優”的算法過程，對他們探索解高階魔方的快速方法相當有啟發，隻是觀摩已經滿足不了他們了