2008/08/13

魔術方塊 Rubik’s Cube

本文來自這兒,看了之後才知道魔術方塊的英文叫 Rubik’s Cube。我現在二層完全沒問題,第三層老是記不住,也試過要去手能生腳,哦是「熟能生巧」,可是玩了很久還是一樣,可憐的記性。怕文章不見了,轉貼一下。

--------------------------------------------------------
寓數學於魔術方塊
‧科學人 2008/08/13
玩魔術方塊的樂趣不只轉一轉而已,其中的數學也大有學問,各式各樣的方塊更要你大開眼界!
【文╱郭君逸】

(照片提供/科學人)
魔術方塊, 廣東話稱做「扭力骰」,英文為「Rubik’s Cube」,它是在1974年由匈牙利的建築系教授魯比克(ErnRubik)所發明,一開始他只是突發奇想地問學生,如何設計一個3×3×3的方塊,讓人可以轉動,又不會散開來?結果真的有學生做出來了,它的中心結構如右頁下方插圖,並且一直沿用至今。最初這個方塊是用木頭做的,經過上色之後,才發現要還原它是一件非常困難的事,因此有人提議將上色的方塊做成益智玩具出售。

魯比克也在1975年為他的魔術方塊申請了專利,1979年風行於歐洲,當時風靡的程度,幾乎是人手一顆。電影「當幸福來敲門」(Pursuit of Happyness)就是改編於這個時期發生的一個真實故事,威爾史密斯飾演的主角賈納是一個窮途潦的低收入戶,為了應徵某證券公司的實習職缺,投了上百封的履歷都石沉大海;是在某次下班時,假藉順路之由厚著臉皮跟公司經理上了計程車,一路上賈納口沫橫飛地為自己爭取工作機會,經理卻一個字也沒聽進去,因為他正專心轉著手上的魔術方塊;後來賈納幫經理完成了手上的方塊,也因此贏得了到公司實習的機會。電影中的計程車司機邊開車,手上也邊拿著一個魔術方塊在轉,可見當時魔術方塊流行的程度。

台灣的魔術方塊從1990年代開始流行,從一顆要價數百元,逐漸普及到只要幾十塊就可以在夜市或路邊攤買到。筆者所認識的兩位對台灣魔術方塊界貢獻良多的愛好者,一位是1990年左右台大魔術社第二屆社長趙承宗,他後來「退隱江湖」了;另一位是2004年左右成立交大魔術社的鄭維駿,現在正在美國康乃爾大學讀電子工程研究所。看起來,似乎喜歡玩魔術的人,都會喜歡玩魔術方塊。

背公式解魔方

魔術方塊發展了近30年了,最短破解時間的世界紀錄每年都在翻新,除了玩家不斷的練習、心得交流之外,靠的就是公式的不斷改進。事實上,坊間流傳的解法很多,不過最常見的就是依一層一層的順序來完成。第一層相信讀者只要把玩個幾十分鐘應該就會了;第二層大概就需要有人指導,才能夠了解其中的邏輯;第三層則很少有人能夠獨立想出解法,原因是要把第三層轉好,又要維持前兩層不被打亂,非常困難,這也是魔術方塊的精神所在。所幸前人已經整理出不少第三層的公式,只要能夠看得懂公式的運作,照著公式就能轉好。

公式可以分成兩種類型,一種適合初學者,另一種適合追求極速的玩家(speedcuber)。適用於初學者的公式,講求的就是盡量好記,能夠花最少的時間學會如何完成魔術方塊,避免因為背得頭昏腦脹而半途而廢。坊間有人宣稱只要四個公式即能完成魔術方塊,或是只要三個、兩個,甚至不用公式。少一、兩個公式的原因,只是把公式的記憶轉嫁到公式的判斷上,必須花更多的時間去記「發生什麼情況時,要做什麼事情」,反而記憶的東西更多。因此如何設計一個容易記憶、讓空間概念不好的人也能學會轉魔術方塊、隔幾個月沒玩還是能夠記得、真正適合初學者的公式,其實也是值得探討的課題。至於要能夠在半分鐘、甚至10秒內就完成方塊的公式,所講求的目標完全不同。追求極速的玩家,會發自內心有一股熱忱,為了多快一、兩秒,再多公式也背得起來。此類公式的訴求就是省時間,不管是「判斷時間」或是「轉的時間」都要盡量的減少,這種我們稱做「速解魔方」(speedcubing)。速解魔方公式的始祖是美國賓漢頓大學教授弗雷德里奇(JessicaFridrich),她設計了70幾個公式,宣稱17秒能完成方塊,現今速解魔方玩家的公式大多改編自她的公式。

很多人都難以置信,為什麼有人可以不到10秒就轉好一個方塊?其實,除了背多一點公式外,就只有「練習再練習」。這就好比學倉頡或無蝦米這種字根式的輸入法,一開始要慢慢背各種字根,然後學習看到一個中文字,就知道怎麼拆碼,最後就是一天打上個一、兩個小時,練到後來,看到字,都是非常直覺地打出來,完全不經思考。魔術方塊要轉得快,一開始也是慢慢背針對各種情況的公式,然後每天練個一、兩個小時,練到能以直覺反應來轉的程度,眼睛一瞥,手就自動迅速地轉了起來;所以常常看到有人可以轉非常快,但請他慢慢轉,他反而轉不出來。

上帝的數字

其實魔術方塊不只好玩,它在數學上用到了極多代數中的李群、群論,還有一些離散數學及機率。其實有機會上這些課的時候,都可以想想它在魔術方塊上的應用,純理論的課會因此變得生動些。

魔術方塊發展至今已有不少研究了,其中最大的課題就是「任意的三階魔術方塊,可以保證最少幾步完成?」1982年佛雷(Alexander H. Frey, Jr.)與辛馬斯特(David Singmaster)合著的《魔術方塊手冊》(Handbook of Cubik)裡,稱這個答案為「上帝的數字」(God's number),並證明這個數字介於17~52之間;也就是說,任意亂的情況,都可以在52步內完成,而且有一些情況保證至少要17步才能完成,書中並猜測上帝的數字為20。

這裡就要談到怎麼樣才算「一步」,常見的有兩種算法:一種是只要把一個面轉90度就算一步,稱做「quarter turnme t r ic」(QTM);另一種是轉動一個面算一步,不管轉幾度,稱做「fa c e t u r nmet r ic」(FTM)。QTM中若把一個面轉180度,就算兩步,而在FTM中只算了一步,因此FTM的數字會比QTM的少,而一般沒特別指明的話,都是用 FTM來計數。

1995年,美國玩家瑞德(M i c h a e lRaid)證明了某些情況至少需要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年,美國史丹佛大學的羅區奇(To m a sR o k i c ki)繼證明25步即可完成後,5月又在「魔方領域」(Domain of the CubeForum)論壇中更進一步證明了23步即可完成,震驚了整個魔方界,不過這些結果到目前還沒有正式的論文出來。

【完整內容,請參閱科學人2008年第78期8月號】

沒有留言: