尋找魔方的上帝之?dāng)?shù)

幾乎從魔方的誕生之日起，某些人就一直在尋找一個(gè)神秘的數(shù)字——復(fù)原任意一個(gè)魔方所需的最少步驟——上帝之?dāng)?shù)。

阿克斯戴克（Erik Akkersdijk）手里握著他的魔方，靜止著不動(dòng)。四周?chē)鷿M了人，目光都聚集在他的手上。離得近的人能看清幾個(gè)邊塊、角塊和棱塊的排列，暗自琢磨著最快的解法。也就等了幾秒鐘，阿克斯戴克把手上的魔方放下，雙手同時(shí)按下邊上的計(jì)時(shí)器，再利落地拿起魔方，似乎只是隨便轉(zhuǎn)動(dòng)了幾下，6 個(gè)面居然就對(duì)出來(lái)了，只有7.08 秒！房間里一片歡呼，這是2008 年7 月，一個(gè)新的魔方速度紀(jì)錄在捷克公開(kāi)賽上誕生了。

阿克斯戴克是魔方世界中的“快派”，追求在半分鐘甚至10 秒內(nèi)解決一個(gè)被打亂的魔方。如果你對(duì)魔方有一知半解，那么就只知有快派。事實(shí)上，在魔方世界中還有另外一派。這一派的歷史可以回溯到20 世紀(jì)80 年代初，魔方剛剛在全世界風(fēng)靡的時(shí)候。從那時(shí)起，他們就開(kāi)始尋找一個(gè)神秘的數(shù)字——魔方的上帝之?dāng)?shù)。確切地說(shuō)，如何以最簡(jiǎn)單的步驟破解一個(gè)處于“最亂狀態(tài)”的魔方。

上帝的套路如何

1980 年，匈牙利講師埃爾諾#8226; 魯比克（Erno Rubik）發(fā)明的“魔術(shù)方塊”開(kāi)始在歐美暢銷(xiāo)，幾乎成為人手一個(gè)的玩具。與此同時(shí)，一些人開(kāi)始研究魔方。像阿科斯戴克這樣的急速玩家（Speed-cuber），想要在10 秒鐘內(nèi)解開(kāi)一個(gè)魔方，其實(shí)有一定的套路。這就好像武林中人，如果不把對(duì)方的這種套路給你講明白，即使把一個(gè)動(dòng)作反復(fù)地在你面前重放，你仍然搞不清對(duì)方在做什么。魔方的套路就是公式。掌握公式就等于摸清魔方的規(guī)律。這方面道行最深、輩分最高的要數(shù)杰西卡#8226; 弗里德里希(Jessica Fridrich)，紐約州立賓漢姆敦大學(xué)的教授。1982 年，弗里德里希首創(chuàng)了一種“中間站”技術(shù)。她發(fā)現(xiàn)在破解魔方的過(guò)程中存在一些特定的狀態(tài)，比如，在魔方的一面上以紅色方塊組成一個(gè)紅色的十字叉形狀。而不管手里的魔方怎么亂，總能在7步之內(nèi)把方塊擺成這樣。有了這個(gè)中間步驟，弗里德里希在此基礎(chǔ)上發(fā)明了一系列公式。記憶這些公式，能夠平均在56 步之內(nèi)解開(kāi)任何一個(gè)魔方。

56 算是上帝之?dāng)?shù)的最初解。不過(guò)弗里德里希發(fā)明公式的時(shí)候，這種叫法還沒(méi)開(kāi)始流行。公式為此后研究上帝之?dāng)?shù)的人提供了基本的策略，但上帝之?dāng)?shù)的名字不是她起的。同一年，亞歷山大#8226; 弗雷(Alexander H. Frey， Jr.) 與大衛(wèi)#8226; 辛格馬斯特(David Singmaster) 兩個(gè)“方塊兒（Cuber）” 寫(xiě)了一本《魔方數(shù)學(xué)手冊(cè)》(Handbook of Cubik Math)，第一次提出存在一個(gè)“上帝的數(shù)字（God`s number）”，無(wú)論多亂的魔方，都可以在一定的步數(shù)內(nèi)解開(kāi)。而之所以叫上帝之?dāng)?shù)，據(jù)說(shuō)是因?yàn)樯系圩鍪驴偸橇η蠛?jiǎn)潔。他們?cè)跁?shū)中證明這個(gè)數(shù)字介于17 到52 之間，同時(shí)還猜測(cè)，上帝之?dāng)?shù)也許是20。

在計(jì)算的時(shí)候，弗雷與辛格馬斯特借鑒了中間站技術(shù)。他們找到一種中間狀態(tài)，計(jì)算從任意混亂狀態(tài)到中間態(tài)所需的步驟，這不難。之后要做的就是從中間狀態(tài)找到最優(yōu)解。前后的步驟數(shù)相加，就得到一個(gè)上帝之?dāng)?shù)的上限值，加上一個(gè)估計(jì)得出的下限值，弗雷和新格馬斯特就把數(shù)字鎖定在一定的范圍之內(nèi)。這樣的計(jì)算需要不止一個(gè)中間站，他們有必要找出成百上千乃至上百萬(wàn)種中間狀態(tài)。這是因?yàn)?，即使一個(gè)擁有54 個(gè)色塊的普通的標(biāo)準(zhǔn)3 階魔方也能組成多達(dá)43×1018 種狀態(tài)。

