Cube

· · 个人记录

序 基本概念

::::info[介绍]

考虑一个长这样的三阶 ^{[1]} 魔方：

我们可以将其拆分为一些部分：角块，棱块，中心块（①，②，③），在标准三阶魔方中，分别有 8、12、6 个。

你可以对六个面中的任意一面进行一个 90x° 度的转动。对于每一个独立的块，在进行任何转动操作的时候，都可以视为一个整体。

:::warning[一些约定与符号]

WCA^{[2]} 或一般标准规定下的魔方操作是绿色面朝前，白色面朝上（便于统一），同时标准配色为白、黄、红、橙、绿、蓝。

标准魔方的每步操作可以用符号表示。如下图用二阶魔方演示了部分操作：

U（up）表示顶层顺时针旋转 90°。

U' 表示顶层逆时针旋转 90°。

U2 表示顶层旋转 180°。

同理：

在此之外还有一些符号：

本文中可能会提及 R 类操作（或简写为 R 操作）在一些语境下包含了 R2 和 R' 的含义。因为可以操作多次 R 来达成这一效果。

魔方的还原状态定义为每面颜色单一的状态。

:::

::::

一 发展历史

这部分对理论不是很重要。

:::info[展开]

魔方作为益智玩具于 1974 年由匈牙利教授厄尔诺·鲁比克发明。

在发展历史中，具有速拧、盲拧、最少步等玩法。

速拧，即在尽可能短的时间里将打乱状态下的魔方复原，目前主流的速拧方法有 CFOP、桥式等。

盲拧，即在尽可能短的时间里记住魔方的状态并随后在蒙眼状态下复原魔方（两部分均计时）。具体方法有四步法以及彳亍法等。

最少步，即给出一个特定的打乱状态，在规定时间（通常是一小时）内找出复原所需的最少步数。

WCA 目前收录的项目有：二~七阶速拧、三阶单手、三阶盲拧、四阶盲拧、五阶盲拧、多盲、最少步、金字塔、斜转、五魔方、SQ1。后四种属于异形魔方范畴。

WCA 在之前还举办过三阶脚拧和魔板（八板、十二板）等项目，均因各种原因取消。Link

:::

二 性质

我们先来研究比较简单的二阶魔方。相比于标准三阶魔方，二阶魔方相当于只包含了八个角块的部分。

:::info[不变量]

首先有一个东西叫做角块方向和的不变性。

我们假定魔方保持初始方向（不做整体转动），仅对于某一个面进行转动。

对于一个角块，它包含了三种不同颜色（在标准配色中是白黄之一，红橙之一，蓝绿之一）。我们将白黄称为标准色，并将白面和黄面（顶层和底层）称为标准面。

然后定义每个角块的权值：

如果这个角块的标准色（白色，黄色）朝向为标准面（即朝上或朝下）则其权值为 0。

如果这个角块的标准色朝向相对于标准面顺时针旋转了（如图），则其权值为 1。

如果这个角块的标准色朝向相对于标准面逆时针旋转了，则其权值为 -1。

简单来讲，就是相对于标准面旋转的情况。

有以下结论：

对于一个正确的打乱状态下的二阶魔方，它的八个角块权值和为 0。

:::

:::info[证明]

证明容易。

考虑归纳，首先初始的复原状态下，权值和为 0。

我们可以从复原状态下出发，对魔方做若干次操作。如果是合法的打乱状态，一定存在一个操作序列。

对于每一步，操作是旋转某个面，会影响到四个角块。如果是 U 或 D 类 ^{[3]} 操作，显然对于影响的四个角块，标准色的朝向没有改变，权值也不会改变。

对于其他操作，比如 R 操作，我们可以手玩一下。

如果块属于图示的第一类块，权值变化如下：

f_1(v) = \begin{cases} 1 & v=0 \\ 2 & v=1 \\ 0 & v=2 \end{cases}

第二类块变化如下：

f_2(v) = \begin{cases} 2 & v=0 \\ 0 & v=1 \\ 1 & v=2 \end{cases}

观察到旋转操作对第一类块权值的本质影响是在 \bmod 3 意义下 +1，对第二类块权值的影响是在 \bmod 3 意义下 -1（人话说就是前者相对于标准面顺时针旋转，后者逆时针旋转）。

由于每次旋转操作影响到两个一类块和两个二类块，权值总和不变。

