復原魔方的最小步數？

02-14

對於最亂的魔方，要復原它的最少步數是多少？

三階魔方有43,252,003,274,489,856,000（約合4.3×10的19次方）種不同的可能組合狀態，但它都能在20步之內還原。這個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步）注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（前面說過了），我就不用費那心思去算他們了。

答疑部分待續。。。

====================乾貨部分====================

1. 首先將魔方狀態群根據H(&)子群分解成 2,217,093,120 個右陪集，其中每個陪集中的元素個數為 19,508,428,800。

2. 利用魔方的對稱性（即對於狀態A及整體轉動S，S^-1 A S和A同解）將陪集的個數降為 55,882,296 ，即約為總量的1/40。 3. 暴力求解每個陪集。

其中第三條的演算法用到一些trick：

對於給定陪集 R = H * r，使用IDA*演算法搜索 R 到 H 的解，則對於每個解 m 有： r * m = h （其中 h 屬於 H）於是有：

(h * r) * m = 1 （其中h = h^-1）

注意到 h 屬於 H 子群，所以h也屬於H，於是 h * r 屬於 H * r = R 因此，映射 H -&> H * r : f(h) = h * r 是雙射

即選取R中的任何一個狀態t，如果t可以在N步內訪問H中的所有狀態，則說明R中的所有狀態可以在N步內還原。

實際暴力求解每個陪集的演算法為

a) 首先取N=15及R中的某一個元素進行進行IDA*，即標記出可以在15步內訪問到的H中的所有狀態（結果保存為bitvector的形式，以節省內存）。

b) 直接對這些狀態在&下轉動1步（使得轉動後的狀態依然屬於H），將新訪問到的狀態與15步狀態合併，記為16步內可以訪問到的狀態（事實上16步內可以訪問的狀態會比標記出來的多，但IDA*的性能遠低於直接轉動特定狀態的性能，為了證明上帝之數為20步不需要那麼做）。

c) 重複上述步驟(b)四次，即得到20步內可以訪問到的H中的狀態的一部分（受限於IDA*，但也足夠了）。

d) 此時H基本已經遍歷完畢，平均還會剩下幾百個狀態沒有遍歷到，將這些狀態所對應的R中的狀態用二階段演算法搞定之。即證明了整個陪集中的那麼多狀態都可以在20步內完成。

對於大部分陪集，上述演算法性能很高，但對於某些噁心的陪集，很有可能c完成後留下了海量沒有遍歷到的狀態，這時候需要改進上述演算法，即增加一部分16步的IDA*過程。

計算時間上，計算完a平均需要3.1秒，計算完c平均需要17.4秒，計算完d平均20秒不到，即20秒搞定一個陪集。總共55,882,296個陪集共需要35CPU年。注意到各陪集之間相互獨立，上述過程可對不同陪集進行分散式並行計算，最後匯總結果。

據說利用魔方對稱性將2,217,093,120個陪集降到55,882,296個並不那麼容易，因為H群只是D4h對稱群，直接可利用的對稱性只有16種，所以採用了一種set cover的技巧。即在H群里找個對稱性更強的子群，即Q（&，Oh的對稱性），然後將Q*r的個數利用對稱性降為原來的1/48左右，最後從H*r中精心尋找一些陪集，完全覆蓋所有的Q*r。這麼一來，只要搞定所有這些能夠覆蓋Q們的H，就能證明所有的Q都能在20步內搞定，即證明了所有的狀態。

但是由於H比Q大太多，這個覆蓋問題計算上搞不定，所以還得引入K和T群，其中K是在H基礎上無視角塊方向，T是在Q基礎上無視角塊，然後將K對T進行一個覆蓋，並求解每個K所對應的好多個H，最終產生了55,882,296個不同的H（其中K覆蓋T的演算法還是貪心演算法，所以總計算量只是原來的1/40，而不是1/48）。

（來自互聯網，並非原創）

現定上帝之數為20 也就是說20步以內可以還原任意打亂後的標準三階魔方。

截至2017年8月，在世界魔方協會認證的比賽中單次最少步紀錄為19步平均為22.33步（具體可以去粗餅網或WCA官網自行查找比賽記錄）

三階魔方有43,252,003,274,489,856,000（約合4.3×10的19次方）種不同的可能組合狀態

center pieces固定，corner pieces有8個位置，每個位置有3個狀態，edge pieces有12個，每個位置有2個狀態。(8! * 3^8) * (12! * 2^12) = 519,024,039,293,878,272,000，比上面的結果多很多，因為很多狀態不能還原？

上帝之數的20是在20步以內可以還原任意打亂後的標準三階魔方；

魔方最小步世界紀錄是針對給定一個打亂狀態在1小時的嘗試時間給出最少步數和解法；

兩者不是一個概念，別混為一談！

上帝之數是20，世界紀錄是19

現在的世界紀錄是19步，太強了