斜转魔方、斜转扭曲魔方

目录斜转魔方1魔方三要素1组成部件2可执行操作3目标态2复原方法1调整8个角块位置2调整6个中心块位置3调整角块方向3中心块位置的奇偶性4状态空间5计算机求解1状态空间大小2最大所需操作数3BFS求解6中心块的朝向7随机拼装的合法概率斜转扭曲魔方1魔方三要素2中心块朝向奇偶性3复原方法1调整8个角块位置2调整6个中心块位置3调整角块方向4调整中心块朝向斜转魔方1魔方三要素1组成部件8个角块和6个中心块把8个角块编号12345678分别对应上层的左上、右上、左下、右下以及下层的。2可执行操作斜转魔方既可以理解成四轴魔方也可以理解成八轴魔方。如果认为是8种操作的话那么可以分成四组任意一组的2个操作各执行1次或2次加起来都相当于魔方整体旋转。按照4种操作理解的话每种操作都会改变3个角块的位置另外5个角块位置不变这4个操作影响的3个角块分别是167、258、358、4673目标态3.1形状任意一次操作之后魔方都是正方体最后也自然是正方体。3.2颜色8个角块可以唯一确定6个面的位置关系。2复原方法1调整8个角块位置先调整4个角块的位置此时可能出现的情况可以用bfs算一下string f1(string s) { char c s[3]; s[3] s[6], s[6] s[5], s[5] c; return s; } string f2(string s) { char c s[2]; s[2] s[4], s[4] s[7], s[7] c; return s; } string f3(string s) { char c s[0]; s[0] s[6], s[6] s[5], s[5] c; return s; } string f4(string s) { char c s[1]; s[1] s[4], s[4] s[7], s[7] c; return s; } void bfs() { string s 12345678; queuestringq; q.push(s); mapstring, intm; m[s] 1; while (!q.empty()) { string str q.front(); q.pop(); string s f1(str); if (!m[s])m[s] 1, q.push(s); s f2(str); if (!m[s])m[s] 1, q.push(s); s f3(str); if (!m[s])m[s] 1, q.push(s); s f4(str); if (!m[s])m[s] 1, q.push(s); } for (auto mi : m) { bool flag true; for (int i 0; i 4; i)if (mi.first[i]4)flagfalse; if(flag)cout mi.first endl; } }输出12345678132486754231576843218765所以只需要上层是1234下层就一定是5678这一步非常简单不需要任何公式。2调整6个中心块位置以8、5、3为轴顺时针各一次8个角块的位置不变左下中心块互换另外4个中心块轮换。为了方便我们把这个叫做853操作。把6个中心块编号为1上2下3前4后5左6右则853操作对中心块的位置影响是123456-451623另外3个操作674、582、761的影响依次是532641、365142、645213于是我们可以就可以推导中心块调整位置的公式string f1(string s) { char c s[2]; s[2] s[5], s[5] c; c s[1]; s[1] s[4], s[4] s[6], s[6] s[3], s[3] c; return s; } string f2(string s) { char c s[2]; s[2] s[3], s[3] c; c s[1]; s[1] s[5], s[5] s[4], s[4] s[6], s[6] c; return s; } string f3(string s) { char c s[2]; s[2] s[6], s[6] c; c s[1]; s[1] s[3], s[3] s[5], s[5] s[4], s[4] c; return s; } string f4(string s) { char c s[2]; s[2] s[4], s[4] c; c s[1]; s[1] s[6], s[6] s[3], s[3] s[5], s[5] c; return s; } void bfs() { string s 123456; queuestringq; q.push(s); mapstring, intm; m[s] 1; while (!q.empty()) { string str q.front(); q.pop(); string s f1(str); if (!m[s])m[s] 1, q.push(s); s f2(str); if (!m[s])m[s] 1, q.push(s); s f3(str); if (!m[s])m[s] 1, q.push(s); s f4(str); if (!m[s])m[s] 1, q.push(s); } for (auto mi : m) { int x 0; for (int i 0; i 7; i)if (mi.first[i]s[i])x; if(x4)cout mi.first endl; } }输出123456123564123645124536124653125346125463126354126435134256135426136452142356143526143652152436153246153462162453163254163425231456243156253416263451312456324156325416326451413256421356423516423651513426521436523146523461613452621453623154623415理论上任选一个都可以作为基础公式模式。为了方便我们选143526作为公式模式。代码略改一下求出123456到143526的变换路径void bfs() { string s 123456; queuestringq; q.push(s); mapstring, intm; mapstring, stringp; mapstring, intp2; m[s] 1; while (!q.empty()) { string str q.front(); q.pop(); string s f1(str); if (!m[s])m[s] 1, q.push(s), p[s] str, p2[s] 1; s f2(str); if (!m[s])m[s] 1, q.push(s), p[s] str, p2[s] 2; s f3(str); if (!m[s])m[s] 1, q.push(s), p[s] str, p2[s] 3; s f4(str); if (!m[s])m[s] 1, q.push(s), p[s] str, p2[s] 4; } s 143526; while (s ! 123456) { cout s p2[s] ; s p[s]; } cout s endl; }输出143526 2 634215 1 415632 3 624351 1 451623 1 123456也就是说从123456依次执行853、853、582、853 、674操作共15次操作即可变成143526即245三个色块的轮换。有此公式即可完成所有中心块的归位。亲测有效会不会出现只有2个面的颜色反过来的情况呢不会首先如果会出现只有2个面的颜色反过来的情况那就一定会出现123456变成123546即012345变成012435且一定是只需要4个操作的组合就可以达成。这一步的推理已经考虑了整个魔方旋转的场景其次用程序枚举int main() { CubeBlock block1(0, 6);//6中心块 vectorCubeBlockb vectorCubeBlock{ block1 }; Opt opt1{ { {3,1,2,4,0,5}} ,左上 }; Opt opt2{ { {3,1,2,5,4,0} } ,右上 }; Opt opt3{ { {2,1,4,3,0,5} } ,左下 }; Opt opt4{ { {2,1,5,3,4,0} } ,右下 }; CubeOpt op1(b, opt1); CubeOpt op2(b, opt2); CubeOpt op3(b, opt3); CubeOpt op4(b, opt4); vectorCubeOptopts { op1,op2,op3,op4 }; for (int i 0; i opts.size(); i)mans[i] opts[i].getName(); Cube cube(b, opts); cube.bfs(0, 1, 2); return 0; }输出k60果然不存在这种场景3调整角块方向把853操作直接重复4遍则所有块位置不变角块中24方向不变其他6个角块都顺时针转一次。我们把它理解成对8个角块顺时针旋转并对24逆时针旋转把这个操作叫做24操作。2个12操作1个24操作我们就得到一个只改变1和4不改变另外6个角块的操作1顺时针旋转4逆时针旋转。有了这个操作显然可以把除了2个相邻角块之外的所有角块方向复原。最后有没有可能只有2个相邻角块方向不对呢应该不可能。至此魔方复原3中心块位置的奇偶性我们会遇到一个状态4个面的中心块的位置都是好的只有2个是反的。那是不是可以理解成任意2个中心块的位置都可以互换呢不能这么简单的理解。比如白色是顶面红色是前面而后面和右面是反的如果顶面白色永远保持不动那么无论怎么操作都不可能6个中心块归位保持白色是上面红色是前面。因为要想六个面的相对位置恢复白色当然还是顶面但前面一定是绿色或者蓝色。“前面是绿色或者蓝色”这样的魔方的整体朝向是不符合标准色的出现这个情况是因为在开始复原之前魔方整体旋转了90度。换句话说以我的这个魔方为例只要复原了顶面白色的“奇艺”两个字就一定不是正对着自己的而是转了90度。4状态空间我们都知道三阶魔方的状态空间大小是8* 3^8 * 12*2^12 / 12 4325亿亿这个挺大的一个数字但即使这样三阶魔方也只需要十几次操作就能复原。同样的对斜转魔方整体旋转的情况进行去重我们只需要按照四轴的方式去理解即可。按照4种操作理解的话每种操作都会改变3个角块的位置另外5个角块位置不变这4个操作影响的3个角块分别是167、258、358、467也就是说一开始上面是白色地面是黄色则上面永远是黄色。6个中心块的情况数是5!/2608个角块的位置的情况数是4*3*4*31448个角块的朝向的情况数是3^6729所以一共60*144*7296298560种情况连一千万都不到。5计算机求解既然状态空间这么小那就可以直接求出任意状态下的最优复原路线。1状态空间大小首先编码求一下状态空间的大小//把6个中心块索引为0上1下 2前3后 4左5右 //上层的左上、右上、左下、右下4个角块索引是6、8、10、12 //下层的左上、右上、左下、右下4个角块索引是14、16、18、20 //每个角块跟着一个朝向复原状态的朝向都是0即白色黄色都在上面和下面朝向表示已经转了几格3格消除 #define TURN1(a,b,c) {int tmp v[a];v[a] v[b], v[b] v[c], v[c] tmp; } //3个块位置轮换 #define TURN2(a) {v[a1](v[a1]1)%3;} //1个角块旋转 #define TURN3(a,b,c) {TURN1(a,b,c);TURN1(a1,b1,c1);TURN2(a);TURN2(b);TURN2(c);TURN2(a);TURN2(b);TURN2(c);} //3个角块位置轮换朝向改变 //以下是4个顺时针旋转操作 vectorint f1(vectorintinput) { vectorint v input; TURN1(2, 1, 5); TURN2(20); TURN3(12, 18, 16); return v; } vectorint f2(vectorintinput) { vectorint v input; TURN1(2, 4, 1); TURN2(18); TURN3(10, 14, 20); return v; } vectorint f3(vectorintinput) { vectorint v input; TURN1(4, 3, 1); TURN2(14); TURN3(6, 16, 18); return v; } vectorint f4(vectorintinput) { vectorint v input; TURN1(5,1,3); TURN2(16); TURN3(8, 20, 14); return v; } vectorstd::functionvectorint(vectorint) vf{ f1,f2,f3,f4 }; void bfs() { vectorintv{ 1,2,3,4,5,6,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0 }; queuevectorintq; q.push(v); setvectorints; s.insert(v); while (!q.empty()) { auto v q.front(); q.pop(); for (auto f : vf) { auto v2 f(v); if (s.find(v2) s.end()) { q.push(v2); s.insert(v2); //if (s.size() % 100000 0)cout q.size() s.size() endl; } } } cout s.size(); } int main() { bfs(); return 0; }输出62985602最大所需操作数把集合set改造成映射表map即可//把6个中心块索引为0上1下 2前3后 4左5右 //上层的左上、右上、左下、右下4个角块索引是6、8、10、12 //下层的左上、右上、左下、右下4个角块索引是14、16、18、20 //每个角块跟着一个朝向复原状态的朝向都是0即白色黄色都在上面和下面朝向表示已经转了几格3格消除 #define TURN1(a,b,c) {int tmp v[a];v[a] v[b], v[b] v[c], v[c] tmp; } //3个块位置轮换 #define TURN2(a) {v[a1](v[a1]1)%3;} //1个角块旋转 #define TURN3(a,b,c) {TURN1(a,b,c);TURN1(a1,b1,c1);TURN2(a);TURN2(b);TURN2(c);TURN2(a);TURN2(b);TURN2(c);} //3个角块位置轮换朝向改变 //以下是4个顺时针旋转操作 vectorint f1(vectorintinput) { vectorint v input; TURN1(2, 1, 5); TURN2(20); TURN3(12, 18, 16); return v; } vectorint f2(vectorintinput) { vectorint v input; TURN1(2, 4, 1); TURN2(18); TURN3(10, 14, 20); return v; } vectorint f3(vectorintinput) { vectorint v input; TURN1(4, 3, 1); TURN2(14); TURN3(6, 16, 18); return v; } vectorint f4(vectorintinput) { vectorint v input; TURN1(5,1,3); TURN2(16); TURN3(8, 20, 14); return v; } vectorstd::functionvectorint(vectorint) vf{ f1,f2,f3,f4 }; void bfs() { vectorintv{ 1,2,3,4,5,6,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0 }; queuevectorintq; q.push(v); mapvectorint,ints; s[v] 0; while (!q.empty()) { auto v q.front(); q.pop(); for (auto f : vf) { auto v2 f(v); if (s.find(v2) s.end()) { q.push(v2); s[v2] s[v]1; if (s.size() % 100000 0)cout q.size() s.size() endl; if (s.size() 6298558)cout s[v2] endl; } } } cout s.size(); } int main() { bfs(); return 0; }输出16也就是说任意状态最多需要16步就可以复原。3BFS求解//把6个中心块索引为0上1下 2前3后 4左5右 //上层的左上、右上、左下、右下4个角块索引是6、8、10、12 //下层的左上、右上、左下、右下4个角块索引是14、16、18、20 //每个角块跟着一个朝向复原状态的朝向都是0即白色黄色都在上面和下面朝向表示已经顺时针转了几格3格消除 #define TURN1(a,b,c) {int tmp v[a];v[a] v[b], v[b] v[c], v[c] tmp; } //3个块位置轮换 #define TURN2(a) {v[a1](v[a1]1)%3;} //1个角块旋转 #define TURN3(a,b,c) {TURN1(a,b,c);TURN1(a1,b1,c1);TURN2(a);TURN2(b);TURN2(c);TURN2(a);TURN2(b);TURN2(c);} //3个角块位置轮换朝向改变 //以下是4个顺时针旋转操作 vectorint f1(vectorint input) { vectorint v input; TURN1(2, 1, 5); TURN2(20); TURN3(12, 18, 16); return v; } vectorint f2(vectorint input) { vectorint v input; TURN1(2, 4, 1); TURN2(18); TURN3(10, 14, 20); return v; } vectorint f3(vectorint input) { vectorint v input; TURN1(4, 3, 1); TURN2(14); TURN3(6, 16, 18); return v; } vectorint f4(vectorint input) { vectorint v input; TURN1(5, 1, 3); TURN2(16); TURN3(8, 20, 14); return v; } vectorstd::functionvectorint(vectorint) vf{ f1,f2,f3,f4 }; void bfs(vectorinttarget) { vectorintv{ 1,2,3,4,5,6,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0 }; queuevectorintq; q.push(v); mapvectorint, ints; s[v] 0; mapvectorint, vectorintfa; mapvectorint, intfaOpt; faOpt[v] -1; while (!q.empty()) { auto v q.front(); q.pop(); for (int i 0; i 4;i) { auto v2 vf[i](v); if (s.find(v2) s.end()) { q.push(v2); s[v2] s[v] 1; //if (s.size() % 100000 0)cout q.size() s.size() endl; fa[v2] v; faOpt[v2] i; if (v2 target) { vectorstring strs{ 右下,左下,左上,右上 }; int lineId 0; while (faOpt[v2] 0) { cout lineId 以底层的 strs[faOpt[v2]] 的大角块为轴逆时针旋转 endl; v2 fa[v2]; } return; } } } } cout s.size(); } //以下是4个顺时针旋转操作 vectorint f5(vectorint input) { vectorint v input; TURN1(2, 1, 5); return v; } vectorint f6(vectorint input) { vectorint v input; TURN1(2, 4, 1); return v; } vectorint f7(vectorint input) { vectorint v input; TURN1(4, 3, 1); return v; } vectorint f8(vectorint input) { vectorint v input; TURN1(5, 1, 3); return v; } vectorstd::functionvectorint(vectorint) vf2{ f5,f6,f7,f8 }; //奇偶性检查即魔方整体要不要旋转90度 bool checkNeedTurn(vectorint target) { vectorintv{ 1,2,3,4,5,6}; queuevectorintq; q.push(v); mapvectorint, ints; s[v] 0; while (!q.empty()) { auto v q.front(); q.pop(); for (int i 0; i 4; i) { auto v2 vf2[i](v); if (s.find(v2) s.end()) { q.push(v2); s[v2] s[v] 1; } } } if (s.find(target) ! s.end()) { return false; } //篡改数据把魔方整体往左旋转90度,保持白色放在顶面,也就是前面转到左边左边转到后面 int tmp target[2]; target[2] target[5], target[5] target[3]; target[3] target[4], target[4] tmp; return true; } int main() { vectorintv{ 1,2,3,4,5,6}; cout 分别输入白色 黄色 红色 橙色 绿色 蓝色中心块的位置用数字表示0上1下 2前3后 4左5右 endl; int id, t; for (int i 1; i 6; i) { cin id; v[id] i; } if (v[0] ! 1) { cout 把白色放在顶面重新运行程序; return 0; } if (checkNeedTurn(v)) { cout 把魔方整体往左旋转90度,保持白色放在顶面,也就是前面转到左边左边转到后面然后继续 endl; } for (int i 1; i 16; i) { v.push_back(0); } cout 分别输入 白绿橙 白蓝橙 白绿红 白蓝红 黄绿橙 黄蓝橙 黄绿红 黄蓝红 8个大角块的位置和朝向 endl; cout 位置用数字表示上层的左上、右上、左下、右下分别是6、8、10、12下层的左上、右上、左下、右下分别是14、16、18、20 endl; cout 每个角块位置输入完立刻输入朝向朝向表示已经顺时针转了几格3格消除0表示白色黄色都在上面和下面 endl; for (int i 1; i 8; i) { cin id t; v[id] i; v[id 1] t; } bfs(v); return 0; }运行示例亲测有效6中心块的朝向基于复原的魔方标准中心块的朝向白色和黄色面的箭头指向红色面另外4面的箭头指向白色面。首先复原状态下每个中心块只能旋转180度的倍数不能旋转90度这个是确定的。其次稍微探索一下就得到只有白色和蓝色面旋转180度其他面方向不变。所以可以推测出应该是每个中心块旋转180的倍数之和一定是偶数。7随机拼装的合法概率6个中心块和7个角块随机拼装能复原的概率是多少呢1计算总状态数中心块位置是6!720角块位置是8!40320角块朝向是3^86561所以一共是720*40320*65611904684544002计算合法状态数前面算过也算法验证过合法状态数是6298560但是这个前提是顶层白色面保持不动整个魔方的朝向也不整体旋转。所以实际的合法状态数是6298560 * 6 * 2 755827203随机拼装的合法概率75582720 / 190468454400 1/2520斜转扭曲魔方1魔方三要素和斜转魔方唯一的区别就是有4个中心块蓝绿红橙是扭曲的也就是要区分朝向了。2中心块朝向奇偶性我们把中心块旋转0度和180度叫偶状态旋转90度和270度叫奇状态。根据若干次尝试我提出1个定理和1个猜想1定理如果6个中心块的位置复原无论角块的位置和朝向6个中心块一定都是偶状态。用斜转魔方证明这个定理可能还不容易想出来但是用斜转扭曲魔方证明就很容易了。扭曲中心块是双色的分界线是一条线段延长之后刚好经过正方体的2个顶点。对顶点进行2染色即可推导出中心块朝向的奇偶性。2猜想如果位置没有完全复原但是满足对立色即6个中心块的位置是整个魔方成镜面无论角块的位置和朝向6个中心块一定都是奇状态。这个猜想应该是对的但是这里我不做证明。基于1斜转扭曲魔方相对于斜转魔方唯一需要多做的事情就是4个扭曲中心块中的若干个需要旋转180度。3复原方法1调整8个角块位置同斜转魔方2调整6个中心块位置同斜转魔方3调整角块方向同斜转魔方因为4个扭曲中心块都是偶状态所以形态是没问题的只有颜色可能对不上。4调整中心块朝向上文有提到24操作即把853操作直接重复4遍则所有块位置不变角块中24方向不变其他6个角块都顺时针转一次。我们定义一个242424操作即853操作重复12遍效果是所有块位置不变所有角块朝向不变25号中心块朝向不变1346号中心块朝向旋转180度。根据扭曲中心块需要调整朝向的数量分为0 1 2 3 4这5种情况4-1-2-3-0之间的转化都刚好是1个242424操作。至此魔方复原