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

〔中央社〕花了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）。利用他的電腦王國去計算，所有演算得以在數星期內解決。（譯者：中央社戴雅真）

http://iservice.libertytimes.com.tw/liveNews/news.php?no=397607&type=%E7%94%9F%E6%B4%BB

God's Number Revealed: 20 Moves Proven Enough to Solve Any Rubik's Cube Position

The world has waited with bated breath for three decades, and now finally a group of academics, engineers, and math geeks has discovered the number that explains life, the universe, and everything. That number is 20, and it's the maximum number of moves it takes to solve a Rubik's Cube.

Known as God's Number, the magic number required about 35 CPU-years and a good deal of man-hours to solve. Why? Because there's 43,252,003,274,489,856,000 possible positions of the cube, and the computer algorithm that finally cracked God's Algorithm had to solve them all. (The terms "God's Number/Algorithm are derived from the fact that if God was solving a Cube, he/she/it would do it in the most efficient way possible. The Creator did not endorse this study, and could not be reached for comment.)

A full breakdown of the history of God's Number as well as a full breakdown of the math is available here, but summarily the team broke the possible positions down into sets, then drastically cut the number of possible positions they had to solve for through symmetry (if you scramble a Cube randomly and then turn it upside down, you haven't changed the solution).

They then borrowed some computing time from Google (one of the principals is an engineer there) and burned about 35 core-years to solve all the possible positions. The number 20 has been the lower limit for God's Number for more than a decade, but the team was finally able to whittle away at the upper limit (which was trimmed back to 22 in 2008).

So far the algorithm has identified some 12 million distance-20 positions, though there are definitely many more than that. Click through the source link below if you want to see what some of the hardest positions are, and how God would sort 'em out.

http://www.popsci.com/science/article/2010-08/gods-number-revealed-20-moves-will-solve-any-rubiks-cube-position