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