已打亂的三階魔方的最簡復原步驟？

01-15

已經打亂了的三階魔方肯定有非常多方法和步驟來還原，但最簡單要幾步呢，由此引申出，對於打亂最複雜的魔方（所需步驟最多）的，需要多少步呢？是不是計算機可以編程來計算這個問題呢

懶得打字了，我直接轉載我好久之前寫的一些文字吧，希望對題主有幫助。

數學家破解"上帝之數"還原任意魔方僅需要20步

儘管擁有43,252,003,274,489,856,000種不同的可能組合狀態，但魔方都可以在20步內還原。

北京時間2010年8月13日消息，據國外媒體報道，相信許多人都玩過魔方，但是此前沒有人知道任意組合的魔方的最小還原步數究竟是多少。這一問題困擾了數學家長達三十多年，這個最小還原步數也被稱為「上帝之數」。美國加利福尼亞州科學家近日利用計算機破解了這一謎團，研究人員證明任意組合的魔方均可以在20步之內還原，「上帝之數」正式定為20。

這支研究團隊位於美國加利福尼亞州帕洛阿爾托市。科學家們通過計算機計算和證明，任意組合的魔方都可以在20步內還原。這一結果表明，大約有10萬多種的起始狀態恰好可以在20步內還原。

利用谷歌公司計算機強大的計算能力，研究人員檢驗了魔方任何可能的混亂狀態(確切數字為43,252,003,274,489,856,000)。美國俄亥俄州肯特州立大學數學家莫雷-戴維德森教授也是研究人員之一，他表示，「我們現在可以肯定，這個『上帝之數』就是20。對於我來說，我也回到了原地。魔方伴隨著我成長，這也是我為什麼深入研究這個數學問題的原因。這個謎團引起了人們的廣泛關注，它也許是人類歷史上最受歡迎的謎語了。」科學家們的初步研究成果發表於在線網站上，但戴維德森表示，他們準備將研究成果提交給雜誌正式發表。

程序員托馬斯-羅基花了15年的時間，致力於尋找這個謎團的答案。據羅基介紹，研究團隊所採用的演算法可以在1秒鐘內嘗試10億種可能，此前的計算機演算法1秒鐘內只能處理4000種可能。

為了讓問題簡單化，研究團隊採用了一種所謂「群論」的數學技術。他們首先將魔方所有可能的起始狀態集分成22億個集合，每個集合包含了195億個可能的狀態。集合的分配原則是這些可能的狀態是如何應對一組10個可能的還原步驟。再通過魔方不同的對稱性，這種分組技術使得研究團隊將集合數減少到5600萬個。

研究人員所採用的演算法可以快速將這些還原步驟與恰當的起始點匹配起來，從而實現在20秒內處理一個集合中的195億種可能。對於普通的家用電腦來說，以這樣的速度完成整個處理任務需要大約35年時間。

注1：上文中魔方特指不帶圖案的3x3x3魔方，其中1步指轉動某個面一下（90度，180度，270度都算1步），如果以90度轉動記為1步，180度轉動記為2步，則結果為26步，請參考：God"s Number is 20

注2：以上轉自網路，以下原創，轉載請註明出處。

====================答疑部分====================

1. 什麼是上帝之數？

說到上帝之數，得從最少步還原說起。對於一個打亂的魔方，有人可能需要100步才能將它還原，有人可能需要60步，這取決於還原的步驟或演算法。我們假設上帝還原魔方的時候總是用最少的步驟還原，那這時候我們就想到一個問題，上帝演算法在最壞情況下需要幾步才能將魔方還原（要知道魔方狀態好多好多，打得不夠亂的可能上帝只需要5步就還原了，那打得稍微亂一些的，噁心一些的呢）？那麼這個數字就被叫做上帝之數。

2. 既然所有魔方都可以在20步內還原，為什麼上帝之數不可能是19或者更少呢？

其實很簡單，因為1995年的時候某大神就找到了一個坑爹狀態（就和那堆精心構造的反例似的），通過計算機暴力搜索的辦法發現，無論如何也不可能在19步內把它還原，或者說上帝還原這個坑爹狀態也得20步，所以很顯然上帝之數沒法小於20了。

3. 那個什麼谷歌計算機到底算了多少個狀態？

其實精確值是55,882,296*19,508,428,800個狀態，大約佔三階總狀態數的1/40，所以其實演算法上和暴力破解差得不太多，只不過，按照35CPU年算來，差不多每秒十億個狀態確實很高端霸氣上檔次（膜拜）。剩下39/40的狀態果斷用數學方法證明掉了，思路差不多是說，如果解決A類狀態的步驟簡單變形就能解決B類狀態，那A和B類只要暴力求一個。

4. 每秒十億個狀態，平均求解一個狀態只要1納秒，如何做到的？

那主要是因為現在只關心上帝之數是否是20的問題，而不關心具體某個狀態的最少步數是多少。一個不是很恰當的比喻是說，比如我找到個狀態，它的最少步數是17步，那麼很顯然這個狀態邊上3步以內的狀態就可以直接pass掉了，反正這些個狀態撐死也能在20步內搞定的，至於它們是不是能夠在19步內搞定我們根本就不關心，反正它們就算能在18步內搞定，上帝之數也不會小於20（前面說過了），我就不用費那心思去算他們了。

上帝之數是上限。

尋求最小步數可能比較難以用計算機實現（因為狀態太多步數挺長），但有一門比賽叫「最小步」，題主可以了解一下人類是怎樣完成這個任務的。

用一個手機應用：極限魔方，裡面有最小步數法，可以最簡答最快的還原。

極限魔方 - 教你輕鬆玩魔方：在 App Store 上的內容itunes.apple.com