魔術方塊介紹3

上帝的數字
其實魔術方塊不只好玩，它在數學上用到了極多代數中的李群(Lie Algebra)、群論(Group Theory)，還有一些離散數學(Discrete Mathematics)及機率(Probability)。其實有機會上這些課的時候，都可以想想它在魔術方塊上的應用，純理論的課程，會因此變得生動些。
魔術方塊發展至今已有不少研究了，其中最大的課題就是「任意的三階魔術方塊，可以保證最少幾步完成？」1982年佛雷(Alexander H. Frey, Jr.)與辛馬斯特(David Singmaster)合著的《魔術方塊手冊》(Handbook of Cubik)裡，稱這個答案為「上帝的數字」(God's number)，並證明這個數字介於17~52之間；也就是說，任意亂的情況，都可以在52步內完成，而且有一些情況保證至少要17步才能完成，書中並猜測上帝的數字為20。
這裡就要談到怎麼樣才算「一步」，常見的有兩種算法：一種是只要把一個面轉90度就算一步，稱做「quarter-turn metric」(QTM)；另一種是轉動一個面算一步，不管轉幾度，稱做「face-turn metric」(FTM)。QTM中若把一個面轉180度，就算兩步，而在FTM中只算了一步，因此FTM的數字會比QTM的少，而一般沒特別指明的話，都是用FTM來計數。
1995年，美國玩家瑞德(Michael Raid)證明了某種情況至少需要20步才能完成，他將這些情況稱做「Superflip」，同時，他也證明了可以在29步內完成所有的方塊(QTM為42步)，一口氣把上帝的數字範圍縮小到20~29之間。2006年，雷杜(Silviu Radu)用群論證明了上界可以再縮小到27步(QTM為34步)，他將所有的情況分成幾類，並借助離散代數系統(GAP)證明出在27步內都能完成。1990年，美國東北大學的電腦科學家古柏曼(Gene Cooperman)等人，在一個談代數編碼的研討會上，發表了「2×2×2的方塊皆可在11步內(QTM為14步)完成」；2007年，古柏曼與他的學生庫柯爾(Daniel Kunkle)將這個方法推廣到3×3×3的方塊上，設計了一個平行演算法，用20台超級電腦，總共花了8000個小時，證明出26步內可以完成。2008年3月，美國史丹佛大學的羅區奇(Tomas Rokicki)繼證明25步即可完成後，8月又在「魔方領域」(Domain of the Cube Forum)論壇中宣稱可以證明出22步即可完成，震驚了整個魔方界。

Superflip

另一方面，德國數學家柯西姆巴(Herbert Kociemba)設計了一個叫做 Cube Explorer的程式，可以幫你「盡量」找出最佳解，有時只比真的最佳解多一、兩步而已，他也用亂數產生了約1012種之多的情況，用Cube Explorer解開之後做了粗略的統計，約28%可以在17步內完成、69%可以18步完成、3%可以19步完成，並沒有跑出20步的情況，可見瑞德的Superflip情況其實很少見。
直到2010年7月，羅區奇與一位數學家與兩位電腦工程師，一起用證明了上帝的數字的確是20，解除了這30年一直存在數學家心中的疑惑，詳細情形請見「God's Number is 20」。除了羅區奇他們偉大的貢獻外，讓人驚嘆的是，在30年前，沒有電腦的時代，佛雷他們竟然可以精準的猜測出上帝的數字，真的非常的不可思議。

資料來源：http://www.davidguo.idv.tw/cube/