破解“上帝之數”,的確是20!

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

要轉動多少步?

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

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

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

數十年的探索

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

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

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

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

聯合進攻最后一步

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

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

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