且听风吟

前幾天和同事吃飯的時候討論 "任意狀態的三階魔方最多需要多少步一定可以復原" (God's Number) 的時候延伸到一個問題，如何計算三階魔方所有可能的狀態數，當時考慮的比較粗糙，回來之後重新思考查了些資料這裡順便記錄下。

三階魔方狀態數的計算#

這是一個普通的三階魔方的立體圖和展開圖。一共六個面，即六個中心點 (中心點不可轉動，不需要考慮其狀態數)，八個角塊 (每個有三面顏色)，十二個邊塊 (每個有兩面顏色)。

角塊狀態數#

角塊有八個位置，所以位置的狀態數是 $8!$ 每個角塊有三面顏色，但顏色狀態數並非 $3!$ 考慮展開圖中紅色面左下角的那個角塊，三面顏色的順時針相對順序是固定的即：[綠紅黃] 任意旋轉下不可能出現：[黃紅綠] 這種情況 (把魔方拆了再重裝也不可以)。所以每個角塊一共只有三種顏色狀態即 ABC CAB BCA

還要考慮一件事情，即角塊之間的狀態是會相互影響的，一旦七個角塊的位置和顏色都已經固定後，第八個角塊的顏色是確定的。換句話說，不可能在不修改其他七個角塊狀態的情況下只修改第八個角塊的顏色狀態。所以最後一個角塊的顏色狀態數是 $1$ 角塊的總狀態數為 $(8*3) * (7*3) ... (2*3) * (1*1) = 8! * 3_{}^{7}$

邊塊狀態數#

分析方式和角塊類似，一共十二個位置，位置狀態數為 $12!$ 顏色狀態只有兩種 AB 和 BA 且最後一個邊塊的顏色是固定的。則邊塊的總狀態數為 $12! * 2_{}^{11}$

總狀態數#

現在我們有了角塊狀態數和邊塊狀態數，但是直接相乘得到的結果會包含一些不可能的狀態。

首先明確一件事情：不可能在不修改其他塊的狀態的情況下，只交換兩個角塊 (或者兩個邊塊) 的位置，因為在拧魔方的時候是按面拧的，每個塊的轉動會影響到其周邊的塊。

假設我們正常將魔方拧到一個合法狀態 $s1 = ...AB...$ 其中 $AB$ 表示兩個角塊 (或者兩個邊塊) 的位置狀態，那顯然不可能出現 $s1_{flip} = ...BA...$ 這種由 $s1$ 僅翻轉 $AB$ 的位置而不修改其他塊狀態的情況。而在我們直接相乘得到的所有狀態中，其實是包含了每種合法狀態及其翻轉狀態的集合：

$\left \{ s1, s2, .., sn, s1_{flip}, s2_{flip}, .., sn_{flip} \right \}$

所以在計算總狀態數時還要除以 $2$ 最終結果為：

$1/2 * 8! * 3_{}^{7} * 12! * 2_{}^{11} = 43252003274489856000$

參考：calculating-the-number-of-permutations-of-the-rubiks-cube