:::

定义魔方的两个状态不同，当且仅当它们不能通过任意整体旋转全等。

::::info[状态计数]

我们希望对二阶魔方所有本质不同的总状态数进行计数。

考虑固定某一个角块的位置和方向（在标准配色中即黄橙蓝块），不难发现此时可以执行的动作是 U、R、F （影响到剩余其他七个块）。这样方便计数。

（事实上，即使例如执行了 L 这样的操作，在二阶魔方意义下我们也可以视作将原魔方做了一次 R' 操作并整体旋转一次。二者没有本质区别）

其他七个块的位置如果不加其他考虑的话，有 7! 种排列；方向组合有 3^7 种情况。

由于我们之前得到方向权值在 \bmod 3 意义下和 为 0，因此其实固定 6 个块后，第 7 个块的方向权值是确定的。

综上，二阶魔方的总合法状态数为 G_2=\dfrac{7! \times 3^7}{3} = 3674160 种。

对于三阶魔方，我们不用角块定向，而是使用中心块进行定向（容易注意到，进行 R，U 等操作是不会引起中心块位置的变化）。因此，八个角块的位置和方向都有可能变化（不过仍然遵循上述限制）。

同时三阶魔方还加入了棱块这一变量，我们可以用类似的定向方法来证明棱块的朝向也是有一定限制的。

还是考虑在绿前白上的情况，我们定义颜色的优先级从大到小为白黄、绿蓝、红橙，权值分别为 3 到 1。

如果一个棱块两边的颜色优先级关系等于两面中心块的颜色优先级关系，则称其方向正确，否则方向错误。

对于 U 和 D 操作，两个优先级关系均未发生变化（白黄始终大于其他面）。

对于 L 和 R 操作，两个优先级关系均未发生变化（红橙始终小于其他面）。

对于 F 和 B 操作，第二类块对应的两个面的优先级发生了变化，因此二类块的方向会发生变化。三类块亦同（要么从正确变成错误，要么从错误变成正确）。

所以只有 F 和 B 会影响操作，并且一次旋转操作同时影响了 4 个棱块。

操作前正确棱块设为 c 个，错误棱块即为 12-c 个。每个受影响的棱块相当于一个 \pm1 的贡献，因此操作四次后，正确棱块和错误棱块数量的奇偶性不变。

因此结果是，固定十一个棱块的朝向之后，剩下一个棱块只有一种方向，因为奇偶性已经确定了。

综上，棱块的贡献为 \dfrac{12!\times 2^{12}}{2}。

因此三阶魔方的总合法状态数为 G_3= \dfrac{8! \times 3^8 \times 12! \times 2^{12} }{2 \times 3 \times 2} \approx 4.325 \times 10^{19} 种。

分子中还多包含一个 2 项，这是因为魔方相当于一个置换群，其进行的每一步操作都是偶置换，只有偶置换的状态才能复原（映射到三阶魔方上就是说，如果单独交换一对棱块，是无法复原的）。

:::info[如何理解另外的 \div 2 项]

我们还可以从奇偶排列的角度理解。其定义为，从原排列 p=\{1,2\dots n \}(n>1) 开始，每次交换两个不同的数，则交换奇数次后得到的是奇排列，偶数次（包括 0 次）后得到的是偶排列。

通过观察逆序对的奇偶性，容易证明任意奇排列只能通过奇数次操作得到，反之亦然。

有简单引理；对于一个长度 n 的排列的所有情况，其奇排列和偶排列是各占一半的。考虑对称性即可。

在三阶里面，交换两个角就是一个奇排列，交换三个角（三角换）就是偶排列。

（在学一些具体的公式之后可能理解会更加深刻，比如 T-perm 的作用是交换一对棱块和一对角块，同时改变了奇偶性）

无论如何，在一组数中，奇排列和偶排列总是各占一半的，于是我们有下面四种组合。

前两种是合法的，后两种是不合法的。正好占了一半的情况。

:::

我们尝试将结论拓展到任意阶数的魔方上。

先考虑偶数阶（n=2k）的情况，八个角块的情况即 G_2。

翼棱组共有 12 \times 2 = 24 组可以排列，且固定位置后方向也固定。如图所示的六阶魔方，每个翼棱组可以分成 k-1=2“块”棱。总排列数为 (24!)^{k-1}。

