上帝之數

上帝之數指還原一個任意打亂的魔方所需要的最少步數。三階魔方有43,252,003,274,489,856,000（約合4.3×10的19次方）種不同的可能組合狀態，但它都能在20步之內還原（最多20步）。這個20，便是（三階魔方的）上帝之數。

二階魔方的上帝之數為11。

基本介紹

• 中文名：上帝之數
• 外文名：God's number
• 出自：魔方
• 對象：數字
• 屬性：最大

簡介

將任意三階魔方打亂後，最小還原步數究竟是多少？這一問題困擾了數學家長達三十多年，這個最小還原步數也被稱為“上帝之數”。美國加利福尼亞州科學家近日利用計算機破解了這一謎團，他們證明任意組合的魔方（三階魔方有43,252,003,274,489,856,000(約合4.3×10的19次方)種不同的可能組合狀態）均可以在20步之內還原。因而，上帝之數=20

具體結果

該團隊給出了各種步數的狀態總數：

註：該團隊還沒有計算出後5種的確切數，不過一直在計算。他們會把結果發布在網站上，當然我們也會更新。

步數	需要此步數的狀態總數
0	1
1	18
2	243
3	3240
4	43,239
5	574,908
6	7,618,438
7	100,803,036
8	1,332,343,288
9	17,596,479,795
10	232,248,063,316
11	3,063,288,809,012
12	40,374,425,656,248
13	531,653,418,284,628
14	6,989,320,578,825,358
15	91,365,146,187,124,313
16	約1,100,000,000,000,000,000
17	約12,000,000,000,000,000,000
18	約29,000,000,000,000,000,000
19	約1,500,000,000,000,000,000
20	約490,000,000

最亂狀態

所謂最亂狀態，就是在和其他狀態相比時他的最少步驟步數最多的狀態。該團隊現在已經給出了部分最亂狀態並且給出了打亂公式。需要說明的是在還原得到的某個最亂狀態時，不用反著做打亂公式，只需要把公式從頭再做一遍就可以了（道理就是該操作的循環的階是2）。下面列舉幾個公式：

註：公式中的3表示該面轉270°，其實就是逆時針，但是該團隊用的是這種表示方式（可能是研究需要，比如數學建模，後邊括弧中為一般表示方式）

