【知識】什麼是上帝之數？
鳥傑WARNING：本文所指的魔方，如無特殊強調，即指三階魔方。
相信大家在學習魔方的過程中或多或少會對「上帝之數」四個字有所耳聞。
即便你沒有耳聞，你也一定曾經疑惑過，究竟需要至少多少步才能還原一個魔方。
究竟什麼是上帝之數？
它又是如何被證明的？除了三階魔方，別的魔方有沒有上帝之數呢？
今天我們介紹的就是關於上帝之數的那些事。
自1974年，厄爾諾·魯比克教授發明魔方以來，有一個問題就始終困擾著魔友和數學家：
我們究竟需要多少步，才能還原一個被打亂的魔方？
要回答這樣一個問題，首先我們要澄清三個概念：
- 我們今天討論的是三階魔方的上帝之數（Gods Number）。
- 上帝之數指的是還原三階魔方最複雜的狀態（Hardest Position）所需要的最少步數。
- 我們採用的記步方法（Turn Metric）是HTM（Half Turn Metric）。
第一條沒什麼問題。第二條如何理解？試想如果我打亂一步魔方，它是不是也只需要一步就能還原，我們要討論最複雜的狀態的最少步數才有意義。第三條，我們要強調的是不同的記步體系會對於同一種操作可能會有不同的計算標準。在此不詳細論述。
首先我們計算一下，三階魔方總共有幾種狀態：
關於這個公式所代表的含義，我簡單說一下：
8!表示8個角塊的排列方式，3^8表示8個角塊的3個方向。12!表示12個棱塊的排列方式，2^12表示12個棱塊的2個方向，最後要去掉11/12不可能復原的情況。最後得到總數約為4.3千兆種。按人類的手速，需要1000多億年才能遍歷所有情況。
如何用排列組合求解魔方的狀態總數？
更多關於狀態的知識，上面那個回答都已經囊括了。
那究竟最少需要多少步，才能復原任意一個三階呢？
其實啊，早在1995年，數學家就發現了上帝之數中最著名的一個情況——Superflip。
Superfilp是一個角塊全復原，棱塊都要翻轉的，極其規律的情況，且它不存在20步以內的解法。
這個情況的發現使得我們確定了一件事：上帝之數是不可能小於20的。
那麼Superflip的發現是不是意味著所有情況都能在20步以內復原呢？如何證明這件事情？
數學家想了一個很偷懶很暴力的辦法：
人是算不過來，這不是有電腦么，我就把這4.3千兆種情況丟給計算機，死算不就完了。
這裡的35年指的是35 CPU years，一個CPU year指的是1GFLOP的機器算一年（8760小時）的計算量，詳情見 GFlops, G-hours, and CPU hours
算出來如果所有情況都可以在20步之內復原，那就證明啦！
當然這個4.3千兆種情況對於計算機還是有那麼點多，於是研究人員做了這麼幾件事情：
- 分組：總共分成了22,1709,3120組，每組195,0842,8800種情況；
- 降組：通過一些操作（比如對稱性），使得只要算5588,2296組就可以得到結果；
- 不算最優解：所以只需要算出所有的狀態不會超過20步即可，沒必要強求最優解；
- 編程：平均算一個魔方20秒；
- 暴力計算：算35個CPU year就好了（實際計算時間是a few weeks）。
算完之後發現，確實沒有超過20步的最少步解法，於是就證明啦~
而且這個20步的情況也不多，也就將近5個億，我是說和別的比……
讓我們來看看網友們對此事的評價……
With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube?, and shown that no position requires more than 20 moves. ? r/programming
一位叫做yiyus的網友說：暴力證明的典範！我以為它會被好好證明，誰知道就這麼簡單粗暴，我喜歡！
一位叫做Chaos3ory的網友說：暴力永遠管用！除非不夠暴力！
最終，於2010年7月，研究人員證明三階魔方的上帝之數是20HTM。
2014年，魔方發明40周年之際，研究證實了三階魔方上帝之數為26QTM。
此外，二階魔方、斜轉魔方、金字塔魔方的上帝之數都是11步。
四階魔方及以上階數的魔方的上帝之數均未被證實到某一確定數字。
人類對於上帝之數的追尋，還將繼續。
此外，科普一下，在數獨中上帝之數為17。
研究參見：http://arxiv.org/abs/1201.0749標準數獨若提示數<17，則數獨不可能存在唯一解。050600000000000730000100000000070800060000050100000000700040200004030000000500060
參考資料：
上帝之數官網
Mini Cube, the 2x2x2 Rubiks Cube
推薦閱讀：
※【不等式】均值不等式及其應用
※Jacobson-Hersteins Commutativity Theorem
※題都城南庄（崔護）
※Atiyah的青春數學之夢