目录一操作序列重建问题 Q1二置换操作序列重建问题 Q1.21操作簇2问题簇3三元轮换公式的充分性定理三错位数四拼接旋转操作序列重建问题簇 {(Q1.2.1, L)}1 {(Q1.2.1, L)}2定理一化简定理3定理二公式充分性定理4t35t46定理三3To2公式构造定理7t58定理四4To3公式构造定理9t610t7、任意t五旋转操作序列重建问题簇 {(Q1.2.2,......)}1双圈交换问题 Q1.2.2.11单块移动问题 Q1.2.2.1.2.12双块移动问题 Q1.2.2.1.2.23三块移动问题 Q1.2.2.1.2.32三圈交换问题六纯色块拼图问题簇 {(Q1.2.3,...)}七魔轮问题 Q1.2.4八置换操作序列近似重建问题Q2九魔轮问题簇{(Q2.1,...)}一操作序列重建问题 Q1Q1给定一个有限长度的自然数数组A给定有限数量的若干个操作opt_1,opt_2,...,opt_n每个操作都是确定的映射即自然数数组到另一个等长的自然数数组的映射随机生成一个任意长度的操作序列{a,b,c,......,k},得到Bopt_a(opt_b(opt_c(......opt_k(A)......)))寻找一个有效且高效的算法只根据A、B和opt_1,opt_2,...,opt_n算出一个任意长度的操作序列{u,v...z}使得Bopt_u(opt_v(......opt_z(A)......))Q1的2个常见实例Q1.1和Q1.2这个命名就表达了泛化关系下文不再赘述。Q1.1自然数数组是一个二维01矩阵操作是特定格子0变成1,1变成0这样就得到了各种的黑白迭代二置换操作序列重建问题 Q1.2Q1.2Q1中操作限定为置换操作。PS实际上绝大部分魔方都可以表示成Q1.2的一种少数魔方可以表示成Q2的一种。1操作簇带唯一参的置换操作簇给定一个操作簇f序列长度-置换操作集输入序列长度L即可输出一个确定的有限个置换操作组成的操作集f(L)因为这个操作簇只有唯一的参数L所以我称之为带唯一参的置换操作簇。PS一般来说这个操作簇是有解析定义且是遗忘操作才比较有研究意义下文的 “拼接旋转操作序列重建问题簇{(Q1.2.1, L)}” 和 “旋转操作序列重建问题簇 {(Q1.2.2,......)}” 都符合这个特点。2问题簇带唯一参的置换操作序列重建问题簇{(Q1.2, L)}对于每个L关于带唯一参的置换操作簇中的操作集f(L)都有一个置换操作序列重建问题我们不仅要找到L2,3,4,5...时的操作序列重建算法还要探索有没有一个带参数L的算法可以解决整个问题簇。带多个参数的置换操作序列重建问题簇{(Q1.2, ...)}至少有2个参数3三元轮换公式的充分性定理对于Q1.2如果找到一个系列公式使得任意连续3个成员之间都可以进行三元轮换那么只需要若干次的三元轮换和至多一次原始置换操作即可把任意打乱序列还原。证明首先很容易把除了2个成员之外的所有成员归位其次再根据逆序数的奇偶性即可证明。三错位数任意一个自然数序列里面的每个数各不相同经过任意方式的打乱顺序之后和原序列对比相同位置不同自然数的数量就是错位数。一般魔方的公式都追求错位数是2或者3。四拼接旋转操作序列重建问题簇 {(Q1.2.1, L)}1 {(Q1.2.1, L)}基于问题簇{(Q1.2, L)}限定L是24的倍数即使L24t把序列A分成24段限定操作簇是包括且仅包括对于任意的2段提取出来拼接得到一个长为2t的数组把数组的第一个数挪到数组最后即数组旋转一位再重新拆分成2个长为t的段放回原位从而形成完整的置换。具体来说混元魔方 复原所有半圆盘的问题抛开一点点微不足道的细节得到的就是拼接旋转操作序列重建问题簇的弱化版比如混元三号就是(Q1.2.1, L72)的弱化版。其中的弱化指的是每个面的4个半圆盘是同色的比如L72的序列其实是1到18各出现了4次的序列。2定理一化简定理定理一对于 {(Q1.2.1, L)}L24t对于任意的t一定存在一个操作序列使得所有置换执行之后得到的序列的前22段都和原始序列A相同。证明方法也很简单随便搞一个构造解就行了。于是接下来只需要考虑对于只有最后2段被打乱的序列如何重建操作序列。3定理二公式充分性定理定理二对于 {(Q1.2.1, L)}如果找到了一个操作序列使得错位数是2那么L个数的全排列中的任何一种都是合法状态且对于任何一种排列都只需要合理使用已经找到的这个公式即可变成复原排列。证明方法也很简单随便搞一个构造解就行了。PS定理二只适用于Q1.2.1而不能适用于Q1.2也就是说实际上每一类魔方都需要单独的论证。4t3其实混元魔方t号就是在混元魔方一号的基础上再加一个拼接旋转操作序列重建问题 (Q1.2.1, L)L24t对于t3在混元三号中已经找到了错位数是2的公式。我们把代码做一个泛化int main() { int N 3; CubeBlock block1(N*3); b vectorCubeBlock{ block1 }; vectorintv1, v2; for (int i 1; i N * 2; i)v1.push_back(i); v1.push_back(0); for (int i N*2; i N * 3; i)v1.push_back(i); Opt opt1{ {v1},a }; for (int i 1; i N ; i)v2.push_back(i); v2.push_back(N*2); for (int i N ; i N * 2; i)v2.push_back(i); for (int i N * 21; i N * 3; i)v2.push_back(i); v2.push_back(0); Opt opt2{ {v2 }, b }; vectorCubeOptopts { opt1,opt2 }; for (int i 0; i opts.size(); i)mans[i] opts[i].getName(); Cube cube(opts); cube.bfs(0, 2, 2); return 0; }输出5,1,2,3,4,0,6,7,8,0a 0a 0a 1b 0a 1b 1b 0a 1b 1b 0a 0a 1b 1b 0a 1b 1b 0a 1b这样这个代码只需要改N的值所有代码都不需要改了。5t40,1,2,3,4,5,6,11,8,9,10,7,0a 0a 1b 0a 0a 0a 1b 0a 0a 0a 1b 0a 0a 0a 1b 0a 0a 1b 0a6定理三3To2公式构造定理定理三对于 {(Q1.2.1, L)}L24t如果找到了一个操作序列使得效果是相邻3个数轮换那么就可以构造出一个错位数是2的操作序列。证明方法也很简单随便搞一个构造解就行了。以t5为例1 2 3 4 5 6 7 8 9 10 五次置换6 7 8 9 10 1 2 3 4 5 四次三元轮换6往后跳4次7 8 9 10 1 2 3 4 6 5 四次置换1 2 3 4 6 5 7 8 9 107t5直接搜错位数很低的公式有点难用上我惯用的技巧先搜cube.bfs(0, 2, 5)得到2个公式0,10,2,3,4,5,7,6,8,9,1,11,12,13,14,0a 0a 0a 0a 0a 0a 1b 0a 1b 1b 1b 1b 1b 1b 1b 1b 1b 0a 0a 0a10,1,2,3,4,6,5,7,8,9,0,11,12,13,14,0a 0a 0a 0a 0a 1b 0a 1b 1b 1b 1b 1b 1b 1b 1b 1b 0a 0a 0a 0a组合int main() { CubeBlock block1(20); b vectorCubeBlock{ block1 }; Opt opt1{ {{1,2,3,4,5, 6,7,8,9,0, 10,11,12,13,14, 15,16,17,18,19}},a }; Opt opt2{ {{1,2,3,4,10, 5,6,7,8,9, 11,12,13,14,0, 15,16,17,18,19} }, b }; Opt opt3{ {{0,1,2,3,4, 6,7,8,9,15, 10,11,12,13,14, 16,17,18,19,5} }, c }; auto opt4 Splice({ opt1,opt2 }, { 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0 }); auto opt5 Splice({ opt1,opt2 }, { 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0 }); auto opt6 opt4 opt3 opt5 opt3 opt3 opt3 opt3 opt3 opt3 opt3 opt3 opt3; opt6.show(); return 0; }输出1,10,2,3,4,5,6,7,8,9,0,11,12,13,14,15,16,17,18,19,操作名aaaaaababbbbbbbbbaaacaaaaababbbbbbbbbaaaaccccccccc这就得到了0 1 10三个部件轮换的公式了。这就等价于相邻3个部件轮换的公式。根据定理二和定理三这个公式就达到了攻略混元五号魔方的标准了。8定理四4To3公式构造定理定理四对于 {(Q1.2.1, L)}L24t如果找到了一个操作序列其中每个操作都只涉及前22段不涉及最后2段且前22段中存在不同的3段x,y,z使得这个操作序列的效果是x段中的2个部件互换y段中的一个部件和z段中的一个部件互换其他22t-4个部件位置不变那么根据这个四元变换公式即可组合成相邻3个部件轮换的公式。证明方法也很简单随便搞一个构造解就行了只需要执行2次这个操作序列x段的互换就抵消掉了。9t60,1,2,3,5,4, 6,7,8,9,10,17, 12,13,14,15,16,11,0a 0a 1b 1b 0a 1b 0a 0a 1b 1b 0a 1b 0a 0a 1b 1b 1b 0a运用定理四即可。10t7、任意t0,2,1,3,4,5,6, 7,14,9,10,11,12,13, 8,15,16,17,18,19,20,0a 1b 0a 1b 1b 1b 1b 1b 1b 1b 1b 1b 1b 1b 1b 1b 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a 0a运用定理四即可。至此我们就得到了一个关键公式a b a b a a不难证明这个公式是通用的。基于此我们就得到了拼接旋转操作序列重建问题簇 {(Q1.2.1, L)}的通用解了。更详细的构造解参考混元四号 - 两百号五旋转操作序列重建问题簇 {(Q1.2.2,......)}纸面魔方 就是Q1.2.2问题簇而且是多个参数的不是唯一参的。1双圈交换问题 Q1.2.2.1普通版是数字版Q1.2.2.1.1简化版是纯色块版Q1.2.2.1.2。1单块移动问题 Q1.2.2.1.2.1按照这样去编号那这就是一个长为2ab的序列的旋转操作序列重建问题。操作序列包含4个操作前a个旋转、前ab个旋转、后a个旋转、后ab个旋转其中所有旋转都是旋转c位而不是1位。puzzle中的是否旋转对应的是2种编号顺序问题的本质不变。除了是否旋转还有a b c三个参数puzzle中把b和c列为了可选参数a是系统自动给定的。2双块移动问题 Q1.2.2.1.2.2和单块移动问题 Q1.2.2.1.2.1类似这里是6种置换组成的操作序列。3三块移动问题 Q1.2.2.1.2.3和单块移动问题 Q1.2.2.1.2.1类似这里是另外4种置换组成的操作序列。2三圈交换问题六纯色块拼图问题簇 {(Q1.2.3,...)}色块拼图 这一类的问题也属于置换操作序列重建问题。七魔轮问题 Q1.2.4参考魔轮八置换操作序列近似重建问题Q2Q2给定一个有限长度的自然数数组A给定SA属于SS是具有对称性的一类数组的集合给定有限数量的若干个操作opt_1,opt_2,...,opt_n每个操作都是确定的映射即自然数数组到另一个等长的自然数数组的映射随机生成一个任意长度的操作序列{a,b,c,......,k},得到Bopt_a(opt_b(opt_c(......opt_k(A)......)))寻找一个有效且高效的算法只根据B、S和opt_1,opt_2,...,opt_n算出一个任意长度的操作序列{u,v...z}使得opt_u(opt_v(......opt_z(B)......))属于S九魔轮问题簇{(Q2.1,...)}魔轮属于置换操作序列近似重建问题因为每2列之间都可以随意交换目标态不唯一。