一年前，谷歌告訴我們?nèi)我鈹Q亂的魔方可以在20步內(nèi)復(fù)原，這個20，也叫做上帝之?dāng)?shù)。當(dāng)然，那只是對于3階的魔方來說的。最近，一幫MIT的數(shù)學(xué)家說，他們找到了一種通用算法，可以找到任意階魔方的上帝之?dāng)?shù)。那么，他們是怎么做到的呢？

魔方大概是現(xiàn)在最有影響力的智力游戲了，它是一個3×3×3的正方體，初始狀態(tài)下每個面的9個方格都涂上同樣顏色，6個面一共6種顏色。作為一個智力游戲，它的目標(biāo)就是將任意擰亂的魔方盡快還原為每面所有小方格同色的初始狀態(tài)。為了贏得比賽，大家都致力于找到更快的魔方復(fù)原方法。

大概一年前，Google的一幫人驗證了任意擰亂的魔方可以在20步內(nèi)復(fù)原。但是，一般人要在20步內(nèi)復(fù)原任意魔方的話，就要記住一個碩大無比的表格（大約8EB，一EB大約是一百萬TB），這東西只有擁有全知全能的上帝及其類似物（比如說團(tuán)長、春哥或者高斯）才能做到，所以20這個數(shù)又被稱為魔方的“上帝之?dāng)?shù)”。

魔方當(dāng)然不只有一種。最簡單的變化方法就是將魔方的“邊長”（或者叫階數(shù)）變大。原版的魔方是3階的，也就是3×3×3的立方體。我們可以擴(kuò)展到4階（4×4×4），5階，一直到7階，甚至有人目擊過11階的魔方。魔方的階數(shù)越大，解起來也越復(fù)雜，需要的步數(shù)也越多，它們的上帝之?dāng)?shù)也越大而且越難計算。

現(xiàn)在，一幫在MIT的由Erik Demaine領(lǐng)銜的數(shù)學(xué)家，竟然說他們找到了任意階數(shù)魔方的上帝之?dāng)?shù)，而且還給出了一個復(fù)原的算法，需要的步數(shù)與上帝之?dāng)?shù)相差不遠(yuǎn)！我們現(xiàn)在就來看個究竟。

怎么轉(zhuǎn)都轉(zhuǎn)不出那24個陷阱
初看起來，魔方每個面可以擰得千變?nèi)f化，讓人無從捉摸。然而對于魔方面上涂色的小方塊來說，它們可去的地方并不多（假設(shè)我們能做的操作就是將魔方的某排擰動90度）。

由24個位置組成的一個位置群

無論魔方被如何擰動，圖中所示的小色塊一共只能到達(dá)最多24個位置。我們把這些位置稱作一個位置群。一個n階的魔方，不算邊角上的色塊，只有大約(n-2)2/4個位置群。這些位置群都是相互獨立的。要復(fù)原魔方，就相當(dāng)于要將所有位置群復(fù)原。

Demaine從玩魔方的人們那里了解到，有標(biāo)準(zhǔn)的手法可以單單將一個位置群內(nèi)的小色塊復(fù)原，而不影響別的位置群的色塊。這就是為什么我們說這些位置群是獨立的。而因為每個位置群內(nèi)色塊的數(shù)目都是固定的（不多于24個），所以要復(fù)原一個位置群里的所有色塊，只需要固定步數(shù)的操作。這些知識，魔方社區(qū)早就一清二楚。

但是，如果單靠這種方法來解n階魔方的話，因為至少有(n-2)2/4個位置群，所以用這種方法復(fù)原魔方需要的步數(shù)大約與n2成正比。有沒有可能用更少的步數(shù)復(fù)原魔方呢？復(fù)原所有魔方的步數(shù)有沒有下限呢？

上帝之?dāng)?shù)不能太小
為了方便，我們記n階魔方的上帝之?dāng)?shù)為D(n)。他們首先證明了，對于足夠大的n，D(n)不能太小，至少是c×n2/ln(n)，其中c是一個常數(shù)。這個計算并不太難，我們就一起來試試看。

