[新聞] 三階魔術方塊 20步數內解決 - 魔術方塊

※ [本文轉錄自 Gossiping 看板 #1CO_jtU0 ]

作者: str8g () 看板: Gossiping
標題: [新聞] 三階魔術方塊 20步數內解決
時間: Thu Aug 12 21:47:31 2010

http://udn.com/NEWS/WORLD/BREAKINGNEWS5/5782416.shtml

三階魔術方塊 20步數內解決

【中央社╱台北12日電】
2010.08.12 06:07 pm

花了15年才達到這一步，但最新研究證明，三階魔術方塊的任何組合，都能夠在20個步數
之內破解，而且不是靠撕掉小方塊的顏色貼紙再重新貼上。

「新科學家雜誌」（New Scientist）電子版報導，一名谷歌（Google）工程師和數名數
學家攜手，破解了魔術方塊的43,252,003,274,489,856,000種組合，每種排列組合都能夠
在20步裡還原。

來自加州巴羅艾托（Palo Alto）羅區奇（TomasRokicki）花了15年尋找破解魔術方塊的
最少步驟。他說：「基本的突破，就是找出一個方法破解所有組合，不僅要一次解決，而
且還要快。」

這個步數被稱為「上帝的數字」（God's number），意味著連上帝都不能在更少步數裡破
解。「新科學家雜誌」曾在2008年報導羅區奇將「上帝的數字」減少到22，但顯然要將數
字再度縮小，需要一些聰明捷徑。

為了簡化問題，羅區奇和他的團隊利用從「群論」（group theory）延伸出來的技巧。

首先將所有可能的排列組合歸納成22億組，每組底下有195億種組合。

他們在網站上寫道：「我們把問題分成2,217,093,120個小問題，每個問題底下有
19,508,428,800種不同組合，因此每個小問題能夠用現代電腦運算。我們把它們分解，因
此能夠快速運算。」

你可以把他的演算法想像成這樣：想像你要去一個不熟悉的城市拜訪朋友。他們給你畫了
地圖，告訴你右轉左轉，但是忘了告訴你起點。如果你隨機找個點開始走，幾乎不可能到
達目的地，但若對照上起點，你就絕對能走到。

因此，這個團隊的快速演算法能夠在20秒內解決195億種組合。

但是即使按照這個速度，要完成任務，一般電腦仍舊需要花上35年，因此需要另一個捷徑
：谷歌工程師達斯瑞吉（John Dethridge）。利用他的電腦王國去計算，所有演算得以在
數星期內解決。

--