科學(xué)家證明還原任意魔方最多需20步.doc

科學(xué)家15年證明還原任意魔方最多需20步 魔方由匈牙利埃爾諾-魯比克教授于1974年所發(fā)明，曾經(jīng)是世界上最暢銷的智力玩具。據(jù)國(guó)外媒體報(bào)道，相信許多人都玩過魔方，但是此前沒有人知道任意組合的魔方的最小還原步數(shù)究竟是多少。這一問題困擾了數(shù)學(xué)家長(zhǎng)達(dá)三十多年，這個(gè)最小還原步數(shù)也被稱為“上帝之?dāng)?shù)”。美國(guó)加利福尼亞州科學(xué)家（Morley Davidson, John Dethridge, Herbert Kociemba, 和Tomas Rokicki），近日利用計(jì)算機(jī)破解了這一謎團(tuán)，他們證明任意組合的魔方均可以在20步之內(nèi)還原，“上帝之?dāng)?shù)”正式定為20(Gods Number is 20)。 這支研究團(tuán)隊(duì)位于美國(guó)加利福尼亞州帕洛阿爾托市。科學(xué)家們通過計(jì)算機(jī)計(jì)算和證明，任意組合的魔方都可以在20步內(nèi)還原。這一結(jié)果表明，大約有10萬多種的起始狀態(tài)恰好可以在20步內(nèi)還原。 利用谷歌公司計(jì)算機(jī)強(qiáng)大的計(jì)算能力，研究人員檢驗(yàn)了魔方任何可能的混亂狀態(tài)(確切數(shù)字為43,252,003,274,489,856,000約合4.31019)。美國(guó)俄亥俄州肯特州立大學(xué)數(shù)學(xué)家莫雷-戴維德森教授也是研究人員之一，他表示，“我們現(xiàn)在可以肯定，這個(gè)上帝之?dāng)?shù)就是20。對(duì)于我來說，我也回到了原地。魔方伴隨著我成長(zhǎng)，這也是我為什么深入研究這個(gè)數(shù)學(xué)問題的原因。這個(gè)謎團(tuán)引起了人們的廣泛關(guān)注，它也許是人類歷史上最受歡迎的謎語了?！笨茖W(xué)家們的初步研究成果發(fā)表于在線網(wǎng)站上，但戴維德森表示，他們準(zhǔn)備將研究成果提交給雜志正式發(fā)表。 程序員托馬斯-羅基花了15年的時(shí)間，致力于尋找這個(gè)謎團(tuán)的答案。據(jù)羅基介紹，研究團(tuán)隊(duì)所采用的算法可以在1秒鐘內(nèi)嘗試10億種可能，此前的計(jì)算機(jī)算法1秒鐘內(nèi)只能處理4000種可能。 為了讓問題簡(jiǎn)單化，研究團(tuán)隊(duì)采用了一種所謂“群論”的數(shù)學(xué)技術(shù)。他們首先將魔方所有可能的起始狀態(tài)集分成22億個(gè)集合，每個(gè)集合包含了195億個(gè)可能的狀態(tài)。集合的分配原則是這些可能的狀態(tài)是如何應(yīng)對(duì)一組10個(gè)可能的還原步驟。再通過魔方不同的對(duì)稱性，這種分組技術(shù)使得研究團(tuán)隊(duì)將集合數(shù)減少到5600萬個(gè)。 研究人員所采用的算法可以快速將這些還原步驟與恰當(dāng)?shù)钠鹗键c(diǎn)匹配起來，從而實(shí)現(xiàn)在20秒內(nèi)處理一個(gè)集合中的195億種可能。對(duì)于普通的家用電腦來說，以這樣的速度完成整個(gè)處理任務(wù)需要大約35年時(shí)間。 2007年，每日電訊報(bào)曾經(jīng)報(bào)道稱，任意組合的魔方均可在26步內(nèi)還原。當(dāng)然，還有其他的報(bào)道稱已證明出更少的還原步驟。2008 年七月， 來自世界各地的很多最優(yōu)秀的魔方玩家聚集在捷克共和國(guó) (Czech Republic) 中部的帕爾杜比采 (Pardubice)， 參加魔方界的重要賽事： 捷克公開賽。 在這次比賽上， 荷蘭玩家阿克斯迪杰克 (E. Akkersdijk) 創(chuàng)下了一個(gè)驚人的紀(jì)錄： 只用 7.08 秒就復(fù)原一個(gè)顏色被徹底打亂的魔方。 無獨(dú)有偶， 在這一年的八月， 人們?cè)谘芯磕Х奖澈蟮臄?shù)學(xué)問題上也取得了重要進(jìn)展。 在本文中， 我們就來介紹一下魔方以及它背后的數(shù)學(xué)問題。一. 風(fēng)靡世界的玩具1974 年春天， 匈牙利布達(dá)佩斯應(yīng)用藝術(shù)學(xué)院 (Budapest College of Applied Arts) 的建筑學(xué)教授魯比克 (E. Rubik) 萌生了一個(gè)有趣的念頭， 他想設(shè)計(jì)一個(gè)教學(xué)工具來幫助學(xué)生直觀地理解空間幾何的各種轉(zhuǎn)動(dòng)。 經(jīng)過思考， 他決定制作一個(gè)由一些小方塊組成的， 各個(gè)面能隨意轉(zhuǎn)動(dòng)的 333 的立方體。 這樣的立方體可以很方便地演示各種空間轉(zhuǎn)動(dòng)。隨后魔方風(fēng)靡全球， 其原因最大的魔力就在于其數(shù)目驚人的顏色組合。 一個(gè)魔方出廠時(shí)每個(gè)面各有一種顏色， 總共有六種顏色，（一般為 ：黃、白、綠、藍(lán)、紅、橙） 但這些顏色被打亂后， 所能形成的組合數(shù)卻多達(dá) 4325 億億。 如果我們將這些組合中的每一種都做成一個(gè)魔方， 這些魔方排在一起， 可以從地球一直排到 250 光年外的遙遠(yuǎn)星空。 也就是說， 如果我們?cè)谶@樣一排魔方的一端點(diǎn)上一盞燈， 那燈光要在 250 年后才能照到另一端。 如果哪位勤勉的玩家想要嘗試所有的組合， 哪怕他不吃、 不喝、 不睡， 每秒鐘轉(zhuǎn)出十種不同的組合， 也要花 1500 億年的時(shí)間才能如愿 (作為比較， 我們的宇宙目前還不到 140 億歲)。 與這樣的組合數(shù)相比， 廣告商們常用的 “成千上萬”、 “數(shù)以億計(jì)”、 “數(shù)以十億計(jì)” 等平日里虛張聲勢(shì)、 忽悠顧客的形容詞反倒變成了難得的謙虛。 我們可以很有把握地說， 假如不掌握訣竅地隨意亂轉(zhuǎn)， 一個(gè)人哪怕從宇宙大爆炸之初就開始玩魔方， 也幾乎沒有任何希望將一個(gè)色彩被打亂的魔方復(fù)原。二. 魔方與 “上帝之?dāng)?shù)”魔方的玩家多了， 相互間的比賽自然是少不了的。 自 1981 年起， 魔方愛好者們開始舉辦世界性的魔方大賽， 從而開始締造自己的世界紀(jì)錄。 這一紀(jì)錄被不斷地刷新著， 到本文寫作之時(shí)為止， 復(fù)原魔方的最快紀(jì)錄 - 如我們?cè)诒疚拈_頭提到的 - 已經(jīng)達(dá)到了令人吃驚的 7.08 秒。 當(dāng)然， 單次復(fù)原的紀(jì)錄存在一定的偶然性， 為了減少這種偶然性， 自 2003 年起， 魔方大賽的冠軍改由多次復(fù)原的平均成績(jī)來決定， 目前這一平均成績(jī)的世界紀(jì)錄為 11.28 秒。 這些記錄的出現(xiàn)， 表明魔方雖有天文數(shù)字般的顏色組合， 但只要掌握竅門， 將任何一種組合復(fù)原所需的轉(zhuǎn)動(dòng)次數(shù)卻并不多。那么， 最少需要多少次轉(zhuǎn)動(dòng)， 才能確保無論什么樣的顏色組合都能被復(fù)原呢？ 這個(gè)問題引起了很多人， 尤其是數(shù)學(xué)家的興趣。 這個(gè)復(fù)原任意組合所需的最少轉(zhuǎn)動(dòng)次數(shù)被數(shù)學(xué)家們戲稱為 “上帝之?dāng)?shù)” (Gods number)， 而魔方這個(gè)玩具世界的寵兒則由于這個(gè) “上帝之?dāng)?shù)” 一舉侵入了學(xué)術(shù)界。要研究 “上帝之?dāng)?shù)”， 首先當(dāng)然要研究魔方的復(fù)原方法。 在玩魔方的過程中， 人們?cè)缇椭溃?將任意一種給定的顏色組合復(fù)原都是很容易的， 這一點(diǎn)已由玩家們的無數(shù)杰出紀(jì)錄所示范。 不過魔方玩家們所用的復(fù)原方法是便于人腦掌握的方法， 卻不是轉(zhuǎn)動(dòng)次數(shù)最少的， 因此無助于尋找 “上帝之?dāng)?shù)”。 尋找轉(zhuǎn)動(dòng)次數(shù)最少的方法是一個(gè)有一定難度的數(shù)學(xué)問題。 當(dāng)然， 這個(gè)問題是難不倒數(shù)學(xué)家的。 早在二十世紀(jì)九十年代中期， 人們就有了較實(shí)用的算法， 可以用平均十五分鐘左右的時(shí)間找出復(fù)原一種給定顏色組合的最少轉(zhuǎn)動(dòng)次數(shù)。 從理論上講， 如果有人能對(duì)每一種顏色組合都找出這樣的最少轉(zhuǎn)動(dòng)次數(shù)， 那么這些轉(zhuǎn)動(dòng)次數(shù)中最大的一個(gè)無疑就是 “上帝之?dāng)?shù)”。 但可惜的是， 4325 億億這個(gè)巨大的數(shù)字成為了人們窺視 “上帝之?dāng)?shù)” 的攔路虎。 如果采用上面提到的算法， 哪怕用一億臺(tái)機(jī)器同時(shí)計(jì)算， 也要超過一千萬年的時(shí)間才能完成?？磥硇U干是行不通的， 數(shù)學(xué)家們于是便求助于他們的老本行： 數(shù)學(xué)。 從數(shù)學(xué)的角度看， 魔方的顏色組合雖然千變?nèi)f化， 其實(shí)都是由一系列基本的操作 (即轉(zhuǎn)動(dòng)) 產(chǎn)生的， 而且那些操作還具有幾個(gè)非常簡(jiǎn)單的特點(diǎn)， 比如任何一個(gè)操作都有一個(gè)相反的操作 (比如與順時(shí)針轉(zhuǎn)動(dòng)相反的操作就是逆時(shí)針轉(zhuǎn)動(dòng))。 對(duì)于這樣的操作， 數(shù)學(xué)家們的軍火庫(kù)中有一種非常有效的工具來對(duì)付它， 這工具叫做群論 (group theory)， 它早在魔方問世之前一百四十多年就已出現(xiàn)了。 據(jù)說德國(guó)數(shù)學(xué)大師希爾伯特 (D. Hilbert) 曾經(jīng)表示， 學(xué)習(xí)群論的竅門就是選取一個(gè)好的例子。 自魔方問世以來， 數(shù)學(xué)家們已經(jīng)寫出了好幾本通過魔方講述群論的書。 因此， 魔方雖未成為空間幾何的教學(xué)工具， 卻在一定程度上可以作為學(xué)習(xí)群論的 “好的例子”。對(duì)魔方研究來說， 群論有一個(gè)非常重要的優(yōu)點(diǎn)， 就是它可以充分利用魔方的對(duì)稱性。 我們前面提到 4325 億億這個(gè)巨大數(shù)字時(shí)， 其實(shí)有一個(gè)疏漏， 那就是并未考慮到魔方作為一個(gè)立方體所具有的對(duì)稱性。 由此導(dǎo)致的結(jié)果， 是那 4325 億億種顏色組合中有很多其實(shí)是完全相同的， 只是從不同的角度去看 (比如讓不同的面朝上或者通過鏡子去看) 而已。 因此， 4325 億億這個(gè)令人望而生畏的數(shù)字實(shí)際上是 “注水豬肉”。 那么， 這 “豬肉” 中的 “水份” 占多大比例呢？ 說出來嚇大家一跳： 占了將近 99%！ 換句話說， 僅憑對(duì)稱性一項(xiàng)， 數(shù)學(xué)家們就可以把魔方的顏色組合減少兩個(gè)數(shù)量級(jí)。但減少兩個(gè)數(shù)量級(jí)對(duì)于尋找 “上帝之?dāng)?shù)” 來說還遠(yuǎn)遠(yuǎn)不夠， 因?yàn)槟遣贿^是將前面提到的一千萬年的時(shí)間減少為了十萬年。 對(duì)于解決一個(gè)數(shù)學(xué)問題來說， 十萬年顯然還是太長(zhǎng)了， 而且我們也并不指望真有人能動(dòng)用一億臺(tái)計(jì)算機(jī)來計(jì)算 “上帝之?dāng)?shù)”。 數(shù)學(xué)家們雖然富有智慧， 但在其它方面卻不見得很富有， 他們真正能動(dòng)用的也許只有自己書桌上的那臺(tái)機(jī)器。 因此為了尋找 “上帝之?dāng)?shù)”， 人們還需要尋找更巧妙的思路。 幸運(yùn)的是， 群論這一工具的威力遠(yuǎn)不只是用來分析象立方體的對(duì)稱性那樣顯而易見的東西， 在它的幫助下， 新的思路很快就出現(xiàn)了。三. 尋找 “上帝之?dāng)?shù)”1992 年， 德國(guó)數(shù)學(xué)家科先巴 (H. Kociemba) 提出了一種尋找魔方復(fù)原方法的新思路。 他發(fā)現(xiàn)， 在魔方的基本轉(zhuǎn)動(dòng)方式中， 有一部分可以自成系列， 通過這部分轉(zhuǎn)動(dòng)可以形成將近 200 億種顏色組合。 利用這 200 億種組合， 科先巴將魔方的復(fù)原問題分解成了兩個(gè)步驟： 第一步是將任意一種顏色組合轉(zhuǎn)變?yōu)槟?200 億種組合之一， 第二步則是將那 200 億種組合復(fù)原。 如果我們把魔方復(fù)原比作是讓一條汪洋大海中的小船駛往一個(gè)固定的目的地， 那么科先巴提出的那兩百億種顏色組合就好比是一片特殊的水域 - 一片比那個(gè)固定地點(diǎn)大了 200 億倍的特殊水域。 他提出的兩個(gè)步驟就好比是讓小船首先駛往那片特殊水域， 然后從那里駛往那個(gè)固定的目的地。 在汪洋大海中尋找一片巨大的特殊水域， 顯然要比直接尋找那個(gè)小小的目的地容易得多， 這就是科先巴的新思路的優(yōu)越之處。但即便如此， 要用科先巴的方法對(duì) “上帝之?dāng)?shù)” 進(jìn)行估算仍不是一件容易的事。 尤其是， 要想進(jìn)行快速的計(jì)算， 最好是將復(fù)原那 200 億種顏色組合的最少轉(zhuǎn)動(dòng)次數(shù) (這相當(dāng)于是那片 “特殊水域” 的地圖) 存儲(chǔ)在計(jì)算機(jī)的內(nèi)存中， 這大約需要 300 兆的內(nèi)存。 300 兆在今天看來是一個(gè)不太大的數(shù)目， 但在科先巴提出新思路的那年， 普通機(jī)器的內(nèi)存連它的十分之一都遠(yuǎn)遠(yuǎn)不到。 因此直到三年后， 才有人利用科先巴的方法給出了第一個(gè)估算結(jié)果。 此人名叫里德 (M. Reid)， 是美國(guó)中佛羅里達(dá)大學(xué) (Unversity of Central Florida) 的數(shù)學(xué)家。 1995 年， 里德通過計(jì)算發(fā)現(xiàn)， 最多經(jīng)過 12 次轉(zhuǎn)動(dòng)， 就可以將魔方的任意一種顏色組合變?yōu)榭葡劝湍?200 億種組合之一； 而最多經(jīng)過 18 次轉(zhuǎn)動(dòng)， 就可以將那 200 億種組合中的任意一種復(fù)原。 這表明， 最多經(jīng)過 12+18=30 次轉(zhuǎn)動(dòng)， 就可以將魔方的任意一種顏色組合復(fù)原。在得到上述結(jié)果后， 里德很快對(duì)自己的計(jì)算作了改進(jìn)， 將結(jié)果從 30 減少為了 29， 這表明 “上帝之?dāng)?shù)” 不會(huì)超過 29。 此后隨著計(jì)算機(jī)技術(shù)的發(fā)展， 數(shù)學(xué)家們對(duì)里德的結(jié)果又作進(jìn)一步的改進(jìn)， 但進(jìn)展并不迅速。 直到 11 年后的 2006 年， 奧地利開普勒大學(xué) (Johannes Kepler University) 符號(hào)計(jì)算研究所 (Research Institute for Symbolic Computation) 的博士生拉杜 (Silviu Radu) 才將結(jié)果推進(jìn)到了 27。 第二年， 即 2007 年， 美國(guó)東北大學(xué) (Northeastern University) 的計(jì)算機(jī)科學(xué)家孔克拉 (D. Kunkle) 和庫(kù)伯曼 (G. Cooperman) 又將結(jié)果推進(jìn)到了 26， 他們的工作采用了并行計(jì)算系統(tǒng)， 所用最大存儲(chǔ)高達(dá) 700 萬兆， 所耗計(jì)算時(shí)間則長(zhǎng)達(dá) 8000 小時(shí) (相當(dāng)于將近一年的 24 小時(shí)不停歇計(jì)算)。這些計(jì)算結(jié)果表明， “上帝之?dāng)?shù)” 不會(huì)超過 26。 但是， 所有這些計(jì)算的最大優(yōu)點(diǎn) - 即利用科先巴的那片 “特殊水域” - 同時(shí)也是它們最致命的弱點(diǎn)， 因?yàn)樗鼈兘o出的復(fù)原方法都必須經(jīng)過那片特殊水域。 可事實(shí)上， 很多顏色組合的最佳復(fù)原方法根本就不經(jīng)過那片特殊水域， 比如緊鄰目的地， 卻恰好不在特殊水域中的任何小船， 顯然都沒必要象大陸臺(tái)灣的直航包機(jī)一樣， 故意從那片特殊水域繞一下才前往目的地。 因此， 用科先巴的思路得到的復(fù)原方法未必是最佳的， 由此對(duì) “上帝之?dāng)?shù)” 所做的估計(jì)也極有可能是高估?？墒?， 如果不引進(jìn)科先巴的特殊水域， 計(jì)算量又實(shí)在太大， 怎么辦呢？ 數(shù)學(xué)家們決定采取折衷的手段， 即擴(kuò)大那片特殊水域的 “面積”， 因?yàn)樘厥馑蛟酱螅?最佳復(fù)原路徑恰好經(jīng)過它的可能性也就越大 (當(dāng)然， 計(jì)算量也會(huì)有相應(yīng)的增加)。 2008 年， 研究 “上帝之?dāng)?shù)” 長(zhǎng)達(dá) 15 年之久的計(jì)算機(jī)高手羅基奇 (T. Rokicki) 運(yùn)用了相當(dāng)于將科先巴的特殊水域擴(kuò)大幾千倍的巧妙方法， 在短短幾個(gè)月的時(shí)間內(nèi)對(duì) “上帝之?dāng)?shù)” 連續(xù)發(fā)動(dòng)了四次猛烈攻擊， 將它的估計(jì)值從 25 一直壓縮到了 22。 截至本文寫作之時(shí)為止， 這是全世界范圍內(nèi)的最佳結(jié)果。 羅基奇的計(jì)算得到了電影特效制作商索尼影像 (Sony Pictures Imageworks) 的支持， 這家曾為 “蜘蛛人” 等著名影片制作特效的公司向羅基奇提供了相當(dāng)于 50 年不停歇計(jì)算所需的計(jì)算機(jī)資源。因此， 現(xiàn)在我們已經(jīng)知道， “上帝之?dāng)?shù)” 一定不超過 22。 但是， 羅基奇的特殊水域雖然很大， 終究仍有很多顏色組合的最佳復(fù)原方法是無需經(jīng)過那片特殊水域的， 因此， “上帝之?dāng)?shù)” 很可能比 22 更小。 那么， 它究竟是多少呢？ 人們雖然還無法確知， 但種種跡象表明， 它極有可能是 20。 這是因?yàn)椋?人們?cè)谶^去這么多年的所有努力 - 其中包括羅基奇直接計(jì)算過的大約四千萬億種顏色組合 - 中， 都從未遇到任何必須用 20 次以上轉(zhuǎn)動(dòng)才能復(fù)原的顏色組合， 這表明 “上帝之?dāng)?shù)” 很可能不大于 20。 另一方面， 人們已經(jīng)發(fā)現(xiàn)了幾萬種顏色組合， 它們必須要用 20 次轉(zhuǎn)動(dòng)才能復(fù)原， 這表明 “上帝之?dāng)?shù)” 不可能小于 20。 將這兩方面綜合起來， 數(shù)學(xué)家們普遍相信， “上帝之?dāng)?shù)” 的真正數(shù)值就是 20。 當(dāng)然， “上帝” 也許是微妙的， 我們誰也無法保證它是否會(huì)在某個(gè)角落為我們留下驚訝， 我們唯一有理由相信的也許是： 這個(gè)游戲與數(shù)學(xué)交織而成的神秘的 “上帝之?dāng)?shù)” 距離它水落石出的那一天已不太遙遠(yuǎn)了。注釋魔方是魯比克自己為這一立方體所取的名字， 魯比克方塊則是美國(guó)玩具公司 Ideal Toys 所取的名字。 在西方國(guó)家， 魯比克方塊這一名稱更為流行， 在中國(guó)， 則是魔方這一名稱更為流行。 另外要提醒讀者的是， 魔方有很多種類， 本文介紹的 333 魔方只是其中最常見的一種。具體的計(jì)算是這樣的： 在組成魔方的小立方體中， 有 8 個(gè)是頂點(diǎn)， 它們之間有 8! 種置換； 這些頂點(diǎn)每個(gè)有 3 種顏色， 在朝向上有 37 種組合 (由于結(jié)構(gòu)所限， 魔方的頂點(diǎn)只有 7 個(gè)能有獨(dú)立朝向)。 類似的， 魔方有 12 個(gè)小立方體是邊， 它們之間有 12!/2 種置換 (之所以除以 2， 是因?yàn)槟Х降捻旤c(diǎn)一旦確定， 邊的置換就只有一半是可能的)； 這些邊每個(gè)有兩種顏色， 在朝向上有 211 種組合 (由于結(jié)構(gòu)所限， 魔方的邊只有 11 個(gè)能有獨(dú)立朝向)。 因此， 魔方的顏色組合總數(shù)為 8!3712!211/2 = 43252003274489856000， 即大約 4325 億億。 另外值得一提的是， 倘若我們?cè)试S將魔方拆掉重組， 則前面提到的結(jié)構(gòu)限定將不復(fù)存在， 它的顏色組合數(shù)將多達(dá) 51900 億億種。 不過組合數(shù)的增加并不意味著復(fù)原的難度變大， 魔方結(jié)構(gòu)對(duì)組合數(shù)的限制實(shí)際上正是使魔方的復(fù)原變得困難的主要原因。 舉個(gè)例子來說， 二十六個(gè)英文字母在相鄰字母的交換之下共有約 400 億億億種組合， 遠(yuǎn)遠(yuǎn)多于魔方顏色的組合數(shù)， 但通過相鄰字母的交換將隨意排列的二十六個(gè)英文字母復(fù)原成從 A 到 Z 的初始排列卻非常簡(jiǎn)單。確切地說是取五次嘗試中居中的三次成績(jī)的平均值。為了使這一問題有意義， 當(dāng)然首先要定義什么是轉(zhuǎn)動(dòng)。 在對(duì)魔方的數(shù)學(xué)研究中， 轉(zhuǎn)動(dòng)是指將魔方的任意一個(gè) (包含 9 個(gè)小方塊的) 面沿順時(shí)針或逆時(shí)針方向轉(zhuǎn)動(dòng) 90 或 180， 對(duì)每個(gè)面來說， 這樣的轉(zhuǎn)動(dòng)共有 3 種 (請(qǐng)讀者想一想， 為什么不是 4 種？)。 由于魔方有 6 個(gè)面， 因此它的基本轉(zhuǎn)動(dòng)方式共有 18 種。確切地說， 是減少至 1/96， 或 45 億億種組合。確切地說， 是 18 種基本轉(zhuǎn)動(dòng)方式中有 10 種自成系列， 由此形成的顏色組合共有 8!8!4!/2 (約 195 億) 種。參考文獻(xiàn)D. Kunkle and G. Cooperman, Twenty-Six Moves Suffice for Rubiks Cube, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 07), ACM Press.J. Palmer, Cracking the Hardest Mystery of the Rubiks Cube, NewScientist, 09 August 2008.T. Rokicki, Twenty-Five Moves Suffice for Rubiks Cube, arXiv:0803.3435 .S. Radu, New Upper Bounds on Rubiks Cube.W. D. Joyner, Mathematics of the Rubiks cube.-補(bǔ)注Kociemba 的算法是本文介紹的一系列計(jì)算研究的起點(diǎn)， 但并不是最早的魔方算法。 早在 1981 年， 目前在美國(guó)田納西大學(xué) (University of Tennessee)， 當(dāng)時(shí)在倫敦南岸大學(xué) (London South Bank University) 的數(shù)學(xué)家 M. Thistlethwaite 就提出了一種算法， 被稱為 Thistlethwaite 算法。 Thistlethwaite 算法可保證通過不超過 52 次轉(zhuǎn)動(dòng)復(fù)員魔方的任意一種顏色組合 (因此上帝之?dāng)?shù)不超過 52)， 在 Kociemba 的算法問世之前的 1991 年， 這一數(shù)字曾被壓縮到 42。 在這里， 本人要感謝老陶網(wǎng)友來信提醒我注意 Thistlethwaite 的算法。 2009-01-23平均成績(jī)的世界紀(jì)錄在 2009 年的華沙公開賽上已被改寫為 10.63 秒。 2009-09-092010 年 8 月， 我們?cè)谡闹刑岬竭^的研究上帝之?dāng)?shù)的 “元老” 科先巴、 “新秀” 羅基奇， 及另兩位合作者 (M. Davidson 和 J. Dethridge) 共同宣布完成了對(duì)上帝之?dāng)?shù)是 20 的證明 (他們所列的證明完成時(shí)間為 2010 年 7 月)。 他們的證明得到了谷歌公司 (Google) 提供的相當(dāng)于 Intel Nehalem 四核心 2.8GHz 處理器 35 年不停歇計(jì)算所需的計(jì)算機(jī)資源的支持。相關(guān)內(nèi)容：A History of Gods NumberBy 1980, a lower bound of 18 had been established for Gods Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results. DateLower boundUpper boundGapNotes and LinksJuly, 1981185234Morwen Thistlethwaite proves 52 moves suffice.April, 1992184224Hans Kl