這無(wú)疑增加了尋找上帝之?dāng)?shù)的難度。為了解決這個(gè)問(wèn)題，1992 年，德國(guó)人赫伯特#8226; 科齊姆巴（Herbert Kociemba）想出一個(gè)點(diǎn)子。他總結(jié)出轉(zhuǎn)動(dòng)魔方的10 個(gè)動(dòng)作，發(fā)現(xiàn)用這10 個(gè)動(dòng)作的排列組合就能夠?qū)⒁粋€(gè)排列完好的魔方轉(zhuǎn)出約200 億種狀態(tài)。科齊姆巴的發(fā)現(xiàn)簡(jiǎn)化了上帝之?dāng)?shù)的求解。他通過(guò)反向思維找到的200 億種狀態(tài)，無(wú)疑就是200 億個(gè)中間站，而從中間站到完美求解之間的步驟，都是他自己排列出來(lái)的，當(dāng)然就在這10 步之內(nèi)。他列出一張表格，將自己求得的結(jié)果羅列其中，在此基礎(chǔ)上編制了一個(gè)叫方塊探索者（Cube Explorer）的程序，專(zhuān)門(mén)用來(lái)計(jì)算從任意混亂狀態(tài)到200 億個(gè)中間站所需的步驟。1995 年，美國(guó)奧蘭多中佛羅里達(dá)大學(xué)的邁克爾#8226; 里德（Michael Raid）通過(guò)一套與Cube Explorer 相似的程序推算出上帝之?dāng)?shù)是30。

然而大多數(shù)人不太相信里德給出的答案。很多人仍堅(jiān)信弗雷與辛格馬斯特最初所猜測(cè)的上帝之?dāng)?shù)，20。而科齊姆巴的程序也確實(shí)有一個(gè)問(wèn)題，那就是如果遇到10 個(gè)規(guī)定動(dòng)作之外的情況怎么辦。比如，拿一個(gè)排列完好的魔方來(lái)只轉(zhuǎn)一下，但是這個(gè)動(dòng)作卻不在10 個(gè)動(dòng)作之內(nèi)。科齊姆巴的程序只認(rèn)可10個(gè)標(biāo)準(zhǔn)動(dòng)作和200 億個(gè)中間站。

始終如一的運(yùn)算難題

于是又過(guò)了10 年。2007 年，美國(guó)東北大學(xué)計(jì)算機(jī)科學(xué)系的研究生丹#8226; 昆克（Dan Kunkle） 和教授吉恩#8226; 庫(kù)珀曼（Gene Cooperman）用20 臺(tái)每秒1 億次，擁有7tb 存儲(chǔ)器的計(jì)算機(jī)以及新的算法準(zhǔn)備再次挑戰(zhàn)上帝之?dāng)?shù)。他們?cè)O(shè)計(jì)了一個(gè)新的平行演算法，在不可思議的整整8000 個(gè)小時(shí)的運(yùn)算之后，得到了一個(gè)新的結(jié)果，26。昆克和庫(kù)珀曼的結(jié)果讓魔方界很興奮，因?yàn)?0 年來(lái)，在尋找上帝之?dāng)?shù)方面，數(shù)學(xué)家們一直沒(méi)有大的突破。但在興 .之余，兩個(gè)人在裝備上的瓶頸開(kāi)始凸顯出來(lái)。在經(jīng)過(guò)漫長(zhǎng)的瘋狂運(yùn)算之后，兩個(gè)人的電腦已經(jīng)累得吐血。但想要得到更精準(zhǔn)的數(shù)據(jù)，他們還需要更強(qiáng)的電腦以及上千小時(shí)的額外運(yùn)算。在沒(méi)有條件搞到新設(shè)備，也沒(méi)有更多時(shí)間的情況下，兩個(gè)人再也無(wú)能為力。上帝之?dāng)?shù)的終解好像暫時(shí)停留在了26。

托馬斯#8226; 羅齊（Tomas Rokicki）就是在這時(shí)得手的。作為一個(gè)骨灰級(jí)的方塊兒，斯坦福大學(xué)的羅齊早從15 年前就開(kāi)始尋找上帝之?dāng)?shù)。在奧地利數(shù)學(xué)家拉杜（Silviu Radu）的幫助下，羅齊在科齊姆巴當(dāng)年設(shè)計(jì)的Cube Explorer 程序的基礎(chǔ)上改進(jìn)了上帝之?dāng)?shù)的算法?？讫R姆巴的程序是對(duì)每一種混亂的狀態(tài)都進(jìn)行多次計(jì)算，每次找出一條可能的路徑，然后從多次的結(jié)果中選出一條最簡(jiǎn)短的路徑。羅齊發(fā)現(xiàn)這其實(shí)就是關(guān)于一類(lèi)有關(guān)聯(lián)的狀態(tài)的運(yùn)算，于是決定充分利用這一點(diǎn)。

