破解“上帝之數(shù)”,的確是20!

8月，一個研究小組通過網(wǎng)站鄭重地向世人宣布，他們在Google提供的超級計算機的支持下，已經(jīng)破解了傳說中的“上帝之數(shù)”——任意給定一種魔方布局，20步以內(nèi)一定能將其還原。這在網(wǎng)絡上立即引起了軒然大波。

要轉(zhuǎn)動多少步?

從匈牙利建筑學教授Erno Rubik在1974年發(fā)明魔方的那一天開始，一個后來被稱為“上帝之數(shù)”的終極魔方謎題便困擾著所有人：至少需要轉(zhuǎn)動多少步才能保證解開任意一個魔方?

由于魔方的每個面都有順時針90度、逆時針90度和180度三種旋轉(zhuǎn)方式，因此魔方中的每一步就有多達3×6＝18種可能。步數(shù)一多，轉(zhuǎn)動的方案數(shù)就將呈指數(shù)級增加。在所有的魔方布局中，一種叫做“超級大翻轉(zhuǎn)”的特殊布局常被認為是最難還原的情形。在這種布局下，所有面的中心和所有角上的方塊都位于正確的位置，只有每條棱上的顏色恰好都顛倒了。

在相當長的一段時間里，人們都一直認為還原“超級大翻轉(zhuǎn)”至少得用22步。1992年，Dik I Wincer找到了用20步還原“超級大翻轉(zhuǎn)”的方法；3年后，Michael Reid證明出，這已經(jīng)是還原“超級大翻轉(zhuǎn)”步驟最少的解法了。科學家們普遍猜測，不會存在比“超級大翻轉(zhuǎn)”更困難的魔方布局了，也就是說“上帝之數(shù)”很可能就是20。

數(shù)十年的探索

為了明確“上帝之數(shù)”的真正數(shù)值，人們對“上帝之數(shù)”的探索長這數(shù)十年?？茖W家們早就想過，由于魔方的布局數(shù)量是有限的，因此可以借助計算機的力量對所有情況進行檢驗。然而，魔方中所有可能的布局有4300億個之多，即使計算機每1秒鐘能找出1萬個布局的最優(yōu)解，也需要1億年的時間才能完成檢驗!

1992年，德國的一位數(shù)學教師Herbert Kociemba提出了著名的“二階段算法”。他把還原魔方的過程分為了兩個階段，即先把魔方變?yōu)橐环N無需對四個側(cè)面進行90度旋轉(zhuǎn)便能還原的布局，再在這種限制條件下將此布局徹底還原。依據(jù)前一階段的處理步驟，4300億億個魔方布局可以被劃分為22億組本質(zhì)不同的情形，這個數(shù)字規(guī)模是當前的計算機能夠承受的。在計算機程序中，Herbert Kociemba采用了一種叫做IDA的高效搜索方法，大大增加了尋找魔方解法的效率。

不過，由于當時計算機的運算能力有限，程序只能得到步驟盡可能少的還原方案。1995年，Michael Reid運用這種算法，驗證了每一種魔方布局都能在30步以內(nèi)還原?！吧系壑當?shù)”的上限被降低到了30，但離科學家們的推測還有一段距離。

隨著計算機硬件水平的提高，魔方問題不斷地有了新的進展。從2005年開始，在連續(xù)三年里，“上帝之數(shù)”的上限先后被改進到了27步、26步、25步。2008年，天才程序設計師Tomas Rokicki對Herben Kcciemba的“二階段算法”進行了一系列優(yōu)化，成功地把“上帝之數(shù)”的上限降到了22，離勝利只有兩步之遙了。

聯(lián)合進攻最后一步

而這一回，程序設計師Tomas Rokicki與德國數(shù)學教師Herbert Kociemba聯(lián)合了起來，與美國肯特州立大學數(shù)學家Morley Da—vidson和Google工程師John Dethridge一道，悄悄地組成了一支特別的國際研究小組，對“上帝之數(shù)”發(fā)起最后一波進攻。

他們利用魔方布局的對稱性，將“二階段算法”中的22億組情形減少到了5588萬組，并對計算機程序進行了新一輪的優(yōu)化，使得每一組問題都可以在大約20秒內(nèi)解決。最后，他們把這5588萬組問題分配給了Google提供的一大批超級計算機，讓所有的機器同時處理。這些超強性能的計算機只耗費了幾個星期的時間便完成了運算，其運算量相當于一臺普通計算機晝夜不停地工作長達35年。

8月份，研究小組建立了網(wǎng)站cube20org，不但宣布了“上帝之數(shù)”等于20，還給出了一些詳細的統(tǒng)計數(shù)據(jù)：絕大多數(shù)魔方布局都需要16步以上才能獲解，像“超級大翻轉(zhuǎn)”一樣至少得用20步才能還原的魔方布局竟然還有3億多個!幾十年來懸而未解的終極謎題得到了完美的解答，“上帝之數(shù)”的神秘面紗終于被揭開。