魔方與“上帝之數”⁽¹⁾

2008年7月，來自世界各地的很多優秀的魔方玩家聚集在捷克共和國（Czech Republic）中部城市帕爾杜比采（Pardubice），參加魔方界的重要賽事：捷克公開賽。在這次比賽上，荷蘭玩家阿克斯迪杰克（Erik Akkersdijk）創下了一個驚人的紀錄：只用7.08秒就復原了一個顏色被打亂的魔方。無獨有偶，在這一年的8月，人們在研究魔方背后的數學問題上也取得了重要進展。在本文中，我們就來介紹一下魔方以及它背后的數學問題。

一、風靡世界的玩具

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

這個想法雖好，實踐起來卻面臨一個棘手的問題，即如何才能讓這樣一個立方體的各個面能隨意轉動？魯比克想了很多點子，比如用磁鐵或橡皮筋連接各個小方塊，但都不成功。那年夏天的一個午后，他在多瑙河畔乘涼，眼光不經意地落在了河畔的鵝卵石上。忽然，他心中閃過一個新的設想：用類似于鵝卵石表面那樣的圓形表面來處理立方體的內部結構。這一新設想成功了，魯比克很快完成了自己的設計，并向匈牙利專利局申請了專利。這一設計就是我們都很熟悉的魔方（magic cube），也叫魯比克方塊（Rubik's cube）⁽²⁾。

6年后，魯比克的魔方經過一位匈牙利商人兼業余數學家的牽頭，打進了西歐及美國市場，并以驚人的速度成為了風靡全球的新潮玩具。在此后的25年間，魔方的銷量超過了3億個。在魔方的玩家中，既有牙牙學語的孩子，也有跨國公司的老總。魔方雖未如魯比克設想的那樣成為一種空間幾何的教學工具，卻變成了有史以來最暢銷的玩具。

魔方之暢銷，最大的魔力就在于其數目驚人的顏色組合。一個魔方出廠時每個面各有一種顏色，總共有6種顏色，但這些顏色被打亂后，所能形成的組合數卻多達4 325億億⁽³⁾（1億億=1×10¹⁶）。如果我們將這些組合中的每一種都做成一個魔方，這些魔方排在一起，可以從地球一直排到250光年外的遙遠星空——也就是說，如果我們在這樣一排魔方的一端點上一盞燈，那燈光要在250年后才能照到另一端！如果哪位勤勉的玩家想要嘗試所有的組合，哪怕他不吃、不喝、不睡，每秒鐘轉出10種不同的組合，也要花1 500億年的時間才能如愿（作為比較，我們的宇宙目前還不到140億歲）。與這樣的組合數相比，廣告商們常用的“成千上萬”、“數以億計”、“數以十億計”等平日里虛張聲勢、忽悠顧客的形容詞反倒變成了難得的謙虛。我們可以很有把握地說，假如不掌握訣竅地隨意亂轉，一個人哪怕從宇宙大爆炸之初就開始玩魔方，也幾乎沒有任何希望將一個色彩被打亂的魔方復原。

二、魔方與“上帝之數”

魔方的玩家多了，相互間的比賽自然是少不了的。自1981年起，魔方愛好者們開始舉辦世界性的魔方大賽，從而開始締造自己的世界紀錄。這一紀錄被不斷地刷新著，截至2013年，復原魔方的最快紀錄已經達到了令人吃驚的5.55秒。當然，單次復原的紀錄存在一定的偶然性，為了減少這種偶然性，自2003年起，魔方大賽的冠軍改由多次復原的平均成績來決定⁽⁴⁾，截至2013年，這一平均成績的世界紀錄為6.54秒。這些紀錄的出現，表明魔方雖有天文數字般的顏色組合，但只要掌握竅門，將任何一種給定的顏色組合復原所需的轉動次數卻很可能并不多。

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

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

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

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

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

三、尋找“上帝之數”

1992年，德國數學家科先巴（Herbert Kociemba）提出了一種尋找魔方復原方法的新思路⁽⁷⁾。他發現，在魔方的基本轉動方式中，有一部分可以自成系列，通過這部分轉動可以形成將近200億種顏色組合⁽⁸⁾。利用這200億種顏色組合，科先巴將魔方的復原問題分解成了兩個步驟：第一步是將任意一種顏色組合轉變為那200億種顏色組合之一，第二步則是將那200億種顏色組合復原。如果我們把魔方的復原比作是讓一條汪洋大海中的小船駛往一個固定目的地，那么科先巴提出的那200億種顏色組合就好比是一片特殊水域——一片比那個固定目的地大了200億倍的特殊水域。他提出的兩個步驟就好比是讓小船首先駛往那片特殊水域，然后從那里駛往那個固定目的地。在汪洋大海中尋找一片巨大的特殊水域，顯然要比直接尋找那個小小的目的地容易得多，這就是科先巴新思路的巧妙之處。

但即便如此，要用科先巴的新思路對“上帝之數”進行估算仍不是一件容易的事。尤其是，要想進行快速計算，最好是將復原那200億種顏色組合的最少轉動次數（這相當于是那片特殊水域的“地圖”）存儲在計算機的內存中，這大約需要300兆（300MB）的內存。300兆在今天看來是一個不太大的數目，但在科先巴提出新思路的年代，普通計算機的內存連它的十分之一都遠遠不到。因此直到3年之后，才有人利用科先巴的新思路給出了第一個估算結果。此人名叫里德（Michael 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）的計算機科學家孔克拉（Dan Kunkle）和庫伯曼（Gene Cooperman）又將結果推進到了26，他們的工作采用了并行計算系統，所用的最大存儲空間高達700萬兆（7×10⁶MB），所耗的計算時間則長達8 000小時（相當于將近一年的24小時不停歇計算）。

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

