異形魔方的算法。by @沉默de世界

這個是暴力破解，打亂試了幾次，一種用了7步還原，一種用了6步還原，估計大部分狀態10步以內可以還原，超過10步計算就比較費時了。

說明如圖：（1）編號如圖所示，上層12345678 下層11,12,13,14,15,16,17,18 。 （2）R1動作為線前側（圖中5,6,7,8,14,15,16,17位置）旋轉180度，R2為線前側（7,6,5,4,18,17,16,15位置）旋轉，R3為線右側（3,4,5,6,12,13,14,15位置）旋轉，R4為線右側（5,4,3,2,16,15,14,13）旋轉。 （3）R5、R6、R7、R8分別對應上層順時針旋轉90度后執行R1、R2、R3、R4。 （4）R9、R10、R11、R12分別對應上層順時針旋轉180度后執行R1、R2、R3、R4。 （5）R13、R14、R15、R16分別對應上層順時針旋轉270度后執行R1、R2、R3、R4。 （6）打亂狀態starta，startb分別為上下兩層、從左上角開始、按順時針順序的塊編號,改程序中初始值即可。在以上轉動過程中編號11的塊位置是始終保持不變的。 ? //written by @沉默de世界 #include "stdafx.h" #include "stdio.h"#define DEEP_MAX 20 //70*6 * 70*6 *4 * 6*6*4 typedef struct _CUBE_STATUS{int a[8];int b[8]; }CUBE_STATUS; CUBE_STATUS cb0,cb1,cb; int succflag=0; int act[DEEP_MAX]={0}; int deep_i=-1; int deep_max=-1; int deep_reuslt=0;void cpy(CUBE_STATUS *p1, CUBE_STATUS *p0); void pntcb(CUBE_STATUS *p); void Rot(CUBE_STATUS *p); void Rn(CUBE_STATUS *p,int n); int IsSame(CUBE_STATUS *p1,CUBE_STATUS *p2);int main(int argc, char* argv[]) {// int starta[8]={3,4,5,6,17,16,15,14}; // int startb[8]={11,12,13,2,1,8,7,18};// int starta[8]={1,2,3,4,5,16,7,8}; // int startb[8]={11,12,13,14,17,6,15,18};int starta[8]={5,14,3,16, 15,6,7,8};int startb[8]={11,12,13,2, 1,4,17,18};int i=0;for (i=0;i<8;i++){cb0.a[i]=i+1;//目標狀態cb0.b[i]=i+11; cb1.a[i]=starta[i];//初始狀態cb1.b[i]=startb[i];cb.a[i]=starta[i];cb.b[i]=startb[i];}printf("start...\n");if(IsSame(&cb,&cb0))succflag=1;else{for (deep_i=0,deep_max=1;deep_max<=DEEP_MAX;deep_max++){printf("\nMAXDEEP: %d \n",deep_max);Rot(&cb);if(succflag==1)break;}}if(succflag==1){printf("\nSucceed! It need %d steppes. \n",deep_reuslt);printf("start:");pntcb(&cb1);for (i=0;i<deep_reuslt;i++){Rn(&cb1,act[i]);printf("R%-2d-> ",act[i]); pntcb(&cb1);}}elseprintf("failed!\n");return 0; }void Rot(CUBE_STATUS *p) {int i;if(deep_i>=deep_max) return;for (i=1;i<=16;i++){CUBE_STATUS tmp;if( deep_i>0 ){if ( ( i==1 && (act[deep_i-1]==1 || act[deep_i-1]==5 || act[deep_i-1]==9 || act[deep_i-1]==13) )|| ( i==2 && (act[deep_i-1]==2 || act[deep_i-1]==6 || act[deep_i-1]==10 || act[deep_i-1]==14) )|| ( i==3 && (act[deep_i-1]==3 || act[deep_i-1]==7 || act[deep_i-1]==11 || act[deep_i-1]==15) ) || ( i==4 && (act[deep_i-1]==4 || act[deep_i-1]==8 || act[deep_i-1]==12 || act[deep_i-1]==16) ))continue;}cpy(&tmp,p); Rn(&tmp,i);act[deep_i]=i;if(IsSame(&tmp,&cb0)) {succflag=1;deep_reuslt=deep_i+1;return;}else{deep_i++;Rot(&tmp);deep_i--;if(succflag==1){ return;}}}}int IsSame(CUBE_STATUS *p1,CUBE_STATUS *p2) {if( (p1->b[0]==p2->b[0] && p1->b[1]==p2->b[1] &&p1->b[2]==p2->b[2] && p1->b[3]==p2->b[3] &&p1->b[4]==p2->b[4] && p1->b[5]==p2->b[5] &&p1->b[6]==p2->b[6] && p1->b[7]==p2->b[7] ) && ( (p1->a[0]==p2->a[0] && p1->a[1]==p2->a[1] &&p1->a[2]==p2->a[2] && p1->a[3]==p2->a[3] &&p1->a[4]==p2->a[4] && p1->a[5]==p2->a[5] &&p1->a[6]==p2->a[6] && p1->a[7]==p2->a[7]) ||(p1->a[0]==p2->a[2] && p1->a[1]==p2->a[3] &&p1->a[2]==p2->a[4] && p1->a[3]==p2->a[5] &&p1->a[4]==p2->a[6] && p1->a[5]==p2->a[7] &&p1->a[6]==p2->a[0] && p1->a[7]==p2->a[1]) ||(p1->a[0]==p2->a[4] && p1->a[1]==p2->a[5] &&p1->a[2]==p2->a[6] && p1->a[3]==p2->a[7] &&p1->a[4]==p2->a[0] && p1->a[5]==p2->a[1] &&p1->a[6]==p2->a[2] && p1->a[7]==p2->a[3]) ||(p1->a[0]==p2->a[6] && p1->a[1]==p2->a[7] &&p1->a[2]==p2->a[0] && p1->a[3]==p2->a[1] &&p1->a[4]==p2->a[2] && p1->a[5]==p2->a[3] &&p1->a[6]==p2->a[4] && p1->a[7]==p2->a[5]) )) return 1; elsereturn 0; }void R90(CUBE_STATUS *p) {int t0=0,t1=0;t0=p->a[0];t1=p->a[1];p->a[0]=p->a[6];p->a[1]=p->a[7];p->a[6]=p->a[4];p->a[7]=p->a[5];p->a[4]=p->a[2];p->a[5]=p->a[3];p->a[2]=t0;p->a[3]=t1;}void R180(CUBE_STATUS *p) {int t0=0,t1=0,t2=0,t3=0;t0=p->a[0];t1=p->a[1];t2=p->a[2];t3=p->a[3];p->a[0]=p->a[4];p->a[1]=p->a[5];p->a[2]=p->a[6];p->a[3]=p->a[7];p->a[4]=t0;p->a[5]=t1;p->a[6]=t2;p->a[7]=t3;}void R270(CUBE_STATUS *p) {int t0=0,t1=0;t0=p->a[0];t1=p->a[1];p->a[0]=p->a[2];p->a[1]=p->a[3];p->a[2]=p->a[4];p->a[3]=p->a[5];p->a[4]=p->a[6];p->a[5]=p->a[7];p->a[6]=t0;p->a[7]=t1;}void R1(CUBE_STATUS *p) {int ta7,ta6,ta5,ta4;ta7=p->a[7];ta6=p->a[6];ta5=p->a[5];ta4=p->a[4];p->a[7]=p->b[3];p->a[6]=p->b[4];p->a[5]=p->b[5];p->a[4]=p->b[6];p->b[3]=ta7;p->b[4]=ta6;p->b[5]=ta5;p->b[6]=ta4; }void R2(CUBE_STATUS *p) {int ta6,ta5,ta4,ta3;ta6=p->a[6];ta5=p->a[5];ta4=p->a[4];ta3=p->a[3];p->a[6]=p->b[4];p->a[5]=p->b[5];p->a[4]=p->b[6];p->a[3]=p->b[7];p->b[4]=ta6;p->b[5]=ta5;p->b[6]=ta4;p->b[7]=ta3; }void R3(CUBE_STATUS *p) {int ta2,ta5,ta4,ta3;ta5=p->a[5];ta4=p->a[4];ta3=p->a[3];ta2=p->a[2];p->a[5]=p->b[1];p->a[4]=p->b[2];p->a[3]=p->b[3];p->a[2]=p->b[4];p->b[1]=ta5;p->b[2]=ta4;p->b[3]=ta3;p->b[4]=ta2; }void R4(CUBE_STATUS *p) {int ta2,ta1,ta4,ta3;ta1=p->a[1];ta4=p->a[4];ta3=p->a[3];ta2=p->a[2];p->a[4]=p->b[2];p->a[3]=p->b[3];p->a[2]=p->b[4];p->a[1]=p->b[5];p->b[2]=ta4;p->b[3]=ta3;p->b[4]=ta2;p->b[5]=ta1; }void Rn(CUBE_STATUS *p,int n) {switch(n){//case 0: R0(p);break;case 1: R1(p);break;case 2: R2(p);break;case 3: R3(p);break;case 4: R4(p);break;case 5: R90(p);R1(p);break;case 6: R90(p);R2(p);break;case 7: R90(p);R3(p);break;case 8: R90(p);R4(p);break; case 9: R180(p);R1(p);break;case 10: R180(p);R2(p);break;case 11: R180(p);R3(p);break;case 12: R180(p);R4(p);break; case 13: R270(p);R1(p);break;case 14: R270(p);R2(p);break;case 15: R270(p);R3(p);break;case 16: R270(p);R4(p);break;default: ;} }void cpy(CUBE_STATUS *p1, CUBE_STATUS *p0) {for (int i=0;i<8;i++){p1->a[i]=p0->a[i];p1->b[i]=p0->b[i];} }void pntcb(CUBE_STATUS *p) {for (int j=0;j<8;j++){printf("%d, ",p->a[j]);}printf(" ");for (j=0;j<8;j++){printf("%d, ",p->b[j]);}printf("\n"); }

轉載于:https://www.cnblogs.com/Silence/archive/2011/08/20/2147556.html

總結

以上是生活随笔為你收集整理的异形魔方SQ1的暴力解法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。