對于足夠大的n，我們大約有n2/4個位置群，它們各自有24個不同位置的小色塊。在這24個色塊中，6種顏色分別各有4個，這是初始狀態(tài)決定的。用一點簡單的組合知識就可以知道，我們一共有(24!)/(4!)?種方法打亂一個位置群中的色塊。因為位置群之間是獨立的，所以魔方至少有 (24!)/(4!)? (n-2)2/4 種不同的打亂方式（還沒算邊角排列的各種可能性）。

由上帝之?dāng)?shù)的定義，我們可以在D(n)步內(nèi)將任意魔方復(fù)原。如果我們將這些復(fù)原的步驟倒過來操作，這其實就意味著我們可以用至多D(n)步將魔方打亂到所有可能的打亂方式。每一步我們有(6n+1)種操作，每次操作就是將某一排擰上90度，另外復(fù)原后舉起魔方炫耀然后被打倒在地踩上一萬只腳也算一次操作，可以爬起來然后多次重復(fù)這項操作。所以魔方至多有 (6n+1) D(n) 種打亂方式，因為某些系列操作會導(dǎo)致同樣的打亂結(jié)果。

我們就有了以下的不等式：

從這個不等式我們可以得到：

當(dāng)n趨向于無窮大的時候，上面那個看起來很復(fù)雜的量就跟 c×n2/ln(n) 差不多了，其中c大約是35.7164。

可能我們做不到在 c×n2/ln(n) 步內(nèi)還原任意的n階魔方，但是能不能提出一種方法，即使還原的步數(shù)稍多一點，但是起碼增長速度跟 n2/ln(n) 一樣呢？

互搭便車的暴力復(fù)原方法
可能是經(jīng)濟(jì)危機(jī)中人們的各種節(jié)儉方式（拼車之類的）啟發(fā)了Demaine，他想，雖然位置群之間是相互獨立的，但是也許可以將不同位置群的復(fù)原操作兼并起來，一次擰動同時解決多個位置群的問題。如果說原來的復(fù)原方法是每個位置群各自為政，各自擁有一條復(fù)原線路的話，Demaine他們的方法就相當(dāng)于建起了一條公交線路，一次將多個位置群送到彼岸。

利用這個方法，他們給出了一個算法，可以在c'×n2/ln(n)步內(nèi)還原任意的n階魔方。在這里c'是另一個常數(shù)，它比c大得多。

本來筆者想在這里描述一下證明過程，但無奈這個證明過于暴力，打上R-18也不為過，所以筆者也不好說太細(xì)，想詳細(xì)觀賞的重口味同學(xué)請上 arXiv 看現(xiàn)場。這里筆者只能寫意地描繪一下。

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

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

步步逼近上帝之?dāng)?shù)

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

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

那么，Demaine他們的工作意義是什么呢？他們其實證明了任意 n 階魔方的上帝之?dāng)?shù) D(n) 的增長趨勢與 n2/ln(n) 是一樣的。更具體地說，盡管我們現(xiàn)在仍然不知道D(n)的具體表達(dá)式（可能永遠(yuǎn)也不會知道），但它必定在 c×n2/ln(n) 和 c'×n2/ln(n) 之間。用數(shù)學(xué)的語言來說，我們第一次確定了任意n階魔方上帝之?dāng)?shù)的階，第一次將它困在了一個區(qū)間里。這是萬里長征第一步，之后我們可以進(jìn)行更精細(xì)的分析，縮短兩個常數(shù)的距離，更好地確定上帝之?dāng)?shù)的位置。這也是Demaine他們下一步打算做的事情。

這個結(jié)果在魔方界也引起了不少人的興趣。據(jù)某些魔方高手所言，Demaine他們的“差一個常數(shù)最優(yōu)”的算法過程，對他們探索解高階魔方的快速方法相當(dāng)有啟發(fā)，只是觀摩已經(jīng)滿足不了他們了。