魔方
为了写出一个Python版的二阶段算法求解魔方。
今天开始学cpp（蜜汁需求得到的蜜汁结果）。
就酱紫。
随时更新。
使用魔方中心块的相对位置来表示魔方块。例如一个已复原的魔方的表示为：UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
解魔方算法的Cpp表达
1 #include <iostream>
2 #include <string>
3
4 using namespace std ;
5 char
6
7 *faces="RLFBUD",
8
9 *order="AECGBFDHIJKLMSNTROQP",
10
11 *bithash="TdXhQaRbEFIJUZfijeYV",
12
13 *perm="AIBJTMROCLDKSNQPEKFIMSPRGJHLNTOQAGCEMTNSBFDHORPQ",
14
15 pos[20],ori[20],val[20],
16
17 TEMP,
18
19 *tables[8];
20
21 int movecube[20],moveamount[20],
22
23 phase=0,
24
25 tablesize[]={1,4096, 6561,4096, 256,1536, 13824,576};
26
27 #define SWAP(a,b) TEMP=a;a=b;b=TEMP;
28
29 #define CHAROFFSET 65
30
31 static string answer = "";
32
33 void cycle(char*p,char*a)
34 {
35 SWAP(p[*a-CHAROFFSET],p[a[1]-CHAROFFSET]);
36 SWAP(p[*a-CHAROFFSET],p[a[2]-CHAROFFSET]);
37 SWAP(p[*a-CHAROFFSET],p[a[3]-CHAROFFSET]);
38 }
39
40 void twist(int i,int a)
41 {
42 i-=CHAROFFSET;
43 ori[i]=(ori[i]+a+1)%val[i];
44 }
45
46 void reset()
47 {
48 for( int i=0; i<20; pos[i]=i, ori[i++]=0);
49 }
50
51 int permtonum(char* p)
52 {
53 int n=0;
54 for ( int a=0; a<4; a++)
55 {
56
57 n*=4-a;
58 for( int b=a; ++b<4; )
59 if (p<p[a]) n++;
60 }
61 return n;
62 }
63
64 void numtoperm(char* p,int n,int o)
65 {
66 p+=o;
67 p[3]=o;
68 for (int a=3; a--;)
69 {
70 p[a] = n%(4-a) +o;
71 n/=4-a;
72 for (int b=a; ++b<4; )
73 if ( p >= p[a]) p++;
74 }
75 }
76
77 int getposition(int t)
78 {
79 int i=-1,n=0;
80 switch(t)
81 {
82 case 1:
83 for(;++i<12;) n+= ori[i]<<i;
84 break;
85 case 2:
86 for(i=20;--i>11;) n=n*3+ori[i];
87 break;
88 case 3:
89 for(;++i<12;) n+= (pos[i]&8)?(1<<i):0;
90 break;
91 case 4:
92 for(;++i<8;) n+= (pos[i]&4)?(1<<i):0;
93 break;
94 case 5:
95 int corn[8],j,k,l,corn2[4];
96 k=j=0;
97 for(;++i<8;)
98 if((l=pos[i+12]-12)&4)
99 {
100 corn[l]=k++;
101 n+=1<<i;
102 }else corn[j++]=l;
103 for(i=0;i<4;i++) corn2[i]=corn[4+corn[i]];
104 for(;--i;) corn2[i]^=corn2[0];
105 n=n*6+corn2[1]*2-2;
106 if(corn2[3]<corn2[2])n++;
107 break;
108 case 6:
109 n=permtonum(pos)*576+permtonum(pos+4)*24+permtonum(pos+12);
110 break;
111 case 7:
112 n=permtonum(pos+8)*24+permtonum(pos+16);
113 break;
114 }
115 return n;
116 }
117
118 void setposition(int t, int n)
119 {
120 int i=0,j=12,k=0;
121 char *corn="QRSTQRTSQSRTQTRSQSTRQTSR";
122 reset();
123 switch(t){
124
125 case 1:
126 for(;i<12;i++,n>>=1) ori[i]=n&1;
127 break;
128 case 2:
129 for(i=12;i<20;i++,n/=3) ori[i]=n%3;
130 break;
131 case 3:
132 for(;i<12;i++,n>>=1) pos[i]= 8*n&8;
133 break;
134 case 4:
135 for(;i<8;i++,n>>=1) pos[i]= 4*n&4;
136 break;
137 case 5:
138 corn+=n%6*4;
139 n/=6;
140 for(;i<8;i++,n>>=1)
141 pos[i+12]= n&1 ? corn[k++]-CHAROFFSET : j++;
142 break;
143 case 6:
144 numtoperm(pos,n%24,12);n/=24;
145 numtoperm(pos,n%24,4); n/=24;
146 numtoperm(pos,n ,0);
147 break;
148 case 7:
149 numtoperm(pos,n/24,8);
150 numtoperm(pos,n%24,16);
151 break;
152 }
153 }
154
155 void domove(int m)
156 {
157 char *p=perm+8*m, i=8;
158
159 cycle(pos,p);
160 cycle(ori,p);
161 cycle(pos,p+4);
162 cycle(ori,p+4);
163 if(m<4)
164 for(;--i>3;) twist(p[i],i&1);
165 if(m<2)
166 for(i=4;i--;) twist(p[i],0);
167 }
168
169 void filltable(int ti)
170 {
171 int n=1,l=1, tl=tablesize[ti];
172
173 char* tb = tables[ti]=new char[tl];
174
175 memset( tb, 0, tl);
176 reset();
177 tb[getposition(ti)]=1;
178
179 while(n)
180 {
181 n=0;
182 for(int i=0;i<tl;i++){
183 if( tb[i]==l )
184 {
185 setposition(ti,i);
186 for( int f=0; f<6; f++)
187 {
188 for( int q=1;q<4;q++)
189 {
190 domove(f);
191 int r=getposition(ti);
192 if( ( q==2 || f>=(ti&6) ) && !tb[r])
193 {
194 tb[r]=l+1;
195 n++;
196 }
197 }
198 domove(f);
199 }
200 }
201 }
202 l++;
203 }
204 }
205
206 bool searchphase(int movesleft, int movesdone,int lastmove)
207 {
208 if( tables[phase ][getposition(phase )]-1 > movesleft ||
209 tables[phase+1][getposition(phase+1)]-1 > movesleft ) return false;
210
211 if(!movesleft) return true;
212
213 for( int i=6;i--;){
214 if( i-lastmove && (i-lastmove+1 || i|1 ) )
215 {
216 movecube[movesdone]=i;
217 for(int j=0;++j<4;){
218 domove(i);
219 moveamount[movesdone]=j;
220 if( (j==2 || i>=phase ) &&
221 searchphase(movesleft-1,movesdone+1,i) ) return true;
222 }
223 domove(i);
224 }
225 }
226 return false;
227 }
228
229 int check()
230 {
231 for(int i=0;i<answer.length()-2;i+=2)
232 {
233 if(answer[i] == answer[i+2])
234 {
235 answer[i+1]=(answer[i+1]+answer[i+3])%4+'0';
236 answer.erase(i+2,2);
237 }
238 }
239 return 1;
240 }
241
242 int solveCube(string state[])//调用入口
243 {
244 int f,i=0,j=0,k=0,pc,mor;
245 for(; k<20; k++) val[k]=k<12?2:3;
246 for(; j<8; j++) filltable(j);
247
248 for(; i<20; i++)
249 {
250 f=pc=k=mor=0;
251 for(;f<val[i];f++)
252 {
253 j=strchr(faces,state[i][f])-faces;
254 if(j>k) {k=j;mor=f;}
255 pc+= 1<<j;
256 }
257 for(f=0; f<20; f++)
258 if( pc==bithash[f]-64 ) break;
259 pos[order[i]-CHAROFFSET]=f;
260 ori[order[i]-CHAROFFSET]=mor%val[i];
261 }
262
263 for( ; phase<8; phase+=2)
264 {
265 for( j=0; !searchphase(j,0,9); j++);
266 for( i=0; i<j; i++)
267 {
268 answer += "FBRLUD"[movecube[i]];
269 answer += (moveamount[i] + '0');
270 }
271
272 }
273 cout<<endl<<"answer:"<<answer<<endl;
274 check();
275 cout<<"checking......\nanswer:"<<answer<<endl;
276 return 1;
277 cout<<"send command"<<endl;
278
279 }
12 October 2016