可是，如果不引進科先巴新思路中的特殊水域，計算量又實在太大，怎么辦呢？數學家們決定采取折中手段，即擴大那片特殊水域的“面積”。因為特殊水域越大，最佳復原路徑恰好經過它的可能性也就越大（當然，計算量也會有相應的增加）。2008年，研究“上帝之數”長達15年之久的計算機高手羅基奇（Tomas Rokicki）運用了相當于將科先巴新思路中的特殊水域擴大幾千倍的巧妙方法，在短短幾個月的時間內對“上帝之數”連續發動了四次猛烈攻擊，將它的估計值從25一直壓縮到了22——這就是本文開頭提到的人們在研究魔方背后的數學問題上取得的重要進展。羅基奇的計算得到了電影特效制作商索尼圖形圖像運作公司（Sony Pictures Imageworks）的支持，這家曾為《蜘蛛人》（Spider-Man）等著名影片制作特效的公司向羅基奇提供了相當于50年不停歇計算所需的計算機資源。

由此我們進一步知道，“上帝之數”一定不會超過22。但是，羅基奇雖然將科先巴新思路中的特殊水域擴展得很大，終究仍有一些顏色組合的最佳復原方法是無需經過那片特殊水域的，因此，“上帝之數”很可能比22更小。那么，它究竟是多少呢？種種跡象表明，它極有可能是20。這是因為，人們在過去這么多年的所有努力——其中包括羅基奇直接計算過的大約4 000萬億種顏色組合——中，都從未遇到過任何必須用20次以上轉動才能復原的顏色組合，這表明“上帝之數”很可能不大于20；另一方面，人們已經發現了幾萬種顏色組合，它們必須要用20次轉動才能復原，這表明“上帝之數”不可能小于20。將這兩方面綜合起來，數學家們普遍相信，“上帝之數”的真正數值就是20。

2010年8月，這個游戲與數學交織而成的神秘的“上帝之數”終于水落石出：研究“上帝之數”的“元老”科先巴、“新秀”羅基奇，以及另兩位合作者——戴維森（Morley Davidson）和德斯里奇（John Dethridge）——宣布了對“上帝之數”是20的證明⁽⁹⁾。他們的證明得到了谷歌公司（Google）提供的相當于英特爾（Intel）四核心處理器35年不停歇計算所需的計算機資源。

因此，現在我們可以用數學特有的確定性來宣布“上帝之數”的數值了，那就是：20。

2008年11月2日寫于紐約

2014年9月18日最新修訂

---

(1)本文曾發表于《科學畫報》2008年第12期（上海科學技術出版社出版）。

(2)“魔方”是魯比克自己為這一設計所取的名字，“魯比克方塊”則是美國玩具公司Ideal Toys所取的名字。在西方國家，魯比克方塊這一名稱更為流行，在中國，則是魔方這一名稱更為流行。另外要提醒讀者的是，魔方有很多種類，本文介紹的3×3×3魔方只是其中最常見的一種。

(3)具體的計算是這樣的：在組成魔方的小立方體中，有8個是頂點，它們之間有8！種置換；這些頂點每個有3種顏色，從而在朝向上有3⁷種組合（由于結構所限，魔方的頂點只有7個能有獨立朝向）。類似的，魔方有12個小立方體是邊，它們之間有12！/2種置換（之所以除以2，是因為魔方的頂點一旦確定，邊的置換就只有一半是可能的）；這些邊每個有兩種顏色，在朝向上有2¹¹種組合（由于結構所限，魔方的邊只有11個能有獨立朝向）。因此，魔方的顏色組合總數為8！×3⁷×12！×2¹¹/2=43 252 003 274 489 856 000，即大約4 325億億。另外值得一提的是，倘若我們允許將魔方拆掉重組，則前面提到的結構限定將不復存在，它的顏色組合數將多達51 900億億種。不過顏色組合數的增加并不意味著復原的難度變大，魔方結構對顏色組合數的限制實際上正是使魔方的復原變得困難的主要原因。舉個例子來說，26個英文字母在相鄰字母的交換之下共有約400億億億種組合，遠遠多于魔方顏色的組合數，但通過相鄰字母的交換將隨意排列的26個英文字母復原成從A到Z的初始排列卻非常簡單。

(4)確切地說是取5次嘗試中居中的3次成績的平均值。

(5)為了使這一問題有意義，當然首先要定義什么是轉動。在對魔方的數學研究中，轉動是指將魔方的任意一個（包含9個小方塊的）面沿順時針或逆時針方向轉動90°或180°，對每個面來說，這樣的轉動共有3種。（請讀者想一想，為什么不是4種？）由于魔方有6個面，因此它的基本轉動方式共有18種。

(6)確切地說，是減少至1/96，或45億億種組合。

(7)科先巴的新思路是本文介紹的一系列計算研究的起點，但并不是最早的魔方算法。早在1981年，目前在美國田納西大學（University of Tennessee），當時在倫敦南岸大學（London South Bank University）的數學家西斯爾斯韋特（Morwen Thistlethwaite）就提出了一種算法，被稱為西斯爾斯韋特算法（Thistlethwaite algorithm）。西斯爾斯韋特算法可保證通過不超過52次轉動復員魔方的任意一種顏色組合（相當于證明了上帝之數不超過52），在科先巴新思路問世之前的1991年，這一數字曾被壓縮到42。

(8)確切地說，是18種基本轉動方式中有10種自成系列，由此形成的顏色組合共有8！×8！×4！/2（約195億）種。

(9)他們所宣布的證明完成時間為2010年7月。