目录一复原问题完整模型1部件信息2复原状态3部件朝向4幽灵部件5可执行操作6部件目标位置二分图7唯一部件、可交换部件8关于构建部件目标位置二分图的补充说明9魔方状态恒等式10平凡恒等式11恒等式的等价表述12限位朝向13状态总集、限位状态总集、可达总集14可达系数、限位可达系数二复原方法推导的完整步骤1确定所有部件信息2确定复原状态3确定所有可执行操作4构建部件目标位置二分图5区分出唯一部件和可交换部件6推导魔方状态恒等式三常见的魔方状态恒等式1三阶魔方1中心块的朝向棱块的位置2中心块的朝向角块的位置3棱块的朝向4角块的朝向2斜转魔方1角块的位置奇偶分组2幽灵部件的朝向角块组的奇偶性3角块的组内位置4幽灵部件的朝向中心块的位置5角块的朝向6中心块的朝向90度的倍数7中心块的朝向180度的倍数3四阶魔方1中心块的位置2中心块的朝向。3棱块的位置4棱块的朝向5中心大正方形的朝向角块的位置5幽灵部件的朝向中心大正方形的朝向棱组的位置6中心大正方形的位置7角块的朝向四魔方恒等式同模无环图1状态组合2状态拆分3恒等式覆盖4带权图双属性边5同模6无环图7自由状态五魔方的合法概率1连通子集合法概率计算2魔方合法概率计算3常见魔方的合法概率1三阶魔方2斜转魔方3四阶魔方待更新六解决状态恒等式的三阶段一复原问题完整模型魔方理论提到一个魔方的状态包括所有部件的位置和朝向魔方的复原问题就是对于任意状态找到通向复原状态的有向路径。这个表述比较易懂但是忽略了一些细节这里我们补充一些细节形成完整的模型。1部件信息每个部件有4个信息所处位置形状朝向表面图案其中形状和表面图案是静态信息而所处位置和朝向是动态信息。2复原状态魔方的总状态由所有部件的总状态组成包含2部分一是所有部件的位置二是所有部件的朝向。而决定复原状态的是所有部件的形状和表面图案。3部件朝向所有朝向只根据形状推导出一共有多少种朝向比如三阶魔方的角块有3种棱块有2种中心块有4种。目标朝向在所有朝向中有一部分朝向是满足复原状态的。一般情况下要么只有一种目标朝向要么所有朝向都是目标朝向但是也不排斥特定图案下a(a1)个是目标朝向b(b0)个不是目标朝向。4幽灵部件把整个魔方理解成一个大部件这个额外的部件我们称之为幽灵部件。可以把它理解成位于最中间的看不见的一个幽灵对它的操作其实就是把整个魔方旋转。虽然这个幽灵部件看不到对于三阶空心魔方能看到最中间的空洞还是看不到这个幽灵但是却是整个魔方的参考系核心。和普通部件一样只根据形状推导出一共有多少种朝向。比如三阶空心魔方的幽灵部件有24种朝向。对于存在参考系核心的魔方我们也可以认为不存在幽灵部件。比如三阶魔方可以认为不存在幽灵部件但是四阶魔方存在。5可执行操作一般情况下一个可执行操作指的是一部分部件完全不动另外一部分部件移动位置或朝向。也可以新增一个特殊操作幽灵部件调整朝向即整个魔方转动。一般情况下一个可执行操作的移动部件是不包含幽灵部件的比如三阶魔方的转动我们指的是2层不动1层动这样中心块的位置永远不变也就是幽灵部件不动。6部件目标位置二分图任意状态下的n个部件和复原状态下的n个部件位置是如何对应的对于绝大部分魔方这一步是朴素的答案是显而易见的。对于少部分魔方比如大脑魔方这一步也是需要推理的。无论是直接得到还是推理得到最终都会得到一个二分图表示每个部件在复原状态下可能处于哪些位置这个二分图我们称之为部件目标位置二分图。注意这里的位置可以理解成相对位置比如三阶空心魔方的所有部件的相对位置只有1种绝对位置有24种因为幽灵部件有24种朝向。注意这个二分图并不总是一一映射对这个二分图的刻画就产生了可交换部件的概念。7唯一部件、可交换部件我们首先定义连通分量完全正则二分图对于一个二分图一边是N个点对应N个部件另一边也是N个点对应N个位置基于连通分量把这个无向图做分割如果“得到的每个连通子图都是完全二分图且两边的节点数相同”那么我们称这个图是连通分量完全正则二分图。PS完全二分图的定义参考这里以连通分量完全正则二分图{1-a 2-b 3-c 3-d 4-c 4-d 5-e 5-f 6-e 6-f 7-h}为例我们拆分成5个部分分别是{1-a} {2-b} {7-h}{3-c 3-d 4-c 4-d}{5-e 5-f 6-e 6-f}这样7个部件可以表示成11122其中的111我们称之为唯一部件3个其中的22我们称之为可交换部件2组每组2个。所有魔方都是连通分量完全正则二分图。也就是说我们总是可以把所有部件不算幽灵部件表述成唯一部件*n可交换部件m1可交换部件m2...这样的形式。例如三阶魔方是1*26即26个唯一部件四阶魔方是1*32444444即每个面的4个中心块是可交换部件剩下32个都是唯一部件。8关于构建部件目标位置二分图的补充说明新手玩家可能会疑惑四阶魔方的2个棱块长得一模一样为什么不算做可交换部件而且唯一部件这里涉及一个底层概念“确定复原状态”用的是直接交换任意2个部件去做的分析而“构建部件目标位置二分图”则是基于可执行操作去分析的。常见的区别在于2个部件如果按照长方体去理解是可以交换位置的但是考虑到部件实体的形状包括被遮起来的奇形怪状的部分直接交换2个部件其实是放不下的。9魔方状态恒等式这里涉及5个常见问题1对于可交换部件是否可以只交换任意2个2对于所有朝向都是目标朝向的部件是否可以单独改变一个部件的朝向3对于可对半分的魔方如何理解幽灵部件的朝向问题4幽灵部件的哪些朝向是对的5多个复原状态哪些是最终可达的诸如此类的问题答案本质上都是同一个形式提出一个魔方状态恒等式。比如三阶图案魔方A如果把6个中心块的方向全都随机调整那么最后方向能对齐的概率是1/2换个说法就是6个中心块的朝向状态之和 % 2 是定值。10平凡恒等式我们用1到12这12个数构成的集合表示所有状态如果我们想表达1 3 5 7 9 11是合法状态另外6个是非法状态我们可以表示成恒等式x%21如果我们想表达3 6 9 12是合法状态另外8个是非法状态我们可以表示成恒等式x%30对于全部是合法状态的情况我们可以用平凡恒等式x%10表示。也就是说各种恒等式其实都是用来描述所有状态中哪些是合法的而且一定是n个状态中有n/k个状态是合法的n是k的倍数。当我们不想准确地定义状态数只想笼统描述时我们可以说这是一个mod k的状态问题。11恒等式的等价表述mod 1的状态问题通俗来讲就是可以随便交换。mod 2的状态问题通俗来讲就是奇偶性。如果是位置状态那就是所有部件位置随机打乱合法的概率是1/2如果是朝向状态那就是单个部件随机朝向合法的概率是1/2也就是说mod k的状态问题也就是恒等式 x % k c的等价表述就是随机选择一种状态合法的概率是1/k12限位朝向对于单个部件我们可以很简单的推理出如果它经过若干次可执行操作后到达某个位置所有朝向中哪些是可达的哪些是不可达的。例如三阶魔方的角块和棱块所有朝向都是可达的。四阶魔方的棱块在每个位置都有1个朝向可达1个朝向不可达。我们把这种基于特定位置推算出的所有朝向的子集称之为限位朝向。13状态总集、限位状态总集、可达总集根据每个部件的所有朝向排列组合之后即可得到状态总集。根据每个部件的限位朝向排列组合之后即可得到限位状态总集。其中有些状态是可达的有些是不可达的。我们把其中可达的部分构成的子集称为可达总集。14可达系数、限位可达系数可达总集占状态总集、限位状态总集的比例往往是一个分子分母都比较小的有理数我们把这个比例称之为可达系数、限位可达系数。三阶魔方的可达系数是1/12限位可达系数也是1/12这里面蕴含了3个魔方状态恒等式分别是mod 2的mod 2的mod 3的。二复原方法推导的完整步骤注意我这里指的是拿到一个新魔方之后独自推导复原方法需要考虑哪些内容而不是一个魔方推导完之后有哪些复原步骤。1确定所有部件信息这一步一定是朴素的没有难度。2确定复原状态这一步一般是朴素的也不排除少部分魔方这一步就需要一些推理比如基于图案满足某种条件定义复原状态。3确定所有可执行操作这一步一般是朴素的也不排除少部分魔方这一步就需要一些推理比如闪蝶系列魔方。4构建部件目标位置二分图这一步一定是朴素的没有难度。不过这里涉及一个常见情况对于一个多面体外形的魔方复原状态下各个面的相对位置可能不唯一构建的部件目标位置二分图可能也有多个图至于其中哪些是最终可以达到的哪些因为可执行操作的限制实际上是达不到的在复原方法推导的过程中可能会在比较靠后的位置才能定下来。如果这一部分的推理内容单独另算那么“构建部件目标位置二分图”这一步就是朴素的。5区分出唯一部件和可交换部件这一步一定是朴素的没有难度。6推导魔方状态恒等式每一种类型的魔方状态恒等式都是只有部分魔方涉及的。只要一旦涉及都不会太简单。常见例子参考上文。为什么要推导这个有4个理由1必须要知道哪些状态不属于可达总集这样的状态就不需要推导处理方法。2必须要知道可达总集的所有状态都有了明确的处理方法才知道复原方法推导完了。3一个非必须的理由基于这套思路可以减少复杂情况的出现。参考三阶图案魔方B4一个非必须的理由基于这套思路可以辅助发明处理复杂情况的公式。参考四阶魔方。三常见的魔方状态恒等式PS平凡恒等式就不记录了除非它很神奇。PS可以认为每个魔方的复原状态都是唯一的对于极光闪蝶的镜像状态把它理解成未复原。1三阶魔方1中心块的朝向棱块的位置这是一个mod 2的状态问题。2中心块的朝向角块的位置这是一个mod 2的状态问题。3棱块的朝向这是一个mod 2的状态问题。4角块的朝向这是一个mod 3的状态问题。注意问题1和问题2是有关联的因为都涉及中心块的朝向。三阶魔方的可达系数、限位可达系数等于1/2 * 1/2 * 1/3 1/12PS中心块的位置就是平凡恒等式。2斜转魔方斜转魔方角块的位置分成3个层级位置奇偶分组、角块组的奇偶性、组内位置1角块的位置奇偶分组这是一个mod 35的状态问题。C7,3 35换句话说8个角块随机打乱位置原本不相邻的4个角块打乱之后刚好各部相邻的概率是1/352幽灵部件的朝向角块组的奇偶性这是一个mod 2的状态问题。3角块的组内位置这是两个mod 2的状态问题。因为2个组是独立的所以是两个独立的状态恒等式。4幽灵部件的朝向中心块的位置这是一个mod 2的状态问题。5角块的朝向这是两个mod 3的状态问题。6中心块的朝向90度的倍数这是六个mod 2的状态问题。在幽灵部件朝向不动的前提下每个中心块只能旋转180度的倍数。7中心块的朝向180度的倍数这是一个mod 2的状态问题。3四阶魔方1中心块的位置应该是一个mod 2的状态问题。因为是自由原子状态所以不用深究。2中心块的朝向。应该是一个mod 2或者mod 4的状态问题。因为是自由原子状态所以不用深究。PS中心块的位置和朝向指的是4个中心块相对1个中心正方形的相对位置和相对朝向。3棱块的位置这是一个mod 1的状态问题。但是在不打破6个中心正方形的情况下是一个mod 2的状态问题。也就是说单棱翻转一定是通过中心正方形的拆开重组来解决的。PS算这个状态的奇偶性可能直接看成所有的棱块排成的序列但是严谨的讲这一部分其实是棱块相对棱组的位置。4棱块的朝向这是一个mod 2的状态问题。5中心大正方形的朝向角块的位置这是一个mod 2的状态问题。5幽灵部件的朝向中心大正方形的朝向棱组的位置这是一个mod 2的状态问题。所以会有1/2的概率出现“双棱对换”6中心大正方形的位置这是一个mod 1的状态问题。PS 本质上双棱对换就是棱组位置奇偶性有问题解决方案就是直接整个魔方转90度幽灵部件的朝向奇偶性改变中心大正方形的朝向奇偶性不变棱组的位置奇偶性改变问题解决。带来的副作用就是最新大正方形的位置被影响了而中心大正方形的位置是一个mod 1的状态问题可以单独调整。7角块的朝向这是一个mod 3的状态问题。四魔方恒等式同模无环图1状态组合四阶魔方中的中心正方形的位置和中心正方形的朝向是不可分割的所以可以理解成“中心正方形的位置和朝向”就是一个状态。同理四阶魔方中的“中心块的位置和朝向”也是一个状态。我们把这种关系称之为2个原始状态组合成1个原子状态。2状态拆分斜转魔方角块的位置分成3个层级位置奇偶分组、角块组的奇偶性、组内位置我们把这种关系称之为1个原始状态拆分成多个原子状态。定理一状态组合拆分二分图的形态定理。如果有n组部件那就有2n个原始状态把原始形态和原子形态表示成二分图那么每个连通子图要么只有1个原始状态要么只有1个原子状态。3恒等式覆盖我们把所有的2n个原始状态经过组合和拆分之后得到的所有原子状态称之为原子状态全集。定理二恒等式覆盖定理。算上平凡恒等式一个魔方的所有恒等式一定会涵盖到原子状态全集且每个恒等式都恰好涉及2个原子状态。PS不同的恒等式可能会涉及到同一个原子状态。4带权图双属性边每一个魔方恒等式都可以表示成x-yc (mod k)的形式。因为状态的定义是开放式的所以我们也可以说xyc (mod k)即xy是一个mod k的状态问题。这也就意味着在同一个魔方的的不同恒等式中xy1c1和y2z-c2里面的y1和y2并不是完全相同的但是我没有专门区分。基于x-yc (mod k)可以构造一条边连接x和y的边的权重是c边的模是k也就是每条边含有2个属性。PS点x和点y也就是原子状态。5同模定理三同模定理。基于无向图分割也就是并查集算法得到的每一个子图的所有边的模一定是相同的。6无环图构建的并查集其实是差分并查集所以每一条即将构成环的边都是冗余的边。比如三阶魔方我们也可以说棱块的位置角块的位置是mod 2的状态问题但是这条边是冗余的。以上就解释清楚了怎么样根据一个魔方的所有恒等式得到一个同模无环图。7自由状态在上文中我们定义了可交换部件、所有朝向、目标朝向。1如果n个部件互为可交换部件那么这n个部件的相对位置状态就是自由状态。如四阶魔方的中心块2如果一个部件的所有朝向都是目标朝向那么这个部件的朝向状态就是自由状态。如三阶魔方的中心块、四阶魔方的中心块3如果一个原子状态是多个原始状态组合而成那么只要其中有一个是自由状态得到的就是自由原子状态。五魔方的合法概率1连通子集合法概率计算定理四连通子集合法概率定理。假如一个连通子集的所有边都是mod k的去掉其中的自由原子状态还剩n个非自由的原子状态那么把魔方拆开随机重组这一个连通子集对应的原始状态可以同时复原的概率就是(1/k)^nPS斜转魔方角块的组内位置是两个mod 2的状态问题可以理解成这是2个连通子集。2魔方合法概率计算定理五魔方合法概率定理。把魔方拆开随机重组可以复原的概率等于每个连通子集的合法概率之乘积。3常见魔方的合法概率1三阶魔方1/2 * 1/2 * 1/3 1/122斜转魔方1/(35*2*2*2*3*3) 1/25203四阶魔方待更新1 * 1 * 1 * 1/2 * 1 * 1 * 1/3 1/6六解决状态恒等式的三阶段三个阶段代表三种风格迥异的复原方法。阶段一算法在即将产生状态和的时候最后一步合理操作保证状态和正确。阶段二算法在刚刚产生状态和之后立刻校验状态和如果不对直接调整。阶段三算法在最后出现没法继续操作必须调整状态和的时候再调整。显然3种思路对本质的理解是递降的即阶段一算法阶段二算法阶段三算法。但是如果理解了本质那么创造相应公式的难度是递增的即阶段一算法创造公式是最容易的甚至可能不需要任何公式。四阶魔方的层先法一般人学的都是阶段三算法而我在高阶魔方自动复原里面处理单棱翻转问题用的就是阶段二算法。
目录一复原问题完整模型1部件信息2复原状态3部件朝向4幽灵部件5可执行操作6部件目标位置二分图7唯一部件、可交换部件8关于构建部件目标位置二分图的补充说明9魔方状态恒等式10平凡恒等式11恒等式的等价表述12限位朝向13状态总集、限位状态总集、可达总集14可达系数、限位可达系数二复原方法推导的完整步骤1确定所有部件信息2确定复原状态3确定所有可执行操作4构建部件目标位置二分图5区分出唯一部件和可交换部件6推导魔方状态恒等式三常见的魔方状态恒等式1三阶魔方1中心块的朝向棱块的位置2中心块的朝向角块的位置3棱块的朝向4角块的朝向2斜转魔方1角块的位置奇偶分组2幽灵部件的朝向角块组的奇偶性3角块的组内位置4幽灵部件的朝向中心块的位置5角块的朝向6中心块的朝向90度的倍数7中心块的朝向180度的倍数3四阶魔方1中心块的位置2中心块的朝向。3棱块的位置4棱块的朝向5中心大正方形的朝向角块的位置5幽灵部件的朝向中心大正方形的朝向棱组的位置6中心大正方形的位置7角块的朝向四魔方恒等式同模无环图1状态组合2状态拆分3恒等式覆盖4带权图双属性边5同模6无环图7自由状态五魔方的合法概率1连通子集合法概率计算2魔方合法概率计算3常见魔方的合法概率1三阶魔方2斜转魔方3四阶魔方待更新六解决状态恒等式的三阶段一复原问题完整模型魔方理论提到一个魔方的状态包括所有部件的位置和朝向魔方的复原问题就是对于任意状态找到通向复原状态的有向路径。这个表述比较易懂但是忽略了一些细节这里我们补充一些细节形成完整的模型。1部件信息每个部件有4个信息所处位置形状朝向表面图案其中形状和表面图案是静态信息而所处位置和朝向是动态信息。2复原状态魔方的总状态由所有部件的总状态组成包含2部分一是所有部件的位置二是所有部件的朝向。而决定复原状态的是所有部件的形状和表面图案。3部件朝向所有朝向只根据形状推导出一共有多少种朝向比如三阶魔方的角块有3种棱块有2种中心块有4种。目标朝向在所有朝向中有一部分朝向是满足复原状态的。一般情况下要么只有一种目标朝向要么所有朝向都是目标朝向但是也不排斥特定图案下a(a1)个是目标朝向b(b0)个不是目标朝向。4幽灵部件把整个魔方理解成一个大部件这个额外的部件我们称之为幽灵部件。可以把它理解成位于最中间的看不见的一个幽灵对它的操作其实就是把整个魔方旋转。虽然这个幽灵部件看不到对于三阶空心魔方能看到最中间的空洞还是看不到这个幽灵但是却是整个魔方的参考系核心。和普通部件一样只根据形状推导出一共有多少种朝向。比如三阶空心魔方的幽灵部件有24种朝向。对于存在参考系核心的魔方我们也可以认为不存在幽灵部件。比如三阶魔方可以认为不存在幽灵部件但是四阶魔方存在。5可执行操作一般情况下一个可执行操作指的是一部分部件完全不动另外一部分部件移动位置或朝向。也可以新增一个特殊操作幽灵部件调整朝向即整个魔方转动。一般情况下一个可执行操作的移动部件是不包含幽灵部件的比如三阶魔方的转动我们指的是2层不动1层动这样中心块的位置永远不变也就是幽灵部件不动。6部件目标位置二分图任意状态下的n个部件和复原状态下的n个部件位置是如何对应的对于绝大部分魔方这一步是朴素的答案是显而易见的。对于少部分魔方比如大脑魔方这一步也是需要推理的。无论是直接得到还是推理得到最终都会得到一个二分图表示每个部件在复原状态下可能处于哪些位置这个二分图我们称之为部件目标位置二分图。注意这里的位置可以理解成相对位置比如三阶空心魔方的所有部件的相对位置只有1种绝对位置有24种因为幽灵部件有24种朝向。注意这个二分图并不总是一一映射对这个二分图的刻画就产生了可交换部件的概念。7唯一部件、可交换部件我们首先定义连通分量完全正则二分图对于一个二分图一边是N个点对应N个部件另一边也是N个点对应N个位置基于连通分量把这个无向图做分割如果“得到的每个连通子图都是完全二分图且两边的节点数相同”那么我们称这个图是连通分量完全正则二分图。PS完全二分图的定义参考这里以连通分量完全正则二分图{1-a 2-b 3-c 3-d 4-c 4-d 5-e 5-f 6-e 6-f 7-h}为例我们拆分成5个部分分别是{1-a} {2-b} {7-h}{3-c 3-d 4-c 4-d}{5-e 5-f 6-e 6-f}这样7个部件可以表示成11122其中的111我们称之为唯一部件3个其中的22我们称之为可交换部件2组每组2个。所有魔方都是连通分量完全正则二分图。也就是说我们总是可以把所有部件不算幽灵部件表述成唯一部件*n可交换部件m1可交换部件m2...这样的形式。例如三阶魔方是1*26即26个唯一部件四阶魔方是1*32444444即每个面的4个中心块是可交换部件剩下32个都是唯一部件。8关于构建部件目标位置二分图的补充说明新手玩家可能会疑惑四阶魔方的2个棱块长得一模一样为什么不算做可交换部件而且唯一部件这里涉及一个底层概念“确定复原状态”用的是直接交换任意2个部件去做的分析而“构建部件目标位置二分图”则是基于可执行操作去分析的。常见的区别在于2个部件如果按照长方体去理解是可以交换位置的但是考虑到部件实体的形状包括被遮起来的奇形怪状的部分直接交换2个部件其实是放不下的。9魔方状态恒等式这里涉及5个常见问题1对于可交换部件是否可以只交换任意2个2对于所有朝向都是目标朝向的部件是否可以单独改变一个部件的朝向3对于可对半分的魔方如何理解幽灵部件的朝向问题4幽灵部件的哪些朝向是对的5多个复原状态哪些是最终可达的诸如此类的问题答案本质上都是同一个形式提出一个魔方状态恒等式。比如三阶图案魔方A如果把6个中心块的方向全都随机调整那么最后方向能对齐的概率是1/2换个说法就是6个中心块的朝向状态之和 % 2 是定值。10平凡恒等式我们用1到12这12个数构成的集合表示所有状态如果我们想表达1 3 5 7 9 11是合法状态另外6个是非法状态我们可以表示成恒等式x%21如果我们想表达3 6 9 12是合法状态另外8个是非法状态我们可以表示成恒等式x%30对于全部是合法状态的情况我们可以用平凡恒等式x%10表示。也就是说各种恒等式其实都是用来描述所有状态中哪些是合法的而且一定是n个状态中有n/k个状态是合法的n是k的倍数。当我们不想准确地定义状态数只想笼统描述时我们可以说这是一个mod k的状态问题。11恒等式的等价表述mod 1的状态问题通俗来讲就是可以随便交换。mod 2的状态问题通俗来讲就是奇偶性。如果是位置状态那就是所有部件位置随机打乱合法的概率是1/2如果是朝向状态那就是单个部件随机朝向合法的概率是1/2也就是说mod k的状态问题也就是恒等式 x % k c的等价表述就是随机选择一种状态合法的概率是1/k12限位朝向对于单个部件我们可以很简单的推理出如果它经过若干次可执行操作后到达某个位置所有朝向中哪些是可达的哪些是不可达的。例如三阶魔方的角块和棱块所有朝向都是可达的。四阶魔方的棱块在每个位置都有1个朝向可达1个朝向不可达。我们把这种基于特定位置推算出的所有朝向的子集称之为限位朝向。13状态总集、限位状态总集、可达总集根据每个部件的所有朝向排列组合之后即可得到状态总集。根据每个部件的限位朝向排列组合之后即可得到限位状态总集。其中有些状态是可达的有些是不可达的。我们把其中可达的部分构成的子集称为可达总集。14可达系数、限位可达系数可达总集占状态总集、限位状态总集的比例往往是一个分子分母都比较小的有理数我们把这个比例称之为可达系数、限位可达系数。三阶魔方的可达系数是1/12限位可达系数也是1/12这里面蕴含了3个魔方状态恒等式分别是mod 2的mod 2的mod 3的。二复原方法推导的完整步骤注意我这里指的是拿到一个新魔方之后独自推导复原方法需要考虑哪些内容而不是一个魔方推导完之后有哪些复原步骤。1确定所有部件信息这一步一定是朴素的没有难度。2确定复原状态这一步一般是朴素的也不排除少部分魔方这一步就需要一些推理比如基于图案满足某种条件定义复原状态。3确定所有可执行操作这一步一般是朴素的也不排除少部分魔方这一步就需要一些推理比如闪蝶系列魔方。4构建部件目标位置二分图这一步一定是朴素的没有难度。不过这里涉及一个常见情况对于一个多面体外形的魔方复原状态下各个面的相对位置可能不唯一构建的部件目标位置二分图可能也有多个图至于其中哪些是最终可以达到的哪些因为可执行操作的限制实际上是达不到的在复原方法推导的过程中可能会在比较靠后的位置才能定下来。如果这一部分的推理内容单独另算那么“构建部件目标位置二分图”这一步就是朴素的。5区分出唯一部件和可交换部件这一步一定是朴素的没有难度。6推导魔方状态恒等式每一种类型的魔方状态恒等式都是只有部分魔方涉及的。只要一旦涉及都不会太简单。常见例子参考上文。为什么要推导这个有4个理由1必须要知道哪些状态不属于可达总集这样的状态就不需要推导处理方法。2必须要知道可达总集的所有状态都有了明确的处理方法才知道复原方法推导完了。3一个非必须的理由基于这套思路可以减少复杂情况的出现。参考三阶图案魔方B4一个非必须的理由基于这套思路可以辅助发明处理复杂情况的公式。参考四阶魔方。三常见的魔方状态恒等式PS平凡恒等式就不记录了除非它很神奇。PS可以认为每个魔方的复原状态都是唯一的对于极光闪蝶的镜像状态把它理解成未复原。1三阶魔方1中心块的朝向棱块的位置这是一个mod 2的状态问题。2中心块的朝向角块的位置这是一个mod 2的状态问题。3棱块的朝向这是一个mod 2的状态问题。4角块的朝向这是一个mod 3的状态问题。注意问题1和问题2是有关联的因为都涉及中心块的朝向。三阶魔方的可达系数、限位可达系数等于1/2 * 1/2 * 1/3 1/12PS中心块的位置就是平凡恒等式。2斜转魔方斜转魔方角块的位置分成3个层级位置奇偶分组、角块组的奇偶性、组内位置1角块的位置奇偶分组这是一个mod 35的状态问题。C7,3 35换句话说8个角块随机打乱位置原本不相邻的4个角块打乱之后刚好各部相邻的概率是1/352幽灵部件的朝向角块组的奇偶性这是一个mod 2的状态问题。3角块的组内位置这是两个mod 2的状态问题。因为2个组是独立的所以是两个独立的状态恒等式。4幽灵部件的朝向中心块的位置这是一个mod 2的状态问题。5角块的朝向这是两个mod 3的状态问题。6中心块的朝向90度的倍数这是六个mod 2的状态问题。在幽灵部件朝向不动的前提下每个中心块只能旋转180度的倍数。7中心块的朝向180度的倍数这是一个mod 2的状态问题。3四阶魔方1中心块的位置应该是一个mod 2的状态问题。因为是自由原子状态所以不用深究。2中心块的朝向。应该是一个mod 2或者mod 4的状态问题。因为是自由原子状态所以不用深究。PS中心块的位置和朝向指的是4个中心块相对1个中心正方形的相对位置和相对朝向。3棱块的位置这是一个mod 1的状态问题。但是在不打破6个中心正方形的情况下是一个mod 2的状态问题。也就是说单棱翻转一定是通过中心正方形的拆开重组来解决的。PS算这个状态的奇偶性可能直接看成所有的棱块排成的序列但是严谨的讲这一部分其实是棱块相对棱组的位置。4棱块的朝向这是一个mod 2的状态问题。5中心大正方形的朝向角块的位置这是一个mod 2的状态问题。5幽灵部件的朝向中心大正方形的朝向棱组的位置这是一个mod 2的状态问题。所以会有1/2的概率出现“双棱对换”6中心大正方形的位置这是一个mod 1的状态问题。PS 本质上双棱对换就是棱组位置奇偶性有问题解决方案就是直接整个魔方转90度幽灵部件的朝向奇偶性改变中心大正方形的朝向奇偶性不变棱组的位置奇偶性改变问题解决。带来的副作用就是最新大正方形的位置被影响了而中心大正方形的位置是一个mod 1的状态问题可以单独调整。7角块的朝向这是一个mod 3的状态问题。四魔方恒等式同模无环图1状态组合四阶魔方中的中心正方形的位置和中心正方形的朝向是不可分割的所以可以理解成“中心正方形的位置和朝向”就是一个状态。同理四阶魔方中的“中心块的位置和朝向”也是一个状态。我们把这种关系称之为2个原始状态组合成1个原子状态。2状态拆分斜转魔方角块的位置分成3个层级位置奇偶分组、角块组的奇偶性、组内位置我们把这种关系称之为1个原始状态拆分成多个原子状态。定理一状态组合拆分二分图的形态定理。如果有n组部件那就有2n个原始状态把原始形态和原子形态表示成二分图那么每个连通子图要么只有1个原始状态要么只有1个原子状态。3恒等式覆盖我们把所有的2n个原始状态经过组合和拆分之后得到的所有原子状态称之为原子状态全集。定理二恒等式覆盖定理。算上平凡恒等式一个魔方的所有恒等式一定会涵盖到原子状态全集且每个恒等式都恰好涉及2个原子状态。PS不同的恒等式可能会涉及到同一个原子状态。4带权图双属性边每一个魔方恒等式都可以表示成x-yc (mod k)的形式。因为状态的定义是开放式的所以我们也可以说xyc (mod k)即xy是一个mod k的状态问题。这也就意味着在同一个魔方的的不同恒等式中xy1c1和y2z-c2里面的y1和y2并不是完全相同的但是我没有专门区分。基于x-yc (mod k)可以构造一条边连接x和y的边的权重是c边的模是k也就是每条边含有2个属性。PS点x和点y也就是原子状态。5同模定理三同模定理。基于无向图分割也就是并查集算法得到的每一个子图的所有边的模一定是相同的。6无环图构建的并查集其实是差分并查集所以每一条即将构成环的边都是冗余的边。比如三阶魔方我们也可以说棱块的位置角块的位置是mod 2的状态问题但是这条边是冗余的。以上就解释清楚了怎么样根据一个魔方的所有恒等式得到一个同模无环图。7自由状态在上文中我们定义了可交换部件、所有朝向、目标朝向。1如果n个部件互为可交换部件那么这n个部件的相对位置状态就是自由状态。如四阶魔方的中心块2如果一个部件的所有朝向都是目标朝向那么这个部件的朝向状态就是自由状态。如三阶魔方的中心块、四阶魔方的中心块3如果一个原子状态是多个原始状态组合而成那么只要其中有一个是自由状态得到的就是自由原子状态。五魔方的合法概率1连通子集合法概率计算定理四连通子集合法概率定理。假如一个连通子集的所有边都是mod k的去掉其中的自由原子状态还剩n个非自由的原子状态那么把魔方拆开随机重组这一个连通子集对应的原始状态可以同时复原的概率就是(1/k)^nPS斜转魔方角块的组内位置是两个mod 2的状态问题可以理解成这是2个连通子集。2魔方合法概率计算定理五魔方合法概率定理。把魔方拆开随机重组可以复原的概率等于每个连通子集的合法概率之乘积。3常见魔方的合法概率1三阶魔方1/2 * 1/2 * 1/3 1/122斜转魔方1/(35*2*2*2*3*3) 1/25203四阶魔方待更新1 * 1 * 1 * 1/2 * 1 * 1 * 1/3 1/6六解决状态恒等式的三阶段三个阶段代表三种风格迥异的复原方法。阶段一算法在即将产生状态和的时候最后一步合理操作保证状态和正确。阶段二算法在刚刚产生状态和之后立刻校验状态和如果不对直接调整。阶段三算法在最后出现没法继续操作必须调整状态和的时候再调整。显然3种思路对本质的理解是递降的即阶段一算法阶段二算法阶段三算法。但是如果理解了本质那么创造相应公式的难度是递增的即阶段一算法创造公式是最容易的甚至可能不需要任何公式。四阶魔方的层先法一般人学的都是阶段三算法而我在高阶魔方自动复原里面处理单棱翻转问题用的就是阶段二算法。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
