且听风吟

前几天和同事吃饭的时候讨论 "任意状态的三阶魔方最多需要多少步一定可以复原" (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