壹. 風靡世界的玩具
1974 年春天， 匈牙利布達佩斯應用藝術學院 (Budapest College of Applied Arts) 的建築學教授魯比克 (E. Rubik) 萌生了壹個有趣的念頭， 他想設計壹個教學工具來幫助學生直觀地理解空間幾何的各種轉動。 經過思考， 他決定制作壹個由壹些小方塊組成的， 各個面能隨意轉動的 3×3×3 的立方體。 這樣的立方體可以很方便地演示各種空間轉動。
這個想法雖好， 實踐起來卻面臨壹個棘手的問題， 即如何才能讓這樣壹個立方體的各個面能隨意轉動？ 魯比克想了很多點子， 比如用磁鐵或橡皮筋連接各個小方塊， 但都不成功。 那年夏天的壹個午後， 他在多瑙河畔乘涼， 他的眼光不經意地落在了河畔的鵝卵石上。 忽然， 他心中閃過壹個新的設想： 用類似於鵝卵石表面那樣的圓形表面來處理立方體的內部結構。 這壹新設想成功了， 魯比克很快完成了自己的設計， 並向匈牙利專利局申請了專利。 這壹設計就是我們都很熟悉的魔方 (magic cube)， 也叫魯比克方塊 (Rubik's cube)[註壹]。
六年後， 魯比克的魔方經過壹位匈牙利商人兼業余數學家的牽頭， 打進了西歐及美國市場， 並以驚人的速度成為了風靡全球的新潮玩具。 在此後的 25 年間， 魔方的銷量超過了 3 億個。 在魔方的玩家中， 既有牙牙學語的孩子， 也有跨國公司的老總。 魔方雖未如魯比克設想的那樣成為壹種空間幾何的教學工具， 卻變成了有史以來最暢銷的玩具。
魔方之暢銷， 最大的魔力就在於其數目驚人的顏色組合。 壹個魔方出廠時每個面各有壹種顏色， 總***有六種顏色， 但這些顏色被打亂後， 所能形成的組合數卻多達 4325 億億[註二]。 如果我們將這些組合中的每壹種都做成壹個魔方， 這些魔方排在壹起， 可以從地球壹直排到 250 光年外的遙遠星空。 也就是說， 如果我們在這樣壹排魔方的壹端點上壹盞燈， 那燈光要在 250 年後才能照到另壹端。 如果哪位勤勉的玩家想要嘗試所有的組合， 哪怕他不吃、 不喝、 不睡， 每秒鐘轉出十種不同的組合， 也要花 1500 億年的時間才能如願 (作為比較， 我們的宇宙目前還不到 140 億歲)。 與這樣的組合數相比， 廣告商們常用的 “成千上萬”、 “數以億計”、 “數以十億計” 等平日裏虛張聲勢、 忽悠顧客的形容詞反倒變成了難得的謙虛。 我們可以很有把握地說， 假如不掌握訣竅地隨意亂轉， 壹個人哪怕從宇宙大爆炸之初就開始玩魔方， 也幾乎沒有任何希望將壹個色彩被打亂的魔方復原。
二. 魔方與 “上帝之數”
魔方的玩家多了， 相互間的比賽自然是少不了的。 自 1981 年起， 魔方愛好者們開始舉辦世界性的魔方大賽， 從而開始締造自己的世界紀錄。 這壹紀錄被不斷地刷新著， 到本文寫作之時為止， 復原魔方的最快紀錄 - 如我們在本文開頭提到的 - 已經達到了令人吃驚的 7.08 秒。 當然， 單次復原的紀錄存在壹定的偶然性， 為了減少這種偶然性， 自 2003 年起， 魔方大賽的冠軍改由多次復原的平均成績來決定[註三]， 目前這壹平均成績的世界紀錄為 11.28 秒。 這些記錄的出現， 表明魔方雖有天文數字般的顏色組合， 但只要掌握竅門， 將任何壹種組合復原所需的轉動次數卻並不多。
那麽， 最少需要多少次轉動， 才能確保無論什麽樣的顏色組合都能被復原呢[註四]？ 這個問題引起了很多人， 尤其是數學家的興趣。 這個復原任意組合所需的最少轉動次數被數學家們戲稱為 “上帝之數” (God's number)， 而魔方這個玩具世界的寵兒則由於這個 “上帝之數” 壹舉侵入了學術界。
要研究 “上帝之數”， 首先當然要研究魔方的復原方法。 在玩魔方的過程中， 人們早就知道， 將任意壹種給定的顏色組合復原都是很容易的， 這壹點已由玩家們的無數傑出紀錄所示範。 不過魔方玩家們所用的復原方法是便於人腦掌握的方法， 卻不是轉動次數最少的， 因此無助於尋找 “上帝之數”。 尋找轉動次數最少的方法是壹個有壹定難度的數學問題。 當然， 這個問題是難不倒數學家的。 早在二十世紀九十年代中期， 人們就有了較實用的算法， 可以用平均十五分鐘左右的時間找出復原壹種給定顏色組合的最少轉動次數。 從理論上講， 如果有人能對每壹種顏色組合都找出這樣的最少轉動次數， 那麽這些轉動次數中最大的壹個無疑就是 “上帝之數”。 但可惜的是， 4325 億億這個巨大的數字成為了人們窺視 “上帝之數” 的攔路虎。 如果采用上面提到的算法， 哪怕用壹億臺機器同時計算， 也要超過壹千萬年的時間才能完成。
看來蠻幹是行不通的， 數學家們於是便求助於他們的老本行： 數學。 從數學的角度看， 魔方的顏色組合雖然千變萬化， 其實都是由壹系列基本的操作 (即轉動) 產生的， 而且那些操作還具有幾個非常簡單的特點， 比如任何壹個操作都有壹個相反的操作 (比如與順時針轉動相反的操作就是逆時針轉動)。 對於這樣的操作， 數學家們的軍火庫中有壹種非常有效的工具來對付它， 這工具叫做群論 (group theory)， 它早在魔方問世之前壹百四十多年就已出現了。 據說德國數學大師希爾伯特 (D. Hilbert) 曾經表示， 學習群論的竅門就是選取壹個好的例子。 自魔方問世以來， 數學家們已經寫出了好幾本通過魔方講述群論的書。 因此， 魔方雖未成為空間幾何的教學工具， 卻在壹定程度上可以作為學習群論的 “好的例子”。
對魔方研究來說， 群論有壹個非常重要的優點， 就是它可以充分利用魔方的對稱性。 我們前面提到 4325 億億這個巨大數字時， 其實有壹個疏漏， 那就是並未考慮到魔方作為壹個立方體所具有的對稱性。 由此導致的結果， 是那 4325 億億種顏色組合中有很多其實是完全相同的， 只是從不同的角度去看 (比如讓不同的面朝上) 而已。 因此， 4325 億億這個令人望而生畏的數字實際上是 “註水豬肉”。 那麽， 這 “豬肉” 中的 “水份” 占多大比例呢？ 說出來嚇大家壹跳： 占了將近 99%！ 換句話說， 僅憑對稱性壹項， 數學家們就可以把魔方的顏色組合減少兩個數量級[註五]。
但減少兩個數量級對於尋找 “上帝之數” 來說還遠遠不夠， 因為那不過是將前面提到的壹千萬年的時間減少為了十萬年。 對於解決壹個數學問題來說， 十萬年顯然還是太長了， 而且我們也並不指望真有人能動用壹億臺計算機來計算 “上帝之數”。 數學家們雖然富有智慧， 但在其它方面卻不見得很富有， 他們真正能動用的也許只有自己書桌上的那臺機器。 因此為了尋找 “上帝之數”， 人們還需要尋找更巧妙的思路。 幸運的是， 群論這壹工具的威力遠不只是用來分析象立方體的對稱性那樣顯而易見的東西， 在它的幫助下， 新的思路很快就出現了。
三. 尋找 “上帝之數”
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 次轉動， 就可以將魔方的任意壹種顏色組合復原。
在得到上述結果後， 裏德很快對自己的計算作了改進， 將結果從 30 減少為了 29， 這表明 “上帝之數” 不會超過 29。 此後隨著計算機技術的發展， 數學家們對裏德的結果又作進壹步的改進， 但進展並不迅速。 直到 11 年後的 2006 年， 奧地利開普勒大學 (Johannes Kepler University) 符號計算研究所 (Research Institute for Symbolic Computation) 的博士生拉杜 (Silviu Radu) 才將結果推進到了 27。 第二年， 即 2007 年， 美國東北大學 (Northeastern University) 的計算機科學家孔克拉 (D. Kunkle) 和庫伯曼 (G. Cooperman) 又將結果推進到了 26， 他們的工作采用了並行計算系統， 所用內存高達 700 萬兆， 所耗計算時間則長達 8000 小時 (相當於將近壹年的 24 小時不停歇計算)。
這些計算結果表明， “上帝之數” 不會超過 26。 但是， 所有這些計算的最大優點 - 即利用科先巴的那片 “特殊水域” - 同時也是它們最致命的弱點， 因為它們給出的復原方法都必須經過那片特殊水域。 可事實上， 很多顏色組合的最佳復原方法根本就不經過那片特殊水域， 比如緊鄰目的地， 卻恰好不在特殊水域中的任何小船， 顯然都沒必要象大陸臺灣的直航包機壹樣， 故意從那片特殊水域繞壹下才前往目的地。 因此， 用科先巴的思路得到的復原方法未必是最佳的， 由此對 “上帝之數” 所做的估計也極有可能是高估。
可是， 如果不引進科先巴的特殊水域， 計算量又實在太大， 怎麽辦呢？ 數學家們決定采取折衷的手段， 即擴大那片特殊水域的 “面積”， 因為特殊水域越大， 最佳復原路徑恰好經過它的可能性也就越大 (當然， 計算量也會有相應的增加)。 2008 年， 研究 “上帝之數” 長達 15 年之久的計算機高手羅基奇 (T. Rokicki) 運用了相當於將科先巴的特殊水域擴大幾千倍的巧妙方法， 在短短幾個月的時間內對 “上帝之數” 連續發動了四次猛烈攻擊， 將它的估計值從 25 壹直壓縮到了 22。 截至本文寫作之時為止， 這是全世界範圍內的最佳結果。 羅基奇的計算得到了電影特效制作商索尼影像 (Sony Pictures Imageworks) 的支持， 這家曾為 “蜘蛛人” 等著名影片制作特效的公司向羅基奇提供了相當於 50 年不停歇計算所需的計算機資源。
因此， 現在我們已經知道， “上帝之數” 壹定不超過 22。 但是， 羅基奇的特殊水域雖然很大， 終究仍有很多顏色組合的最佳復原方法是無需經過那片特殊水域的， 因此， “上帝之數” 很可能比 22 更小。 那麽， 它究竟是多少呢？ 人們雖然還無法確知， 但種種跡象表明， 它極有可能是 20。 這是因為， 人們在過去這麽多年的所有努力 - 其中包括羅基奇直接計算過的大約四千萬億種顏色組合 - 中， 都從未遇到任何必須用 20 次以上轉動才能復原的顏色組合， 這表明 “上帝之數” 很可能不大於 20。 另壹方面， 人們已經發現了幾萬種顏色組合， 它們必須要用 20 次轉動才能復原， 這表明 “上帝之數” 不可能小於 20。 將這兩方面綜合起來， 數學家們普遍相信， “上帝之數” 的真正數值就是 20。 當然， “上帝” 也許是微妙的， 我們誰也無法保證它是否會在某個角落為我們留下驚訝， 我們唯壹有理由相信的也許是： 這個遊戲與數學交織而成的神秘的 “上帝之數” 距離它水落石出的那壹天已不太遙遠了。
註釋
1.魔方是魯比克自己為這壹立方體所取的名字， 魯比克方塊則是美國玩具公司 Ideal Toys 所取的名字。 在西方國家， 魯比克方塊這壹名稱更為流行， 在中國， 則是魔方這壹名稱更為流行。 另外要提醒讀者的是， 魔方有很多種類， 本文介紹的 3×3×3 魔方只是其中最常見的壹種。
2.具體的計算是這樣的： 在組成魔方的小立方體中， 有 8 個是頂點， 它們之間有 8! 種置換； 這些頂點每個有 3 種顏色， 在朝向上有 37 種組合 (由於結構所限， 魔方的頂點只有 7 個能有獨立朝向)。 類似的， 魔方有 12 個小立方體是邊， 它們之間有 12!/2 種置換 (之所以除以 2， 是因為魔方的頂點壹旦確定， 邊的置換就只有壹半是可能的)； 這些邊每個有兩種顏色， 在朝向上有 211 種組合 (由於結構所限， 魔方的邊只有 11 個能有獨立朝向)。 因此， 魔方的顏色組合總數為 8!×37×12!×211/2 = 43252003274489856000， 即大約 4325 億億。 另外值得壹提的是， 倘若我們允許將魔方拆掉重組， 則前面提到的結構限定將不復存在， 它的顏色組合數將多達 51900 億億種。 不過組合數的增加並不意味著復原的難度變大， 魔方結構對組合數的限制實際上正是使魔方的復原變得困難的主要原因。 舉個例子來說， 二十六個英文字母在相鄰字母的交換之下***有約 400 億億億種組合， 遠遠多於魔方顏色的組合數， 但通過相鄰字母的交換將隨意排列的二十六個英文字母復原成從 A 到 Z 的初始排列卻非常簡單。
3.確切地說是取五次嘗試中居中的三次成績的平均值。
4.為了使這壹問題有意義， 當然首先要定義什麽是轉動。 在對魔方的數學研究中， 轉動是指將魔方的任意壹個 (包含 9 個小方塊的) 面沿順時針或逆時針方向轉動 90° 或 180°， 對每個面來說， 這樣的轉動***有 3 種 (請讀者想壹想， 為什麽不是 4 種？)。 由於魔方有 6 個面， 因此它的基本轉動方式***有 18 種。
5.確切地說， 是 18 種基本轉動方式中有 10 種自成系列， 由此形成的顏色組合***有 8!×8!×4!/2 (約 195 億) 種。