B3L2U1R2L3F2B1U3R1D3B1L1U3B1D2B3L2B2R2F2(B'L2U1R2L'F2B1U'R1D'B1L1U'B1D2B'L2B2R2F2)U2F2L2U3F2U1R2U2F2L3U2B3D3L2U1L1U2F3R1B1(U2F2L2U'F2U1R2U2F2L'U2B'D'L2U1L1U2F'R1B1)L1B2U2R2B2D2R1U1B3F2D3F2L1R2F3U2B3U3R3D3(L1B2U2R2B2D2R1U1B'F2D'F2L1R2F'U2B'U'R'D')R1D3R2F3U1B1D1F1R1U1L3U2B1D3L2U3L2F2U3F2(R1D'R2F'U1B1D1F1R1U1L'U2B1D'L2U'L2F2U'F2)B2F2L1F2L2B2R2F2D1L1U3B3U3R2U1F2D3L1B3F1(B2F2L1F2L2B2R2F2D1L1U'B'U'R2U1F2D'L1B'F1)R1B3L1D3F1D2B3U3B1R3U2R2L2B2D1L2U1R2U2R2(R1B'L1D'F1D2B'U'B1R'U2R2L2B2D1L2U1R2U2R2)D2R2B3D2B2D2L2B2F3D3L3U2R1U3B3D3F1L1B2R3(D2R2B'D2B2D2L2B2F'D'L'U2R1U'B'D'F1L1B2R')D2R3U2L3B2D2F2B3R1D2B1U3L2D1R1U3B3F1U1F3(D2R'U2L'B2D2F2B'R1D2B1U'L2D1R1U'B'F1U1F')B1U3B2R2D2L3B3R1F3D1B1L3F2R3D2R3L1U2F2R2(B1U'B2R2D2L'B'R1F'D1B1L'F2R'D2R'L1U2F2R2)L2U2B1L2B3L2R2U2B1R3B1R2F3U1B1F3L3D3F3U2(L2U2B1L2B'L2R2U2B1R'B1R2F'U1B1F'L'D'F'U2)

還有一種需要20步的情況與人們的普通感覺不一樣。我們總是覺得每個面在正確位置的塊越少需要步數越多。但是按照這個公式打亂：RLU2FU'DF2R2B2LU2F'B'UR2DF2UR2U。你會發現8個角塊全部正確，棱塊位置正確，但是方向反了，這是Michael Reid於1995年發現的一種狀態，因為有了這個狀態上帝之數的下限在1995年確定為不小於20.

尋找上帝之數

1992 年， 德國數學家科先巴(H. Kociemba) 提出了一種尋找魔方復原方法的新思路。 他發現， 在魔方的基本轉動方式中， 有一部分可以自成系列， 通過這部分轉動可以形成將近 200 億種顏色組合。 利用這 200 億種組合， 科先巴將魔方的復原問題分解成了兩個步驟： 第一步是將任意一種顏色組合轉變為那 200 億種組合之一， 第二步則是將那 200 億種組合復原。 如果我們把魔方復原比作是讓一條汪洋大海中的小船駛往一個固定的目的地， 那么科先巴提出的那兩百億種顏色組合就好比是一片特殊的水域 - 一片比那個固定地點大了 200 億倍的特殊水域。 他提出的兩個步驟就好比是讓小船首先駛往那片特殊水域， 然後從那裡駛往那個固定的目的地。 在汪洋大海中尋找一片巨大的特殊水域， 顯然要比直接尋找那個小小的目的地容易得多， 這就是科先巴的新思路的優越之處。但即便如此， 要用科先巴的方法對 “上帝之數” 進行估算仍不是一件容易的事。 尤其是， 要想進行快速的計算， 最好是將復原那 200 億種顏色組合的最少轉動次數 (這相當於是那片 “特殊水域” 的地圖) 存儲在計算機的記憶體中， 這大約需要 300 兆的記憶體。 300 兆在今天看來是一個不太大的數目， 但在科先巴提出新思路的那年， 普通機器的記憶體連它的十分之一都遠遠不到。 因此直到三年後， 才有人利用科先巴的方法給出了第一個估算結果。 此人名叫里德(M. Reid)， 是美國中佛羅里達大學(Unversity of Central Florida) 的數學家。 1995 年， 里德通過計算發現， 最多經過 12 次轉動， 就可以將魔方的任意一種顏色組合變為科先巴那 200 億種組合之一； 而最多經過 18 次轉動， 就可以將那 200 億種組合中的任意一種復原。 這表明， 最多經過 12+18=30 次轉動， 就可以將魔方的任意一種顏色組合復原。

這些計算結果表明， “上帝之數” 不會超過 26。 但是， 所有這些計算的最大優點 - 即利用科先巴的那片 “特殊水域” - 同時也是它們最致命的弱點， 因為它們給出的復原方法都必須經過那片特殊水域。 可事實上， 很多顏色組合的最佳復原方法根本就不經過那片特殊水域， 比如緊鄰目的地， 卻恰好不在特殊水域中的任何小船， 顯然都沒必要像大陸台灣的直航包機一樣， 故意從那片特殊水域繞一下才前往目的地。 因此， 用科先巴的思路得到的復原方法未必是最佳的， 由此對 “上帝之數” 所做的估計也極有可能是高估。

可是， 如果不引進科先巴的特殊水域， 計算量又實在太大， 怎么辦呢？ 數學家們決定採取折衷的手段， 即擴大那片特殊水域的 “面積”， 因為特殊水域越大， 最佳復原路徑恰好經過它的可能性也就越大 (當然， 計算量也會有相應的增加)。 2008 年， 研究 “上帝之數” 長達 15 年之久的計算機高手羅基奇 (T. Rokicki) 運用了相當於將科先巴的特殊水域擴大幾千倍的巧妙方法， 在短短几個月的時間內對 “上帝之數” 連續發動了四次猛烈攻擊， 將它的估計值從 25 一直壓縮到了 22。這是當時全世界範圍內的最佳結果。 羅基奇的計算得到了電影特效製作商索尼影像 (Sony Pictures Imageworks) 的支持， 這家曾為 “蜘蛛人” 等著名影片製作特效的公司向羅基奇提供了相當於 50 年不停歇計算所需的計算機資源。

與此同時，科學家們發現了一種已知的最混亂狀態——superflip。在Superflip這種狀態中，每個魔塊的位置都是對的，除了每個棱塊都是翻轉反向的。這種形態已被證明不可能用小於20種方法還原，因此上帝之數一定大於等於20，也有不少的研究人員預測，上帝之數就是20。

2010年7月，美國加利福尼亞州科學家徵用到了更加強大的資源——谷歌舊金山總部的超級主腦計算機。隨著程式的精簡和設備的提升，這量配置驚人的計算機破解了這一謎團。研究人員利用計算機，用枚舉法驗證了每一種情況，證明任意組合的魔方均可以在20步之內還原，“上帝之數”正式定為20。

這支研究團隊位於美國加利福尼亞州帕洛阿爾托市。科學家們通過計算機計算和證明，任意組合的魔方都可以在20步內還原。這一結果表明，大約有10萬多種的起始狀態恰好可以在20步內還原。

利用谷歌公司計算機強大的計算能力，研究人員檢驗了魔方任何可能的混亂狀態(確切數字為43,252,003,274,489,856,000約合4.3×10的19次方)。美國俄亥俄州肯特州立大學數學家莫雷-戴維德森教授也是研究人員之一，他表示，“我們現在可以肯定，這個‘上帝之數’就是20。對於我來說，我也回到了原地。魔方伴隨著我成長，這也是我為什麼深入研究這個數學問題的原因。這個謎團引起了人們的廣泛關注，它也許是人類歷史上最受歡迎的謎語了。”科學家們的初步研究成果發表於線上網站上，但戴維德森表示，他們準備將研究成果提交給雜誌正式發表。

程式設計師托馬斯-羅基花了15年的時間，致力於尋找這個謎團的答案。據羅基介紹，研究團隊所採用的算法可以在1秒鐘內嘗試10億種可能，此前的計算機算法1秒鐘內只能處理4000種可能。

為了讓問題簡單化，研究團隊採用了一種所謂“群論”的數學技術。他們首先將魔方所有可能的起始狀態集分成22億個集合，每個集合包含了195億個可能的狀態。集合的分配原則是這些可能的狀態是如何應對一組10個可能的還原步驟。再通過魔方不同的對稱性，這種分組技術使得研究團隊將集合數減少到5600萬個。

研究人員所採用的算法可以快速將這些還原步驟與恰當的起始點匹配起來，從而實現在20秒內處理一個集合中的195億種可能。對於普通的家用電腦來說，以這樣的速度完成整個處理任務需要大約35年時間。

魔方與數學

1974 年春天，匈牙利布達佩斯套用藝術學院(Budapest College of Applied Arts) 的建築學教授魯比克(E. Rubik) 萌生了一個有趣的念頭， 他想設計一個教學工具來幫助學生直觀地理解空間幾何的各種轉動。 經過思考， 他決定製作一個由一些小方塊組成的， 各個面能隨意轉動的 3×3×3 的立方體。 這樣的立方體可以很方便地演示各種空間轉動。

隨後魔方風靡全球， 其原因最大的魔力就在於其數目驚人的顏色組合。 一個魔方出廠時每個面各有一種顏色， 總共有六種顏色，（一般為 ：黃、白、綠、藍、紅、橙） 但這些顏色被打亂後， 所能形成的組合數卻多達 4325 億億個（注意確實是兩個億字）。 如果我們將這些組合中的每一種都做成一個魔方， 這些魔方排在一起， 可以從地球一直排到 250 光年外的遙遠星空。 也就是說， 如果我們在這樣一排魔方的一端點上一盞燈， 那燈光要在 250 年後才能照到另一端。 如果哪位勤勉的玩家想要嘗試所有的組合， 哪怕他不吃、 不喝、 不睡， 每秒鐘轉出十種不同的組合， 也要花 1500 億年的時間才能如願 (作為比較， 我們的宇宙目前還不到 140 億歲)。 與這樣的組合數相比， 廣告商們常用的 “成千上萬”、 “數以億計”、 “數以十億計” 等平日裡虛張聲勢、 忽悠顧客的形容詞反倒變成了難得的謙虛。 我們可以很有把握地說， 假如不掌握訣竅地隨意亂轉， 一個人哪怕從宇宙大爆炸之初就開始玩魔方， 也幾乎沒有任何希望將一個色彩被打亂的魔方復原。

魔方與上帝之數

魔方的玩家多了， 相互間的比賽自然是少不了的。 自 1981 年起， 魔方愛好者們開始舉辦世界性的魔方大賽， 從而開始締造自己的世界紀錄。 這一紀錄被不斷地刷新著， 到本文寫作之時為止， 復原魔方的最快紀錄 - 如我們在本文開頭提到的 - 已經達到了令人吃驚的 3.47秒。 當然， 單次復原的紀錄存在一定的偶然性， 為了減少這種偶然性， 自 2003 年起， 魔方大賽的冠軍改由多次復原的平均成績來決定， 目前這一平均成績的世界紀錄為 5.80秒。 這些記錄的出現， 表明魔方雖有天文數字般的顏色組合， 但只要掌握竅門， 將任何一種組合復原所需的轉動次數卻並不多。

三階魔方速擰世界紀錄5.55s

那么， 最少需要多少次轉動， 才能確保無論什麼樣的顏色組合都能被復原呢？ 這個問題引起了很多人， 尤其是數學家的興趣。 這個復原任意組合所需的最少轉動次數被數學家們戲稱為 “上帝之數” (God's number)， 而魔方這個玩具世界的寵兒則由於這個 “上帝之數” 一舉侵入了學術界。

要研究 “上帝之數”， 首先當然要研究魔方的復原方法。 在玩魔方的過程中， 人們早就知道， 將任意一種給定的顏色組合復原都是很容易的， 這一點已由玩家們的無數傑出紀錄所示範。 不過魔方玩家們所用的復原方法是便於人腦掌握的方法， 卻不是轉動次數最少的， 因此無助於尋找 “上帝之數”。 尋找轉動次數最少的方法是一個有一定難度的數學問題。 當然， 這個問題是難不倒數學家的。 早在二十世紀九十年代中期， 人們就有了較實用的算法， 可以用平均十五分鐘左右的時間找出復原一種給定顏色組合的最少轉動次數。 從理論上講， 如果有人能對每一種顏色組合都找出這樣的最少轉動次數， 那么這些轉動次數中最大的一個無疑就是 “上帝之數”。 但可惜的是， 4325 億億這個巨大的數字成為了人們窺視 “上帝之數” 的攔路虎。 如果採用上面提到的算法， 哪怕用一億台機器同時計算， 也要超過一千萬年的時間才能完成。

看來蠻幹是行不通的， 數學家們於是便求助於他們的老本行： 數學。 從數學的角度看， 魔方的顏色組合雖然千變萬化， 其實都是由一系列基本的操作 (即轉動) 產生的， 而且那些操作還具有幾個非常簡單的特點， 比如任何一個操作都有一個相反的操作 (比如與順時針轉動相反的操作就是逆時針轉動)。 對於這樣的操作， 數學家們的軍火庫中有一種非常有效的工具來對付它， 這工具叫做群論 (group theory)， 它早在魔方問世之前一百四十多年就已出現了。 據說德國數學大師希爾伯特(D. Hilbert) 曾經表示， 學習群論的竅門就是選取一個好的例子。 自魔方問世以來， 數學家們已經寫出了好幾本通過魔方講述群論的書。 因此， 魔方雖未成為空間幾何的教學工具， 卻在一定程度上可以作為學習群論的 “好的例子”。

對魔方研究來說， 群論有一個非常重要的優點， 就是它可以充分利用魔方的對稱性。 我們前面提到 4325 億億這個巨大數字時， 其實有一個疏漏， 那就是並未考慮到魔方作為一個立方體所具有的對稱性。 由此導致的結果， 是那 4325 億億種顏色組合中有很多其實是完全相同的， 只是從不同的角度去看 (比如讓不同的面朝上或者通過鏡子去看) 而已。 因此， 4325 億億這個令人望而生畏的數字實際上是 “注水豬肉”。 那么， 這 “豬肉” 中的 “水份” 占多大比例呢？ 說出來嚇大家一跳： 占了將近 99%！ 換句話說， 僅憑對稱性一項， 數學家們就可以把魔方的顏色組合減少兩個數量級。

但減少兩個數量級對於尋找 “上帝之數” 來說還遠遠不夠， 因為那不過是將前面提到的一千萬年的時間減少為了十萬年。 對於解決一個數學問題來說， 十萬年顯然還是太長了， 而且我們也並不指望真有人能動用一億台計算機來計算 “上帝之數”。 數學家們雖然富有智慧， 但在其它方面卻不見得很富有， 他們真正能動用的也許只有自己書桌上的那台機器。 因此為了尋找 “上帝之數”， 人們還需要尋找更巧妙的思路。 幸運的是， 群論這一工具的威力遠不只是用來分析象立方體的對稱性那樣顯而易見的東西， 在它的幫助下， 新的思路很快就出現了。

革命尚未成功

目前只是找到了三階魔方的上帝之數，但是4階及以上，還有許多經典的異形的上帝之數還沒有解決，看到三階解決歷程，可以想像找出所有魔方的上帝之數是對人類智慧的一大考驗。