數學家破解"上帝之數" 還原任意魔方僅需要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(<U, R2, F2, D, L2, B2>)子群分解成 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) 直接對這些狀態在<U, R2, F2, D, L2, B2>下轉動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（<U2, R2, F2, D2, L2, B2>，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）