羅齊將整個(gè)上帝之?dāng)?shù)問(wèn)題分成20 億個(gè)部分，每部分都包含大約200 億種有關(guān)聯(lián)的狀態(tài)。羅齊的程序每次只對(duì)20 億份中的一份進(jìn)行運(yùn)算。而時(shí)間“大概花去了25 分鐘”。2008 年3 月，羅齊得到了新的上帝之?dāng)?shù)，25，并將結(jié)果發(fā)表在著名的論文預(yù)印本網(wǎng)站arXiv 上。

走到這一步，羅齊同樣遭遇了設(shè)備上的瓶頸。但幸運(yùn)的是，他的研究受到了另一個(gè)人的關(guān)注。

索尼圖形圖像工作室是一家專(zhuān)門(mén)制作視覺(jué)特效的公司，曾經(jīng)為影片《蜘蛛俠３》和《我是傳奇》制作過(guò)電腦動(dòng)畫(huà)。該公司的軟件工程師約翰#8226; 威爾伯恩（John Welborn）在網(wǎng)站上看到了羅齊的論文，就立即按照上面的地址聯(lián)系羅齊，表示愿意把公司數(shù)百臺(tái)電腦的空閑時(shí)間都借給他。這可幫了羅齊的大忙。經(jīng)過(guò)斷斷續(xù)續(xù)的運(yùn)算，2008 年4 月，羅齊和威爾伯恩將上帝之?dāng)?shù)的上限精確到24，兩周后又精確到23。

想要進(jìn)一步證明上帝之?dāng)?shù)最終為20，還需要進(jìn)行比目前多數(shù)百倍的運(yùn)算?！凹词褂媚壳笆澜缟献羁斓挠?jì)算機(jī)，也需要運(yùn)算38 天，”對(duì)自己的研究有幸能用上超級(jí)計(jì)算機(jī)，托馬斯#8226; 羅齊還不敢奢望。而索尼方面也不再準(zhǔn)備繼續(xù)幫助羅齊了。看來(lái)，如果沒(méi)有人找到一種新的捷徑來(lái)幫助運(yùn)算，那么可能在相當(dāng)長(zhǎng)一段時(shí)間內(nèi)，上帝之?dāng)?shù)的答案就不可能比23更接近20。

Tips：

魯比克的方塊

20 世紀(jì)80 年代初，匈牙利布達(dá)佩斯工藝美術(shù)學(xué)院的講師埃爾諾#8226; 魯比克（左圖）發(fā)明了魔方。其實(shí)在魯比克的魔方進(jìn)入西歐和美國(guó)市場(chǎng)前，已經(jīng)有類(lèi)似的玩具注冊(cè)了英國(guó)和美國(guó)的專(zhuān)利。但是這都不能阻擋人們把它稱之為“魯比克的方塊”。

基本竅門(mén)：

6 個(gè)中心塊的相對(duì)位置保持不變。拆開(kāi)一個(gè)魔方就會(huì)發(fā)現(xiàn)，它的骨架就是一個(gè)由6 個(gè)中心塊構(gòu)成的xyz 坐標(biāo)系。

玩魔方的各種流派

普通玩法

這類(lèi)玩法適合拿魔方當(dāng)作放松和娛樂(lè)的愛(ài)好者。他們通常僅僅滿足于復(fù)原一個(gè)魔方，不

會(huì)追求更高的標(biāo)準(zhǔn)。

競(jìng)速玩法

世界上大多數(shù)魔方高手使用的方法都是杰西卡#8226; 弗里德里希發(fā)明的。競(jìng)速?gòu)?fù)原有幾個(gè)要點(diǎn)：使用的方法要最簡(jiǎn)便，但是隨之產(chǎn)生的問(wèn)題是步驟越少，需要記憶的公式就越多；擁有方法和好的魔方不是最重要的，雙手能夠熟練的轉(zhuǎn)動(dòng)魔方才能有最高的效率。

最少步驟還原

最為艱難的玩法。在這種玩法或者比賽中，不能轉(zhuǎn)動(dòng)魔方，只能用眼睛觀察魔方的狀態(tài)，然后思考出最少的步驟來(lái)解決魔方。目前的世界紀(jì)錄是28 步還原，耗時(shí)兩個(gè)半小時(shí)。

盲眼玩法

稱作盲擰或稱盲解。其定義就是不用眼睛觀看魔方，進(jìn)行復(fù)原的過(guò)程。計(jì)時(shí)是從第一眼看到魔方開(kāi)始的，也就是說(shuō)記憶魔方的時(shí)間也算在總時(shí)間內(nèi)。這種玩法對(duì)一個(gè)人的記憶力和空間想像力有極大的考驗(yàn)。目前世界紀(jì)錄為波蘭人Rafal Guzewicz 創(chuàng)造的54.22 秒。

單手玩法

即以單手轉(zhuǎn)動(dòng)魔方進(jìn)行復(fù)原，或稱單擰。目前世界紀(jì)錄為法國(guó)人Thibaut Jacquinot 創(chuàng)造的15.81 秒。