在所有益智游戲中穷吮，魔方是當(dāng)之無(wú)愧的王者逻翁。魔方從發(fā)明至今已風(fēng)魔全球三十多年饥努，人們卻一直樂(lè)此不疲，不斷探索魔方提出的問(wèn)題八回。
魔方是人類發(fā)明的所有益智游戲中的佼佼者酷愧。首先，其他任何游戲都沒(méi)能吸引如此多的關(guān)注缠诅，引來(lái)眾人發(fā)表諸多相關(guān)文章和書(shū)籍溶浴，討論其中奧妙。其次管引，魔方頗具難度士败，數(shù)百萬(wàn)人開(kāi)展各種競(jìng)賽，屢創(chuàng)壯舉……這些成就愈顯奇特褥伴，甚至接近瘋狂谅将。同時(shí)，魔方啟發(fā)了數(shù)百種機(jī)械益智游戲重慢，衍生游戲往往和魔方一樣驚人〖⒈郏現(xiàn)在，我們也可以在電腦上進(jìn)行模擬操作似踱。最后隅熙，三十年來(lái)稽煤，最復(fù)雜形態(tài)的問(wèn)題一直無(wú)解，唯有強(qiáng)大的計(jì)算機(jī)網(wǎng)絡(luò)或許才能最終將之破解囚戚。
我們還會(huì)細(xì)談這四個(gè)話題酵熙，尤其要講講已經(jīng)證實(shí)的結(jié)論：在任何情況下，20 步足以將魔方不同顏色的 6 個(gè)面還原驰坊。
巧妙的機(jī)械結(jié)構(gòu)
在 1980 年 8 月出版的法國(guó)《為了科學(xué)》（Pour la Science）雜志第 34 期里绿店，埃馬努埃爾·哈伯斯塔特發(fā)表了題為“匈牙利方塊及群理論”（Le cube hongrois et la théorie des groups）的文章，在其中描述了魔方庐橙，并基于魔方數(shù)學(xué)結(jié)構(gòu)分析提出一種還原魔方的實(shí)用方法假勿。
這篇文章讓魔方在法國(guó)風(fēng)靡一時(shí)，而人們對(duì)魔方的癡迷早已快速席卷世界各地态鳖。
回溯到此前六年转培，雕塑家及建筑學(xué)教授埃爾諾·魯比克發(fā)明了由 26 個(gè)通過(guò)巧妙機(jī)械結(jié)構(gòu)相連的小方塊組成的魔方。魔方各面由 9 個(gè)方塊（3×3）構(gòu)成浆竭，每面均可繞著平行于棱且經(jīng)過(guò)面中點(diǎn)的軸旋轉(zhuǎn)浸须。這本該是一個(gè)完整的 3×3×3 立方體，但中心位置的方塊卻替換為轉(zhuǎn)軸系統(tǒng)邦泄，使整體既相互連接删窒，又能轉(zhuǎn)動(dòng)。魔方處在初始形態(tài)時(shí)顺囊，各面都僅有一種顏色肌索，總共是藍(lán)、紅特碳、橙诚亚、綠、黃午乓、白六種站宗。把魔方各面擰幾下，不同顏色的方塊被打亂益愈，問(wèn)題就是怎樣將魔方還原到初始形態(tài)梢灭。
試著擺弄幾下，我們就能理解這個(gè)益智游戲結(jié)構(gòu)的一些基本要素蒸其。
每個(gè)面的中心塊繞著自身旋轉(zhuǎn)敏释，位置不變。它們決定著每個(gè)面的顏色枣接，可以準(zhǔn)確地表示立方體的方向颂暇。
角塊一共有 8 個(gè)，一直在頂點(diǎn)位置但惶。每個(gè)角塊有 3 個(gè)顏色不同的可見(jiàn)面耳鸯，考慮魔方每個(gè)面中心塊的顏色湿蛔，可以準(zhǔn)確判定一個(gè)角塊在魔方還原后所處的位置。
剩下 12 個(gè)就是棱中間的棱塊县爬。每個(gè)棱塊有兩種不同顏色的可見(jiàn)面阳啥，和角塊一樣，可以準(zhǔn)確判定棱塊在最終形態(tài)中所處的位置财喳。
1魔方的最難形態(tài)察迟，為了證明 20 步總能足以將魔方還原，人們?cè)谶\(yùn)算過(guò)程中得出這種極致形態(tài)耳高。圖中將 20 個(gè)還原步驟一一畫(huà)出扎瓶。你可以照著圖反向操作，給自稱魔方高手的親朋好友出個(gè)難題泌枪。
還原魔方看起來(lái)簡(jiǎn)單概荷，實(shí)際卻是塊難啃的骨頭。魔方一旦被打亂碌燕，在沒(méi)有任何幫助或從未對(duì)魔方背后的數(shù)學(xué)問(wèn)題進(jìn)行過(guò)深入研究的情況下误证，任憑怎么努力也不可能將它還原。這個(gè)游戲?qū)嵲谔y了修壕，它能大受歡迎也耐人尋味愈捅。
自 1977 年第一批魔方在匈牙利上市以來(lái)，大約有 3 億 5 千萬(wàn)個(gè)魔方被生產(chǎn)和銷售慈鸠。魔方打敗各類益智游戲蓝谨，成為各歷史階段的銷量冠軍——唯一的例外也許是Taquin（也叫作“15 塊拼圖”）。自 1879 年問(wèn)世以來(lái)林束，Taquin 游戲衍生出數(shù)千種不同版本像棘，我們無(wú)法統(tǒng)計(jì)到底一共制造稽亏、銷售了多少壶冒。盡管魔方被造假者無(wú)恥地剽竊、復(fù)制截歉，魔方還是為其發(fā)明者埃爾諾·魯比克收獲了財(cái)富和榮譽(yù)胖腾，讓他可以在后半生專心發(fā)明并制作其他益智游戲。
人們圍繞魔方的構(gòu)造理論和解答方法出版和發(fā)表了眾多書(shū)籍和文章瘪松。在互聯(lián)網(wǎng)上也有大量專門(mén)講解魔方的網(wǎng)頁(yè)咸作。每年涌現(xiàn)的大量文獻(xiàn)可追溯到 20 世紀(jì) 80 年代，那時(shí)宵睦，人們對(duì)魔方的熱情幾近狂熱记罚。喬治·赫爾姆斯編纂的文獻(xiàn)收錄了 22 種語(yǔ)言的 719 篇文章。1979 年有 14 篇著作發(fā)表壳嚎、1980 年 52 篇桐智、1981 年 174 篇末早、1982 年 70 篇、1983 年 15 篇说庭。詹姆斯·諾斯的著作《魔方的簡(jiǎn)單解法》（The Simple Solution to Rubik's Cube）是 1982 年 1 月全球銷量最大的圖書(shū)然磷，在暢銷書(shū)排行榜上停留三年之久，總共賣(mài)出了逾六百萬(wàn)冊(cè)刊驴。另有多本魔方書(shū)籍的銷量都超過(guò)了百萬(wàn)冊(cè)姿搜。
世界各地都在舉辦魔方競(jìng)賽。世界魔方協(xié)會(huì)（WCA）為眾多比賽提供贊助捆憎。
最厲害的魔方玩家不到 10 秒就能還原 3×3×3 魔方舅柜。有一點(diǎn)要說(shuō)清楚，世界魔方協(xié)會(huì)的規(guī)則允許在開(kāi)始擰魔方之前先觀察 15 秒躲惰。15 歲的澳大利亞冠軍菲利克斯·曾姆丹格斯平均用 8.5 秒就能將魔方還原业踢。他也能解決更難的 4×4×4 魔方，平均耗時(shí) 42 秒礁扮；還有極難的5×5×5魔方知举，平均耗時(shí) 68 秒。
有些記錄沒(méi)那么正規(guī)太伊，但也成為了經(jīng)典戰(zhàn)績(jī)雇锡，像體育競(jìng)賽紀(jì)錄一樣不斷被刷新。2010 年的單手?jǐn)Q魔方冠軍用時(shí) 14.7 秒僚焦。腳擰魔方冠軍用時(shí) 42 秒锰提。2008 年 11 月 16 日，米蘭·巴提克用不到 24 小時(shí)的時(shí)間復(fù)原了 4786 個(gè)魔方芳悲，打破之前 3505 個(gè)魔方的紀(jì)錄立肘。值得一提的是，巴提克連續(xù) 24 小時(shí)成功保持了每個(gè)魔方平均耗時(shí) 18.05 秒的驚人速度名扛！
2魔方主義畫(huà)派：這些畫(huà)作由 9 種像素塊構(gòu)成谅年，藝術(shù)家用足夠多的魔方，將 其一面擰成不同顏色的 9 個(gè)像素塊肮韧，用 6 種顏色耐心拼成整幅作品融蹂。類似作品 可以在www.space-invaders.com/archives.html看到。
魔方盲擰更加不可思議弄企。玩家對(duì)魔方進(jìn)行觀察之后超燃，蒙上眼睛擰轉(zhuǎn)魔方。2010 年的盲擰冠軍莊海燕包括觀察步驟的整個(gè)操作過(guò)程只用了 31 秒拘领。盲擰魔方數(shù)量的世界紀(jì)錄屬于印度尼西亞人穆哈默德·伊里勒·凱魯·阿納姆意乓。2010 年，他在觀察魔方后蒙上眼睛约素，于規(guī)定的一小時(shí)內(nèi)逐一還原了 16 個(gè)魔方届良。
最年輕的魔方玩家在成績(jī)被認(rèn)可時(shí)只有 4 歲本涕。年紀(jì)最大的玩家高齡 88 歲。魔方盲擰的難度更大伙窃，玩家年齡紀(jì)錄分別是 10 歲和 60 歲菩颖。
玩魔方的成就感在于把玩時(shí)體驗(yàn)到的樂(lè)趣。僅由磁鐵吸在一起的八方塊立方體益智游戲比魔方還早幾年誕生为障，它與魔方類似晦闰，卻更為簡(jiǎn)單。磁鐵吸附的方塊很容易被拆下鳍怨，而非只能轉(zhuǎn)動(dòng)變換位置呻右，因此，玩家可以投機(jī)取巧鞋喇，游戲也未能引起轟動(dòng)声滥。魔方的天才創(chuàng)意在于機(jī)械創(chuàng)新，而非數(shù)學(xué)創(chuàng)意侦香。
在魔方各類卓然出眾的變體中落塑，空心魔方堪稱奇跡」藓空心魔方的外觀和轉(zhuǎn)動(dòng)方式與魔方相同憾赁，只是魔方用于運(yùn)轉(zhuǎn)的所有構(gòu)件都消失了：立方體中心和每個(gè)面的中心都是空的，僅剩下 8 個(gè)角塊和 12 個(gè)棱塊散吵，就能完全像魔方那樣移動(dòng)（參見(jiàn)下圖）龙考。締造魔方神話的精巧機(jī)械結(jié)構(gòu)就這樣被超越了！如果你想嘗試研究魔方的各種變體矾睦，且不想一一購(gòu)買(mǎi)晦款，可以通過(guò)網(wǎng)上的免費(fèi)小程序就模擬操作（特別推薦：www.randelshofer.ch/rubik/index.html）。
數(shù)一數(shù)還原魔方的步驟
很容易看出枚冗，15 步不足以將任意形態(tài)的魔方恢復(fù)原狀缓溅。魔方的6個(gè)面都可以轉(zhuǎn)動(dòng) 90 度、180 度或 270 度官紫，因此肛宋，魔方每轉(zhuǎn)動(dòng)一次（一個(gè)面的旋轉(zhuǎn)）共有 18 種選擇。轉(zhuǎn)動(dòng)一次可以變出 18 個(gè)形態(tài)束世，轉(zhuǎn)動(dòng)兩次，最多可以變出 18×18 ＝ 182個(gè)不同的形態(tài)床玻，依次類推毁涉。如果最多轉(zhuǎn)動(dòng) 15 次，可變出的不同形態(tài)數(shù)目小于或等于：18+182+183+184+…+1815=7.1435×1018锈死。
不過(guò)贫堰，這一數(shù)字卻小于魔方可變出的形態(tài)總數(shù)穆壕，即 4.3×1019。所以其屏，如果最多只轉(zhuǎn)動(dòng) 15 次喇勋，我們無(wú)法變出所有可能形態(tài)。如果魔方處于一個(gè)無(wú)法只用 15 步擰成的形態(tài)偎行，恐怕需要至少轉(zhuǎn)動(dòng) 16 步才能還原川背。進(jìn)一步推理指出，某些形態(tài)需要至少 17 步還原蛤袒。
能將魔方還原已經(jīng)很不錯(cuò)熄云，如果能用最少的轉(zhuǎn)動(dòng)步數(shù)將魔方還原，就更好了……當(dāng)然妙真，難度也更大缴允。世界魔方協(xié)會(huì)設(shè)立了一個(gè)競(jìng)賽，衡量參賽者們節(jié)省轉(zhuǎn)動(dòng)步驟的能力珍德，規(guī)則如下：
(a) 參賽者有一小時(shí)時(shí)間觀察并仔細(xì)研究被打亂的魔方练般，必要時(shí)，可以借助鉛筆锈候、紙張踢俄、三個(gè)輔助魔方和有顏色的小膠條；
(b) 一小時(shí)后晴及，參賽者將自己找到的最優(yōu)轉(zhuǎn)動(dòng)步驟按標(biāo)準(zhǔn)記錄方法寫(xiě)下來(lái)都办。
解法的長(zhǎng)度即面的轉(zhuǎn)動(dòng)次數(shù)，一次轉(zhuǎn)動(dòng)也可以是四分之一圈或者半圈虑稼。2010 的冠軍是匈牙利人伊斯特萬(wàn)·柯察——看看琳钉！又是匈牙利人！他用 22 步轉(zhuǎn)動(dòng)還原了試題中打亂的魔方蛛倦。值得注意的是歌懒，這個(gè)數(shù)字確實(shí)已經(jīng)很小了。書(shū)籍或各種網(wǎng)頁(yè)里介紹的魔方還原方法大約需要 60 步溯壶，一些更難學(xué)的最佳方法也要 30 步及皂。柯察取得 22 步的優(yōu)異成績(jī)且改，并不是因?yàn)?2010 年的題目碰巧簡(jiǎn)單验烧。2009 年，該項(xiàng)競(jìng)賽的冠軍也用了 22 步又跛，2011 年的紀(jì)錄是 25 步碍拆，2012 年為 20 步，2013 年為 21 步。參賽者在不斷進(jìn)步感混，隨之也出現(xiàn)一個(gè)問(wèn)題：能否總用 22 步或者更少的步數(shù)還原魔方端幼？更確切地說(shuō)，頂級(jí)參賽者面對(duì)最壞情況時(shí)要轉(zhuǎn)動(dòng)多少步弧满？
當(dāng)純理論遇上實(shí)際困難
長(zhǎng)久以來(lái)婆跑，人們懷疑終極答案是 20 步。2010 年 7 月庭呜，該結(jié)論被證實(shí)確鑿滑进。魔方轉(zhuǎn)動(dòng)步數(shù)的研究可以歸結(jié)為某些數(shù)學(xué)群的研究，所以疟赊，我們?cè)J(rèn)為依靠不斷完善的數(shù)學(xué)知識(shí)能揭開(kāi)謎底郊供。我們所研究的魔方結(jié)構(gòu)不包含任何隨意性。這和國(guó)際象棋的例子恰恰相反近哟。國(guó)際象棋擁有復(fù)雜的規(guī)則驮审，可能出現(xiàn)的棋局圖像十分繁復(fù)難懂。在這里吉执，我們用圖來(lái)表示魔方問(wèn)題的結(jié)構(gòu)（參見(jiàn)“魔方的圖論”）疯淫，并用十分簡(jiǎn)單的幾何元素加以定義。對(duì)數(shù)學(xué)家來(lái)說(shuō)戳玫，這似乎是比較理想的狀態(tài)熙掺，他們可以盡情施展才華，依賴群咕宿、群的分類币绩、群的分解等數(shù)學(xué)知識(shí)得出答案。然而府阀，沒(méi)有得出任何結(jié)果缆镣，純理論方法最終被證明是不可行的！
4. 魔方的圖論
我們將魔方所有可能形態(tài)用圖示表達(dá)出來(lái)试浙。圖的節(jié)點(diǎn)是4.3×1019種可能的形態(tài)董瞻，若兩個(gè)形態(tài)可以通過(guò)魔方一個(gè)面的一次旋轉(zhuǎn)相互轉(zhuǎn)化，相應(yīng)兩個(gè)節(jié)點(diǎn)由一條弧連接田巴。
我們無(wú)法完整呈現(xiàn)這幅圖钠糊。魔方圖具有高度的對(duì)稱性，因?yàn)樗泄?jié)點(diǎn)都相互等價(jià)壹哺，與立方體頂點(diǎn)圖的情況相似抄伍。尋找還原魔方最優(yōu)轉(zhuǎn)動(dòng)步驟就轉(zhuǎn)化為如何在該圖中找到最短路徑。尋找還原最難形態(tài)所需的最多轉(zhuǎn)動(dòng)步數(shù)等價(jià)于尋找距初始形態(tài)最遠(yuǎn)的形態(tài)斗躏，基于本圖的對(duì)稱性逝慧，問(wèn)題又轉(zhuǎn)化為尋找圖的直徑昔脯，即圖中兩個(gè)節(jié)點(diǎn)之間的最大距離啄糙。
由于圖太大笛臣，在圖中無(wú)法直接應(yīng)用一般算法（計(jì)算最短路徑和直徑，等等）隧饼，即便使用強(qiáng)大的計(jì)算機(jī)網(wǎng)絡(luò)也是如此沈堡。通過(guò)改造算法并盡可能利用圖的特殊性質(zhì)，才能算出圖的直徑燕雁。
研究者們采用了如下想法：為了計(jì)算A和B兩個(gè)位置之間的一條短路徑诞丽，可以選取距A不太遠(yuǎn)的形態(tài)C，然后找出A和C之間的最短路徑以及B和C之間的最短路徑拐格。將這兩條最短路徑相連僧免，未必能得出A和B之間的最短路徑，但已能得出足夠好的結(jié)果捏浊。另外懂衩，通過(guò)變換C，能基本確定A和B之間的最短路徑金踪。
對(duì)魔方圖直徑問(wèn)題的研究已有三十年之久浊洞，卻進(jìn)展緩慢，直到2010年7月才證明直徑等于20胡岔。為了感受一下進(jìn)展速度法希，讓我們回顧一下關(guān)鍵日期、證明者姓名及其得出的直徑：1981年7月摩溫·希斯特斯維特得出52靶瘸，1993年4月漢斯·克魯斯特曼得出42苫亦，1992年5月邁克爾·瑞德得出39，1992年5月迪克·溫特得出37怨咪，1995年1月邁克爾·瑞德又得出小于29且大于20屋剑，1995年12月斯?fàn)柗颉だ鹊贸?8，2006年4月斯?fàn)柗颉だ扔值贸?7惊暴，2007年5月丹·康克勒得出26饼丘，2008年3月托馬斯·洛基奇又得出23，2008年8月進(jìn)一步得出22辽话，2010年7月托馬斯·洛基奇肄鸽、赫伯特·科辛巴、莫雷·戴維森和約翰·戴斯里奇最終證明直徑等于20油啤。
伴隨最后一個(gè)結(jié)果的誕生典徘，人們得出下面的列表，指出了與初始形態(tài)相距給定距離的節(jié)點(diǎn)數(shù)量益咬。列表中最后幾行是近似結(jié)果逮诲。
20 步，這個(gè)答案最終通過(guò)一系列算法的拓展研究才得以證實(shí)，前后歷時(shí)二十年梅鹦。人們必須借助強(qiáng)大的運(yùn)算能力才能修成正果裆甩，相當(dāng)于一臺(tái)臺(tái)式電腦不間斷工作 35 年。研究人員動(dòng)員業(yè)界巨頭谷歌公司出借一批計(jì)算機(jī)齐唆，花了幾周時(shí)間才完成運(yùn)算嗤栓。
打亂魔方可以得到的形態(tài)數(shù)量是 4300 億億。除了轉(zhuǎn)動(dòng)箍邮，如果將魔方拆卸再隨意重組茉帅，形態(tài)數(shù)量就會(huì)翻 12 倍，那么锭弊，僅有十二分之一的概率能將魔方還原堪澎。魔方的這一性質(zhì)和 Taquin 游戲類似：將 Taquin 拆卸并隨意拼回圖形，只有二分之一的概率能找回初始位置味滞。
我們可以逐一處理 4.3×1019個(gè)可能形態(tài)樱蛤，找到最佳轉(zhuǎn)動(dòng)步驟將魔方還原。赫伯特·科辛巴自 1992 年就開(kāi)始研究這個(gè)問(wèn)題桃犬，并找出了優(yōu)越的算法刹悴。多虧了他，找到給定魔方形態(tài)的最少還原步驟不再是夢(mèng)想攒暇。對(duì)于給定形態(tài)土匀，強(qiáng)大的機(jī)器通常也需要好幾秒鐘才能找到最優(yōu)轉(zhuǎn)動(dòng)步驟。采用每秒處理一個(gè)形態(tài)的算法形用，計(jì)算每一個(gè)形態(tài)的最優(yōu)轉(zhuǎn)動(dòng)步驟就轧，最終找出魔方最復(fù)雜的形態(tài)，這需要調(diào)動(dòng)現(xiàn)今地球上存在的全部十億臺(tái)計(jì)算機(jī)一起工作 1300 多年田度。強(qiáng)使蠻力也無(wú)法給出答案妒御。
另一個(gè)辦法主張逐步處理，記住所得結(jié)果镇饺，并將其重復(fù)利用乎莉。觀察一步轉(zhuǎn)動(dòng)能夠得出的所有形態(tài)（一共 18 個(gè)），將一步轉(zhuǎn)動(dòng)所得形態(tài)的相關(guān)信息列出奸笤。從這些形態(tài)出發(fā)惋啃，進(jìn)行下一步所有可能的轉(zhuǎn)動(dòng)，此后监右，再將兩步得到全新形態(tài)的相關(guān)信息記錄下來(lái)边灭。
以相同方式繼續(xù)，我們漸漸記錄下達(dá)到所有可能形態(tài)的最短路徑信息（因?yàn)榻『校?dāng)我們第一次生成一個(gè)形態(tài)時(shí)绒瘦，不可能有更短的轉(zhuǎn)動(dòng)步驟來(lái)得到它）称簿。當(dāng)最新一步計(jì)算無(wú)法再產(chǎn)生新形態(tài)時(shí)，終止算法惰帽。我們確信憨降，能夠得到所有最短路徑的長(zhǎng)度，同時(shí)善茎，找到所需還原步驟最多的魔方形態(tài)券册。
理論上频轿，這個(gè)方法更好地利用了已逐步保存的計(jì)算結(jié)果垂涯，比上一個(gè)方法速度更快。然而航邢，由于信息存儲(chǔ)量過(guò)大耕赘，此法依然不可行。想要完成剛剛描述的算法膳殷，逐步計(jì)算所有最短路徑操骡，所需存儲(chǔ)量是地球上所有計(jì)算機(jī)硬盤(pán)的存儲(chǔ)量總和，數(shù)量級(jí)為 1021字節(jié)赚窃！
算法的功勞
在過(guò)多運(yùn)算和過(guò)大存儲(chǔ)之間册招，必須找一個(gè)折中的辦法。托馬斯·洛基奇勒极、科辛巴是掰、莫雷·戴維森和約翰·戴斯里奇找到一個(gè)辦法，證明了 20 步就是將魔方從最復(fù)雜形態(tài)還原所需的轉(zhuǎn)動(dòng)步數(shù)辱匿。他們通過(guò)長(zhǎng)期研究和一系列改進(jìn)措施键痛，希望限制問(wèn)題的復(fù)雜性，同時(shí)匾七，利用一臺(tái)現(xiàn)代化計(jì)算機(jī)的存儲(chǔ)和計(jì)算能力絮短，確保絕不超出當(dāng)今技術(shù)的極限。
3魔方最經(jīng)典的變體是 2×2×2 魔方昨忆、4×4×4 魔方的復(fù)仇丁频、5×5×5 教授魔方。這些都是世界魔方協(xié)會(huì)的競(jìng)賽項(xiàng)目邑贴。2008 年上市的 6×6×6 魔方和 7×7×7 魔方體積最大席里。2×2×2 魔方的形態(tài)總數(shù)是 3 674 160 種，3×3×3 是 4.3×1019種痢缎，4×4×4 是 7.4×1045種胁勺，5×5×5 是 2.8×1074種，6×6×6 是 1.57×10116種独旷，7×7×7 是 1.95×10160種署穗。這已經(jīng)超過(guò)了可見(jiàn)宇宙中信息量的比特?cái)?shù)寥裂！魔方的數(shù)十種變體風(fēng)靡全球，包括給視障人群的盲文版魔方案疲。
利用問(wèn)題的對(duì)稱性可以略微減小運(yùn)算規(guī)模封恰。此外，將問(wèn)題分解成數(shù)量眾多的子問(wèn)題褐啡，憑借類似上述漸進(jìn)法的辦法诺舔，一臺(tái)計(jì)算機(jī)的存儲(chǔ)能力就足以完成整體處理。于是备畦，問(wèn)題就被分解成 2 217 093 120 個(gè)子集低飒，各自包含 19 508 428 800 種形態(tài)。再次利用對(duì)稱性懂盐，所要處理的子集數(shù)量還可減少到 55 882 296 個(gè)褥赊。
最復(fù)雜情況至少需要 20 步完成，科辛巴算法的一個(gè)變體正是利用了這個(gè)信息莉恼。從 1995 年起拌喉，人們便知道少于 20 步無(wú)法還原某些形態(tài)。因此俐银，對(duì)于給定形態(tài)尿背，只要找到一個(gè)小于 20 步的解法娜扇，即便不是最優(yōu)方法钧排，我們就不再費(fèi)力尋找更簡(jiǎn)短的路徑了。
為了證明“20 步足以還原最復(fù)雜形態(tài)”骑歹，冗長(zhǎng)的運(yùn)算還得出了另外一些有趣的信息售躁。比如坞淮，所需步數(shù)的平均值為 17.7 步。需要 20 步才能還原的復(fù)雜形態(tài)比較少見(jiàn)陪捷，大約有 3 億種回窘。這意味著，如果隨機(jī)抽取市袖，出現(xiàn)這種復(fù)雜形態(tài)的概率少于一千億分之一啡直。這些信息讓我們認(rèn)識(shí)到，能夠用 22 步還原魔方的魔方達(dá)人已經(jīng)十分接近完美境地苍碟，著實(shí)值得稱贊酒觅。然而，盡管他們做出了巨大努力微峰，經(jīng)歷了艱苦訓(xùn)練舷丹，卻仍然無(wú)法發(fā)現(xiàn)最優(yōu)的轉(zhuǎn)動(dòng)步驟。
曾幾何時(shí)蜓肆，這個(gè)有著三十余年歷史的游戲向全體計(jì)算機(jī)科學(xué)家們宣戰(zhàn)颜凯，研究者們費(fèi)盡心思才解決了最復(fù)雜形態(tài)的問(wèn)題谋币。魔方也要挑戰(zhàn)數(shù)學(xué)家。目前症概，面對(duì)這個(gè)簡(jiǎn)單的純代數(shù)抽象問(wèn)題蕾额，數(shù)學(xué)家們只能聽(tīng)任機(jī)器擺布，勉強(qiáng)接受一個(gè)任何數(shù)學(xué)理論家都無(wú)法質(zhì)疑彼城、卻也無(wú)法手工驗(yàn)證的結(jié)論诅蝶。
【相關(guān)圖書(shū)】
作者：讓-保羅·德拉耶
譯者：路遙
本書(shū)揭開(kāi)趣味游戲、藝術(shù)設(shè)計(jì)和日常生活中的數(shù)學(xué)密碼募壕，通過(guò)新穎話題和精美圖示展現(xiàn)算術(shù)與幾何中隱藏的妙趣调炬，從最簡(jiǎn)單的數(shù)學(xué)原理走入算法的精彩世界，展現(xiàn)算法破解數(shù)學(xué)謎題的無(wú)窮威力司抱。本書(shū)適合所有數(shù)學(xué)愛(ài)好者閱讀筐眷。
【作者簡(jiǎn)介】
讓-保羅·德拉耶 | Jean-Paul Delahaye
法國(guó)數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家，數(shù)學(xué)科普作家习柠，現(xiàn)任法國(guó)里爾科技大學(xué)計(jì)算機(jī)技術(shù)教授，法國(guó)國(guó)家科學(xué)研究院（CNR）計(jì)算機(jī)基礎(chǔ)科學(xué)實(shí)驗(yàn)室研究員照棋，主要研究邏輯編程资溃、偶然性和游戲的算法原理。