中心组分为若干种情况。如对于如图所示的六阶魔方，圈内是四种不同的中心块。每种中心块的位置变化是独立的。

对于每种中心块，每面有四个可以容纳的位置，共 24 个，因此方案数为 24!。

然而，注意到每种中心块都包含 6 组 4 个相同的颜色，这些相同的中心块改变位置之后是不会影响方案数的。因此式子还要除以 {4!}^6。

中心组的总方案数为 (\dfrac{24!}{{4!}^6})^{(k-1)^2}。

综上，G_{2k}=G_2 \times (24!)^{k-1} \times (\dfrac{24!}{{4!}^6})^{(k-1)^2}。

对于奇数阶的魔方：

角块和中心棱的排列数为 G_3。

翼棱组同理，为 (24!)^{k-1}。

中心组相比于偶数阶，每组的方案数仍为 \dfrac{24!}{{4!}^6}，不过不同的组数是 k(k-1)（如上是 3 \times 2 = 6）。

综上，G_{2k+1}=G_3 \times (24!)^{k-1} \times (\dfrac{24!}{{4!}^6})^{k(k-1)}。

::::

3 上帝之数

::::info[展开]

上帝之数的含义：

对于标准魔方（如三阶）的任意打乱状态，将其还原所需的最少步数。

如图是二阶魔方的状态分布表。横轴（HTM）表示在半转计量法下（旋转 90° 和 180° 都算一步）的步数，纵轴（QTM）表示四分之一转计量法下（旋转 90° 算一步，180° 算两步）的步数。

比如对 (4,3) 坐标的 144 个状态，它们在半转计量法下至少需要 3 步，而在四分之一转计量法下至少需要 4 步复原。

此事在A079761中亦有记载。

注：HTM 主要适用于速拧相关，因为一般来说进行 R2（180° 旋转）和 R 的速度是差不多的。WCA 最少步比赛也采用了这个标准。

对于三阶魔方，上帝之数（不加指代的话，一般指 HTM）在 2010 年通过穷举被证明是 20。

目前四阶魔方上帝之数已证明的下界不超过 55。

对于一般的 n 阶魔方，我们只知道这个最坏情况下需要的步数（即“上帝之数”）的增长随着阶数 n 大致呈 O(\dfrac{n^2}{\log n}) 增长。来源Link

这篇论文还证明了随着 n 的增长，上帝之数的计算是 NP 完全问题。

:::info[闲话：如果你想出最少步题？]

对于二阶的 10^6 种状态，你可以对于四个角块的状态随便压位然后跑最短路（误

搜索+哈希即可。

三阶难以直接搜索，即使通过 meet-in-the-middle 来解决（即从还原状态搜索 10 步并记录所有状态，之后从打乱状态搜索 10 步进行匹配）结果也过于庞大。

如果希望得到更加优秀的做法，可以参考下文。

:::

注：以下 G 相关符号与上文排列数无关。

魔方的群论原理大概就是说，给定一个还原状态，然后给定一个操作集合，则可以从初始状态按照这个操作往外搜索，得到若干状态结果。

举个例子，如果操作集合为 \{\textrm R\}，则只能得到四种情况（R 可以重复操作，但只能得到四种结果）。

如果集合为 \{\textrm{U,D,L,R,F,B}\}，则可以覆盖所有状态。

降群法解最少步的基本方法就是，将魔方从一个大集合（还原状态和初始所有操作形成的群）降解到更小的子群，最后到单位子群即还原状态。

上图是 1981 年 7 月 Thistlethwaite 提出的四阶段算法，证明了上帝之数的上界为 52。

这里有一些用程序实现寻找三阶魔方解的优秀办法。其中 rk2 采用的便是上述的降群方法。

第一步（G_0 \to G_1），本质上是将棱块的方向归位（即将 2^{11} 种棱块方向的排列缩减到 1）。

具体来说，我们前文提到过棱块方向的奇偶性。如果要翻转一个或多个棱块，必须要用到 F，R，U 操作的组合（这里我们将 F 和 D，L 和 R 等操作视作等价，因为魔方具有镜像性），如 OLL57。

由于 G1 内的状态不能使用 U（只有 U2 操作），我们考虑如何在这一步就将所有棱块的方向统一（方向这个概念可以参考前文的定向）。

【building】

::::