一個n階魔方在最壞情況下至少需要幾步能夠復原？
n&>=2
想到哪寫到哪，寫得有點亂，湊合看吧。下述n階魔方均指正六面體n*n*n純色魔方（不考慮中心塊的朝向）。
對於一般的n階魔方，我們只知道這個最壞情況下需要的步數（即「上帝之數」）的增長隨著階數n大致呈O(n^2/log(n))。詳情可圍觀：http://arxiv.org/abs/1106.5736v1。這篇paper里給出了一個構造性的解法。儘管係數比較大，但步數增長的階依然是 O(n^2/log(n)) 。另外這篇文章還證明了隨著n的增長，上帝之數的計算是NP完全問題。
而精確的數值，迄今為止在現有的計算能力下我們只有n=2或3的結果，即二階的上帝之數為11步，三階的上帝之數為20步。隨著n的增長，上帝之數的計算量呈幾何級數增長。以二階或三階為例，二階上帝之數的計算即便放到個人電腦上，也可以在不到1秒內完成。而三階則需要35年。至於更高階，根據現有的計算能力和演算法，計算四階魔方某一個充分打亂的狀態還原所需要的最少步數都是一個相當難的問題，其計算量甚至超過證明三階上帝之數過程中的所有計算量之和。
可以通過組合數學的方法給出上帝之數的下界（例如三階轉動17步所能達到的狀態小於總狀態數，所以我們可以斷定必然存在一些狀態須要至少18步才可以復原），估算結果可以圍觀：http://cubezzz.dyndns.org/drupal/?q=node/view/236
而想獲得更大的下界，通常的做法只能是尋找一個特定的狀態，然後通過各種搜索演算法證明不存在小於k步的解法，從而證明至少存在一個狀態需要k步才能還原，即上帝之數&>=k。以三階魔方為例，1995年Reid證明了「super flip」（即所有角塊正確，棱塊原地翻轉）狀態不存在19步或更短的解法，從而證明上帝之數&>=20。（其證明過程利用了該狀態的對稱性，極大的減小了計算量）
從三階上帝之數的進展過程來看，上帝之數上界的估算方法一般為：
a) 將還原劃分成若干個階段。
b) 分別計算每個階段所需要的最大步數。 c) 將各個階段所需要的步數加起來即可估算上界。以三階魔方為例，1981，Thistlethwaite先生提出了分4個階段還原魔方的方法，並分別計算了每個階段需要的最大步數，最終給出了三階魔方至多需要52步即可還原的上界，即上帝之數&<=52。
Rokicki大神通過coset分析的手段給出了進一步減小上帝之數的方法。具體我就不展開了，感興趣的朋友可以圍觀三階魔方上帝之數=20的證明：God"s Number is 20
最後提一下，對於四階魔方，我通過三階段降階的方法證明其上帝之數&<=57 (http://cubezzz.dyndns.org/drupal/?q=node/view/525)，暫時是至今為止我們所知道的最小上界。作為參考，四階魔方上帝之數的下界為35步，尚有一定距離。
另外，上個月Rokicki發起了一次四階最少步比賽：4x4x4 FMC (computer and human) 對於所有5個充分打亂的狀態，我們都找到了40步或更短的解法。至少有理由相信四階的上帝之數在35~40步左右。====================更新於2015-03-09四階上帝之數最新的進展是&<=55步（http://cubezzz.dyndns.org/drupal/?q=node/view/541）。謝邀。
暫時還沒有通用的演算法計算確切的數字，至於為什麼。。。計算領域，NP問題什麼的- -有興趣可以搜一下。計算準確值：現在的思路是使用降群，然後每一個sets使用計算機進行大量窮舉運算，比如說三階的20步，就是用把所有情況分成2,217,093,120個子集，然後用google的集群花了35個CPU年算出來的。資料看這裡God"s Number is 20另外這裡面有提到，1995前一直認為這個數字的下界是18，後來更正為20， 之後20年只有上界在縮小，下界沒有進步過了，很有可能不會再進步了，除非演算法進步，或者計算力進步到能夠在可接受的時間與資源代價內窮舉所有情況。
扯遠了。。。如果是計算上帝之數的範圍的話，還是可以有的- -科普：可以看果殼這篇文章數學，讓魔方擰得更快論文：http://arxiv.org/abs/1106.5736v1反正論文我是沒有足夠的耐心看下去。。。。。。這個問題很複雜的吧，幾年之前好像讀者上有介紹3階現在證明到20步，現在不知道證明到多少了
將任意三階魔方打亂後，最小還原步數究竟是多少？這一問題困擾了數學家長達三十多年，這個最小還原步數也被稱為「上帝之數」。美國加利福尼亞州科學家近日利用計算機破解了這一謎團，他們證明任意組合的魔方均可以在20步之內還原。上帝之數=20三階魔方有43,252,003,274,489,856,000(約合4.3×10的19次方)種不同的可能組合狀態，但它都能在20步之內還原。見上帝之數_百度百科
可以。我以前編寫過一套用盲擰演算法求解魔方的程序，就是可以輸入魔方的打亂公式，然後給出求解的步驟，只不過步數較多。這個主要是給盲擰用的，不過姑且也能滿足求解魔方的要求。目前市面上有很多可以求解的軟體，原理我知道得不太詳細，等大神來說，感謝邀…
顯示全部
推薦閱讀：