1 /*
2  * cu2.cpp v 20051216 - Fri 2005 Dec 16
3  * 2x2x2 Cube Solver class (c) 2005 by Eric Dietz
4  * notes: readme.txt  email: root@wrongway.org
5  */
6 
7 // includes
8 #include <stdlib.h>
9 #include <stdio.h>
10 #include <string>
11 // namespace
12 using namespace std;
13 
14 // local includes
15 #include "cu2.h"
16 
17 // defines
18 
19 // cu2 class definition
20 
21 // constructor
cu2()22 cu2::cu2()
23 {
24   // values for shorten:
25   // SHORTEN_NONE, SHORTEN_STRIP_SOME, SHORTEN_STRIP_ALL,
26   // SHORTEN_STRIP_ROTATE_SOME, SHORTEN_STRIP_ROTATE_ALL
27   // cube rotations means trying to solve the cube with every possible different
28   // color on top and on front.  This will greatly affect the speed of solvecube().
29   shorten = SHORTEN_STRIP_ROTATE_ALL;
30   erval = 0;
31   solution = "";
32   resetcube();
33   numcubes++;
34 }
35 // destructor
~cu2()36 cu2::~cu2()
37 {
38   numcubes--;
39 }
40 // version string
41 const char* cu2::version = "20051216";
42 // number of instantiated cubes
43 int cu2::numcubes = 0;
44 // overloaded == comparison
operator ==(const cu2 & q)45 const bool cu2::operator==(const cu2 &q)
46 {
47   for (int i = 1; i <= N; ++i)
48     for (int j = 1; j <= N; ++j)
49       if
50       (q.cube[i][N+1][j] != cube[i][N+1][j] ||
51        q.cube[0][i][j]   != cube[0][i][j]   ||
52        q.cube[i][j][0]   != cube[i][j][0]   ||
53        q.cube[N+1][i][j] != cube[N+1][i][j] ||
54        q.cube[i][j][N+1] != cube[i][j][N+1] ||
55        q.cube[i][0][j]   != cube[i][0][j]  )
56         return false;
57   return true;
58 }
59 // overloaded != comparison
operator !=(const cu2 & q)60 const bool cu2::operator!=(const cu2 &q)
61 {
62   return !operator==(q);
63 }
64 // pointer to cube array
face(int x,int y,int z)65 int *cu2::face(int x, int y, int z)
66 {
67   if (x < 0 || x > N+1 || y < 0 || y > N+1 || z < 0 || z > N+1)
68     return NULL;
69   return &cube[x][y][z];
70 }
71 // display cube diagram
renderscreen()72 const void cu2::renderscreen()
73 {
74   /*
75   for (int i = 1; i <= N; i++) {
76     for (int j = 1; j <= N; j++) printf("  ");
77     printf(" ");
78     for (int j = 1; j <= N; j++)
79       printf(" %i", cube[j][N+1][N+1-i]);
80     printf("\n");
81   }
82   for (int i = 1; i <= N; i++) {
83     for (int j = 1; j <= N; j++)
84       printf(" %i", cube[0][N+1-i][N+1-j]);
85     printf(" ");
86     for (int j = 1; j <= N; j++)
87       printf(" %i", cube[j][N+1-i][0]);
88     printf(" ");
89     for (int j = 1; j <= N; j++)
90       printf(" %i", cube[N+1][N+1-i][j]);
91     printf(" ");
92     for (int j = 1; j <= N; j++)
93       printf(" %i", cube[N+1-j][N+1-i][N+1]);
94     printf("\n");
95   }
96   for (int i = 1; i <= N; i++) {
97     for (int j = 1; j <= N; j++) printf("  ");
98     printf(" ");
99     for (int j = 1; j <= N; j++)
100       printf(" %i", cube[j][0][i]);
101     printf("\n");
102   }
103   */
104   printf(
105 "\
106       %i %i\n\
107       %i %i\n\
108  %i %i  %i %i  %i %i  %i %i\n\
109  %i %i  %i %i  %i %i  %i %i\n\
110       %i %i\n\
111       %i %i\n\
112 ",
113 cube[1][3][2], cube[2][3][2],
114 cube[1][3][1], cube[2][3][1],
115 cube[0][2][2], cube[0][2][1],
116 cube[1][2][0], cube[2][2][0],
117 cube[3][2][1], cube[3][2][2],
118 cube[2][2][3], cube[1][2][3],
119 cube[0][1][2], cube[0][1][1],
120 cube[1][1][0], cube[2][1][0],
121 cube[3][1][1], cube[3][1][2],
122 cube[2][1][3], cube[1][1][3],
123 cube[1][0][1], cube[2][0][1],
124 cube[1][0][2], cube[2][0][2]
125   );
126 }
127 // return solvedness of cube
issolved()128 const bool cu2::issolved()
129 {
130   int c[7], d;
131   c[1] = cube[1][N+1][1]; c[2] = cube[0][1][1];
132   c[3] = cube[1][1][0];   c[4] = cube[N+1][1][1];
133   c[5] = cube[1][1][N+1]; c[6] = cube[1][0][1];
134   for (int i = 1; i <= 6; i++) {
135     d = 0;
136     for (int j = 1; j <= 6; j++)
137       if (c[i] == j)
138         d++;
139     if (d != 1)
140       return false;
141   }
142   for (int i = 1; i <= N; i++)
143     for (int j = 1; j <= N; j++)
144       if
145       (cube[i][N+1][j] != c[1] ||
146        cube[0][i][j]   != c[2] ||
147        cube[i][j][0]   != c[3] ||
148        cube[N+1][i][j] != c[4] ||
149        cube[i][j][N+1] != c[5] ||
150        cube[i][0][j]   != c[6])
151         return false;
152   return true;
153 }
154 // reset the cube
resetcube()155 const void cu2::resetcube()
156 {
157   solution = "";
158   for (int i = 0; i <= MOV; i++)
159     mov[i] = 0;
160   for (int i = 0; i <= N+1; i++)
161     for (int j = 0; j <= N+1; j++)
162       for (int k = 0; k <= N+1; k++)
163         cube[i][j][k] = 0;
164   for (int i = 1; i <= N; i++)
165     for (int j = 1; j <= N; j++)
166     {
167       cube[i][N+1][j] = 1;
168       cube[0][i][j]   = 2;
169       cube[i][j][0]   = 3;
170       cube[N+1][i][j] = 4;
171       cube[i][j][N+1] = 5;
172       cube[i][0][j]   = 6;
173     }
174   erval = 0;
175   fx = 0; fy = 0; fz = 0;
176   inited = true;
177 }
178 // temporary copier function
copytemp(int c[N+2][N+2][N+2],int t[N+2][N+2][N+2])179 void cu2::copytemp(int c[N+2][N+2][N+2], int t[N+2][N+2][N+2])
180 {
181   for (int i = 0; i <= N+1; i++)
182     for (int j = 0; j <= N+1; j++)
183       for (int k = 0; k <= N+1; k++)
184         t[i][j][k] = c[i][j][k];
185 }
186 // rotate given slice left
slice_l(int s)187 const void cu2::slice_l(int s)
188 {
189   if (s < 1 || s > N) return;
190   int temp[N+2][N+2][N+2];
191   for (int i = 0; i <= N+1; i++)
192     for (int j = 0; j <= N+1; j++)
193       for (int k = 0; k <= N+1; k++)
194         temp[i][j][k] = cube[i][j][k];
195   //copytemp(cube, temp);
196   for (int i = 1; i <= N; i++)
197   {
198     if (s == 1)
199       for (int j = 1; j <= N; j++)
200         cube[i][0][j] = temp[N+1-j][0][i];
201     else if (s == N)
202       for (int j = 1; j <= N; j++)
203         cube[i][N+1][j] = temp[N+1-j][N+1][i];
204     cube[i][s][0]   = temp[N+1][s][i];
205     cube[i][s][N+1] = temp[0][s][i];
206     cube[0][s][i]   = temp[N+1-i][s][0];
207     cube[N+1][s][i] = temp[N+1-i][s][N+1];
208   }
209 }
210 // rotate given slice right
slice_r(int s)211 const void cu2::slice_r(int s)
212 {
213   if (s < 1 || s > N) return;
214   int temp[N+2][N+2][N+2];
215   for (int i = 0; i <= N+1; i++)
216     for (int j = 0; j <= N+1; j++)
217       for (int k = 0; k <= N+1; k++)
218         temp[i][j][k] = cube[i][j][k];
219   //copytemp(cube, temp);
220   for (int i = 1; i <= N; i++)
221   {
222     if (s == 1)
223       for (int j = 1; j <= N; j++)
224         cube[i][0][j] = temp[j][0][N+1-i];
225     else if (s == N)
226       for (int j = 1; j <= N; j++)
227         cube[i][N+1][j] = temp[j][N+1][N+1-i];
228     cube[i][s][0]   = temp[0][s][N+1-i];
229     cube[i][s][N+1] = temp[N+1][s][N+1-i];
230     cube[0][s][i]   = temp[i][s][N+1];
231     cube[N+1][s][i] = temp[i][s][0];
232   }
233 }
234 // rotate given slice up
slice_u(int s)235 const void cu2::slice_u(int s)
236 {
237   if (s < 1 || s > N) return;
238   int temp[N+2][N+2][N+2];
239   for (int i = 0; i <= N+1; i++)
240     for (int j = 0; j <= N+1; j++)
241       for (int k = 0; k <= N+1; k++)
242         temp[i][j][k] = cube[i][j][k];
243   //copytemp(cube, temp);
244   for (int i = 1; i <= N; i++)
245   {
246     if (s == 1)
247       for (int j = 1; j <= N; j++)
248         cube[0][i][j] = temp[0][j][N+1-i];
249     if (s == N)
250       for (int j = 1; j <= N; j++)
251         cube[N+1][i][j] = temp[N+1][j][N+1-i];
252     cube[s][i][0]   = temp[s][0][N+1-i];
253     cube[s][i][N+1] = temp[s][N+1][N+1-i];
254     cube[s][0][i]   = temp[s][i][N+1];
255     cube[s][N+1][i] = temp[s][i][0];
256   }
257 }
258 // rotate given slice down
slice_d(int s)259 const void cu2::slice_d(int s)
260 {
261   if (s < 1 || s > N) return;
262   int temp[N+2][N+2][N+2];
263   for (int i = 0; i <= N+1; i++)
264     for (int j = 0; j <= N+1; j++)
265       for (int k = 0; k <= N+1; k++)
266         temp[i][j][k] = cube[i][j][k];
267   //copytemp(cube, temp);
268   for (int i = 1; i <= N; i++)
269   {
270     if (s == 1)
271       for (int j = 1; j <= N; j++)
272         cube[0][i][j] = temp[0][N+1-j][i];
273     if (s == N)
274       for (int j = 1; j <= N; j++)
275         cube[N+1][i][j] = temp[N+1][N+1-j][i];
276     cube[s][i][0]   = temp[s][N+1][i];
277     cube[s][i][N+1] = temp[s][0][i];
278     cube[s][0][i]   = temp[s][N+1-i][0];
279     cube[s][N+1][i] = temp[s][N+1-i][N+1];
280   }
281 }
282 // rotate given slice clockwise
slice_c(int s)283 const void cu2::slice_c(int s)
284 {
285   if (s < 1 || s > N) return;
286   int temp[N+2][N+2][N+2];
287   for (int i = 0; i <= N+1; i++)
288     for (int j = 0; j <= N+1; j++)
289       for (int k = 0; k <= N+1; k++)
290         temp[i][j][k] = cube[i][j][k];
291   //copytemp(cube, temp);
292   for (int i = 1; i <= N; i++)
293   {
294     if (s == 1)
295       for (int j = 1; j <= N; j++)
296         cube[i][j][0] = temp[N+1-j][i][0];
297     if (s == N)
298       for (int j = 1; j <= N; j++)
299         cube[i][j][N+1] = temp[N+1-j][i][N+1];
300     cube[i][0][s]   = temp[N+1][i][s];
301     cube[i][N+1][s] = temp[0][i][s];
302     cube[0][i][s]   = temp[N+1-i][0][s];
303     cube[N+1][i][s] = temp[N+1-i][N+1][s];
304   }
305 }
306 // rotate given slice counterclockwise
slice_a(int s)307 const void cu2::slice_a(int s)
308 {
309   if (s < 1 || s > N) return;
310   int temp[N+2][N+2][N+2];
311   for (int i = 0; i <= N+1; i++)
312     for (int j = 0; j <= N+1; j++)
313       for (int k = 0; k <= N+1; k++)
314         temp[i][j][k] = cube[i][j][k];
315   //copytemp(cube, temp);
316   for (int i = 1; i <= N; i++)
317   {
318     if (s == 1)
319       for (int j = 1; j <= N; j++)
320         cube[i][j][0] = temp[j][N+1-i][0];
321     if (s == N)
322       for (int j = 1; j <= N; j++)
323         cube[i][j][N+1] = temp[j][N+1-i][N+1];
324     cube[i][0][s]   = temp[0][N+1-i][s];
325     cube[i][N+1][s] = temp[N+1][N+1-i][s];
326     cube[0][i][s]   = temp[i][N+1][s];
327     cube[N+1][i][s] = temp[i][0][s];
328   }
329 }
330 // cube rotator aliases
UL()331 const void cu2::UL() { slice_l(N  ); }  // rotate top slice left
UR()332 const void cu2::UR() { slice_r(N  ); }  // rotate top slice right
DL()333 const void cu2::DL() { slice_l(1  ); }  // rotate bottom slice left
DR()334 const void cu2::DR() { slice_r(1  ); }  // rotate bottom slice right
LU()335 const void cu2::LU() { slice_u(1  ); }  // rotate left slice up
LD()336 const void cu2::LD() { slice_d(1  ); }  // rotate left slice down
RU()337 const void cu2::RU() { slice_u(N  ); }  // rotate right slice up
RD()338 const void cu2::RD() { slice_d(N  ); }  // rotate right slice down
FC()339 const void cu2::FC() { slice_c(1  ); }  // rotate front slice clockwise
FA()340 const void cu2::FA() { slice_a(1  ); }  // rotate front slice counterclockwise
BC()341 const void cu2::BC() { slice_c(N  ); }  // rotate rear slice clockwise (from front view)
BA()342 const void cu2::BA() { slice_a(N  ); }  // rotate rear slice counterclockwise (from front view)
CL()343 const void cu2::CL() { for (int i = 1; i <= N; i++) slice_l(i); } // rotate whole cube left
CR()344 const void cu2::CR() { for (int i = 1; i <= N; i++) slice_r(i); } // rotate whole cube right
CU()345 const void cu2::CU() { for (int i = 1; i <= N; i++) slice_u(i); } // rotate whole cube up
CD()346 const void cu2::CD() { for (int i = 1; i <= N; i++) slice_d(i); } // rotate whole cube down
CC()347 const void cu2::CC() { for (int i = 1; i <= N; i++) slice_c(i); } // rotate whole cube clockwise
CA()348 const void cu2::CA() { for (int i = 1; i <= N; i++) slice_a(i); } // rotate whole cube counterclockwise
U2()349 const void cu2::U2() { UL(); UL(); }    // rotate top slice twice
D2()350 const void cu2::D2() { DR(); DR(); }    // rotate bottom slice twice
L2()351 const void cu2::L2() { LD(); LD(); }    // rotate left slice twice
R2()352 const void cu2::R2() { RU(); RU(); }    // rotate right slice twice
F2()353 const void cu2::F2() { FC(); FC(); }    // rotate front slice twice
B2()354 const void cu2::B2() { BA(); BA(); }    // rotate rear slice twice
355 // end of cube rotator aliases
356 // scramble the cube
scramblecube()357 const void cu2::scramblecube()
358 {
359   int axis_direction, slice;
360   // come up with a better calculation for a good number of random moves based on cube size later
361   int nummoves = (N-2)*25+10;
362   nummoves += rand() % nummoves;
363   resetcube();
364   for (int i = 1; i <= nummoves; i++)
365   {
366     axis_direction = rand() % 6 + 1;  // which axis and direction
367     slice = rand() % N + 1;           // which slice
368     switch (axis_direction)
369     {
370       case 1: slice_l(slice); break;
371       case 2: slice_r(slice); break;
372       case 3: slice_u(slice); break;
373       case 4: slice_d(slice); break;
374       case 5: slice_c(slice); break;
375       case 6: slice_a(slice); break;
376     }
377   }
378 }
379 // do a series of moves
domoves(string s)380 const void cu2::domoves(string s)
381 {
382   string a = "";
383   for (int i = 1; i <= (int)(s.length() / 3); i++) {
384     a = s.substr(i * 3 - 3, 2);
385     if      (a == "UL") UL();
386     else if (a == "UR") UR();
387     else if (a == "DL") DL();
388     else if (a == "DR") DR();
389     else if (a == "LU") LU();
390     else if (a == "LD") LD();
391     else if (a == "RU") RU();
392     else if (a == "RD") RD();
393     else if (a == "FC") FC();
394     else if (a == "FA") FA();
395     else if (a == "BC") BC();
396     else if (a == "BA") BA();
397     else if (a == "CL") CL();
398     else if (a == "CR") CR();
399     else if (a == "CU") CU();
400     else if (a == "CD") CD();
401     else if (a == "CC") CC();
402     else if (a == "CA") CA();
403     else if (a == "U2") U2();
404     else if (a == "D2") D2();
405     else if (a == "L2") L2();
406     else if (a == "R2") R2();
407     else if (a == "F2") F2();
408     else if (a == "B2") B2();
409   }
410 }
411 // execute solution
dosolution()412 const void cu2::dosolution()
413 {
414   domoves(solution);
415 }
416 // find given corner in clockwise order
findcorner_c(int a,int b,int c)417 const int cu2::findcorner_c(int a, int b, int c)
418 {
419   // for speed I just broke this into a series of if's instead of for's
420   if      (cube[1][3][1] == a && cube[1][2][0] == b && cube[0][2][1] == c) // top left front
421   { fx = 1; fy = 3; fz = 1; return POSY; }
422   else if (cube[1][2][0] == a && cube[0][2][1] == b && cube[1][3][1] == c)
423   { fx = 1; fy = 2; fz = 0; return NEGZ; }
424   else if (cube[0][2][1] == a && cube[1][3][1] == b && cube[1][2][0] == c)
425   { fx = 0; fy = 2; fz = 1; return NEGX; }
426   else if (cube[2][3][1] == a && cube[3][2][1] == b && cube[2][2][0] == c) // top right front
427   { fx = 2; fy = 3; fz = 1; return POSY; }
428   else if (cube[3][2][1] == a && cube[2][2][0] == b && cube[2][3][1] == c)
429   { fx = 3; fy = 2; fz = 1; return POSX; }
430   else if (cube[2][2][0] == a && cube[2][3][1] == b && cube[3][2][1] == c)
431   { fx = 2; fy = 2; fz = 0; return NEGZ; }
432   else if (cube[1][3][2] == a && cube[0][2][2] == b && cube[1][2][3] == c) // top left back
433   { fx = 1; fy = 3; fz = 2; return POSY; }
434   else if (cube[0][2][2] == a && cube[1][2][3] == b && cube[1][3][2] == c)
435   { fx = 0; fy = 2; fz = 2; return NEGX; }
436   else if (cube[1][2][3] == a && cube[1][3][2] == b && cube[0][2][2] == c)
437   { fx = 1; fy = 2; fz = 3; return POSZ; }
438   else if (cube[2][3][2] == a && cube[2][2][3] == b && cube[3][2][2] == c) // top right back
439   { fx = 2; fy = 3; fz = 2; return POSY; }
440   else if (cube[2][2][3] == a && cube[3][2][2] == b && cube[2][3][2] == c)
441   { fx = 2; fy = 2; fz = 3; return POSZ; }
442   else if (cube[3][2][2] == a && cube[2][3][2] == b && cube[2][2][3] == c)
443   { fx = 3; fy = 2; fz = 2; return POSX; }
444   else if (cube[1][0][1] == a && cube[0][1][1] == b && cube[1][1][0] == c) // bottom left front
445   { fx = 1; fy = 0; fz = 1; return NEGY; }
446   else if (cube[0][1][1] == a && cube[1][1][0] == b && cube[1][0][1] == c)
447   { fx = 0; fy = 1; fz = 1; return NEGX; }
448   else if (cube[1][1][0] == a && cube[1][0][1] == b && cube[0][1][1] == c)
449   { fx = 1; fy = 1; fz = 0; return NEGZ; }
450   else if (cube[2][0][1] == a && cube[2][1][0] == b && cube[3][1][1] == c) // bottom right front
451   { fx = 2; fy = 0; fz = 1; return NEGY; }
452   else if (cube[2][1][0] == a && cube[3][1][1] == b && cube[2][0][1] == c)
453   { fx = 2; fy = 1; fz = 0; return NEGZ; }
454   else if (cube[3][1][1] == a && cube[2][0][1] == b && cube[2][1][0] == c)
455   { fx = 3; fy = 1; fz = 1; return POSX; }
456   else if (cube[1][0][2] == a && cube[1][1][3] == b && cube[0][1][2] == c) // bottom left back
457   { fx = 1; fy = 0; fz = 2; return NEGY; }
458   else if (cube[1][1][3] == a && cube[0][1][2] == b && cube[1][0][2] == c)
459   { fx = 1; fy = 1; fz = 3; return POSZ; }
460   else if (cube[0][1][2] == a && cube[1][0][2] == b && cube[1][1][3] == c)
461   { fx = 0; fy = 1; fz = 2; return NEGX; }
462   else if (cube[2][0][2] == a && cube[3][1][2] == b && cube[2][1][3] == c) // bottom right back
463   { fx = 2; fy = 0; fz = 2; return NEGY; }
464   else if (cube[3][1][2] == a && cube[2][1][3] == b && cube[2][0][2] == c)
465   { fx = 3; fy = 1; fz = 2; return POSX; }
466   else if (cube[2][1][3] == a && cube[2][0][2] == b && cube[3][1][2] == c)
467   { fx = 2; fy = 1; fz = 3; return POSZ; }
468   return 0;
469 }
470 // find given corner in counterclockwise order
findcorner_a(int a,int b,int c)471 const int cu2::findcorner_a(int a, int b, int c)
472 {
473   // for speed I just broke this into a series of if's instead of for's
474   if      (cube[1][3][1] == a && cube[0][2][1] == b && cube[1][2][0] == c) // top left front
475   { fx = 1; fy = 3; fz = 1; return POSY; }
476   else if (cube[1][2][0] == a && cube[1][3][1] == b && cube[0][2][1] == c)
477   { fx = 1; fy = 2; fz = 0; return NEGZ; }
478   else if (cube[0][2][1] == a && cube[1][2][0] == b && cube[1][3][1] == c)
479   { fx = 0; fy = 2; fz = 1; return NEGX; }
480   else if (cube[2][3][1] == a && cube[2][2][0] == b && cube[3][2][1] == c) // top right front
481   { fx = 2; fy = 3; fz = 1; return POSY; }
482   else if (cube[3][2][1] == a && cube[2][3][1] == b && cube[2][2][0] == c)
483   { fx = 3; fy = 2; fz = 1; return POSX; }
484   else if (cube[2][2][0] == a && cube[3][2][1] == b && cube[2][3][1] == c)
485   { fx = 2; fy = 2; fz = 0; return NEGZ; }
486   else if (cube[1][3][2] == a && cube[1][2][3] == b && cube[0][2][2] == c) // top left back
487   { fx = 1; fy = 3; fz = 2; return POSY; }
488   else if (cube[0][2][2] == a && cube[1][3][2] == b && cube[1][2][3] == c)
489   { fx = 0; fy = 2; fz = 2; return NEGX; }
490   else if (cube[1][2][3] == a && cube[0][2][2] == b && cube[1][3][2] == c)
491   { fx = 1; fy = 2; fz = 3; return POSZ; }
492   else if (cube[2][3][2] == a && cube[3][2][2] == b && cube[2][2][3] == c) // top right back
493   { fx = 2; fy = 3; fz = 2; return POSY; }
494   else if (cube[2][2][3] == a && cube[2][3][2] == b && cube[3][2][2] == c)
495   { fx = 2; fy = 2; fz = 3; return POSZ; }
496   else if (cube[3][2][2] == a && cube[2][2][3] == b && cube[2][3][2] == c)
497   { fx = 3; fy = 2; fz = 2; return POSX; }
498   else if (cube[1][0][1] == a && cube[1][1][0] == b && cube[0][1][1] == c) // bottom left front
499   { fx = 1; fy = 0; fz = 1; return NEGY; }
500   else if (cube[0][1][1] == a && cube[1][0][1] == b && cube[1][1][0] == c)
501   { fx = 0; fy = 1; fz = 1; return NEGX; }
502   else if (cube[1][1][0] == a && cube[0][1][1] == b && cube[1][0][1] == c)
503   { fx = 1; fy = 1; fz = 0; return NEGZ; }
504   else if (cube[2][0][1] == a && cube[3][1][1] == b && cube[2][1][0] == c) // bottom right front
505   { fx = 2; fy = 0; fz = 1; return NEGY; }
506   else if (cube[2][1][0] == a && cube[2][0][1] == b && cube[3][1][1] == c)
507   { fx = 2; fy = 1; fz = 0; return NEGZ; }
508   else if (cube[3][1][1] == a && cube[2][1][0] == b && cube[2][0][1] == c)
509   { fx = 3; fy = 1; fz = 1; return POSX; }
510   else if (cube[1][0][2] == a && cube[0][1][2] == b && cube[1][1][3] == c) // bottom left back
511   { fx = 1; fy = 0; fz = 2; return NEGY; }
512   else if (cube[1][1][3] == a && cube[1][0][2] == b && cube[0][1][2] == c)
513   { fx = 1; fy = 1; fz = 3; return POSZ; }
514   else if (cube[0][1][2] == a && cube[1][1][3] == b && cube[1][0][2] == c)
515   { fx = 0; fy = 1; fz = 2; return NEGX; }
516   else if (cube[2][0][2] == a && cube[2][1][3] == b && cube[3][1][2] == c) // bottom right back
517   { fx = 2; fy = 0; fz = 2; return NEGY; }
518   else if (cube[3][1][2] == a && cube[2][0][2] == b && cube[2][1][3] == c)
519   { fx = 3; fy = 1; fz = 2; return POSX; }
520   else if (cube[2][1][3] == a && cube[3][1][2] == b && cube[2][0][2] == c)
521   { fx = 2; fy = 1; fz = 3; return POSZ; }
522   return 0;
523 }
524 // find given corner
findcorner(int a,int b,int c)525 const int cu2::findcorner(int a, int b, int c)
526 {
527   int x;
528   if ((x = findcorner_c(a, b, c))) return x;
529   if ((x = findcorner_a(a, b, c))) return x;
530   return 0;
531 }
532 // convert standard string to metric
std_to_metr(string s)533 const string cu2::std_to_metr(string s)
534 {
535   string a = s;
536   char slice_std, slice_metr='\0', dir, dir_prime='\0';
537   for (int i = 1; i <= (int)(s.length() / 3); i++)
538   {
539     slice_std = s.at(i * 3 - 3);
540     dir = s.at(i * 3 - 2);
541     if (slice_std == 'C')
542       continue;
543     if (dir == '2')
544     {
545       if
546       (slice_std == 'U' || slice_std == 'D')
547         dir_prime = 'L';
548       else if
549       (slice_std == 'L' || slice_std == 'R')
550         dir_prime = 'U';
551       else if
552       (slice_std == 'F' || slice_std == 'B')
553         dir_prime = 'C';
554     }
555     if
556     (slice_std == 'D' || slice_std == 'L' || slice_std == 'F')
557       slice_metr = '1';
558     else if
559     (slice_std == 'U' || slice_std == 'R' || slice_std == 'B')
560       slice_metr = '2';
561     a.at(i * 3 - 3) = slice_metr;
562     if (dir == '2')
563     {
564       a.at(i * 3 - 2) = dir_prime;
565       a.insert(i * 3, "  .");
566       a.at(i * 3) = slice_metr;
567       a.at(i * 3 + 1) = dir_prime;
568       i++;
569     }
570   }
571   return a;
572 }
573 // convert metric string to standard
metr_to_std(string s)574 const string cu2::metr_to_std(string s)
575 {
576   string a = s;
577   char slice_std='\0', slice_metr, dir;
578   for (int i = 1; i <= (int)(s.length() / 3); i++)
579   {
580     slice_metr = s.at(i * 3 - 3);
581     dir = s.at(i * 3 - 2);
582     if (slice_metr == 'C')
583       continue;
584     switch (dir)
585     {
586     case 'L':
587     case 'R':
588       switch (slice_metr)
589       {
590         case '1': slice_std = 'D'; break;
591         case '2': slice_std = 'U'; break;
592       }
593       break;
594     case 'U':
595     case 'D':
596       switch (slice_metr)
597       {
598         case '1': slice_std = 'L'; break;
599         case '2': slice_std = 'R'; break;
600       }
601       break;
602     case 'C':
603     case 'A':
604       switch (slice_metr)
605       {
606         case '1': slice_std = 'F'; break;
607         case '2': slice_std = 'B'; break;
608       }
609       break;
610     }
611     a.at(i * 3 - 3) = slice_std;
612   }
613   return a;
614 }
615 // convert standard string to relative
std_to_rel(string s)616 const string cu2::std_to_rel(string s)
617 {
618   string a = s;
619   char slice, dir_std, dir_rel='\0';
620   for (int i = 1; i <= (int)(s.length() / 3); i++)
621   {
622     slice = s.at(i * 3 - 3);
623     dir_std = s.at(i * 3 - 2);
624     if (slice == 'C')
625       continue;
626     switch (dir_std)
627     {
628       case 'L': dir_rel = '+'; break;
629       case 'R': dir_rel = '-'; break;
630       case 'U': dir_rel = '-'; break;
631       case 'D': dir_rel = '+'; break;
632       case 'C': dir_rel = '+'; break;
633       case 'A': dir_rel = '-'; break;
634       case '2': dir_rel = '2'; break;
635     }
636     a.at(i * 3 - 2) = dir_rel;
637   }
638   return a;
639 }
640 // convert relative string to standard
rel_to_std(string s)641 const string cu2::rel_to_std(string s)
642 {
643   string a = s;
644   char slice, dir_std='\0', dir_rel;
645   for (int i = 1; i <= (int)(s.length() / 3); i++)
646   {
647     slice = s.at(i * 3 - 3);
648     dir_rel = s.at(i * 3 - 2);
649     if (slice == 'C')
650       continue;
651     switch (slice)
652     {
653     case 'U':
654     case 'D':
655       switch (dir_rel)
656       {
657         case '+': dir_std = 'L'; break;
658         case '-': dir_std = 'R'; break;
659       }
660       break;
661     case 'L':
662     case 'R':
663       switch (dir_rel)
664       {
665         case '+': dir_std = 'D'; break;
666         case '-': dir_std = 'U'; break;
667       }
668       break;
669     case 'F':
670     case 'B':
671       switch (dir_rel)
672       {
673         case '+': dir_std = 'C'; break;
674         case '-': dir_std = 'A'; break;
675       }
676       break;
677     }
678     if (dir_rel == '2')
679       dir_std = '2';
680     a.at(i * 3 - 2) = dir_std;
681   }
682   return a;
683 }
684 // convert metric string to relative
metr_to_rel(string s)685 const string cu2::metr_to_rel(string s)
686 {
687   return std_to_rel(metr_to_std(s)); // the lazy way
688 }
689 // convert relative string to metric
rel_to_metr(string s)690 const string cu2::rel_to_metr(string s)
691 {
692   return std_to_metr(rel_to_std(s)); // the lazy way
693 }
694 // allow the use of the half turn
usehalfturns(string s,int b=0)695 const string cu2::usehalfturns(string s, int b=0)
696 {
697   // note: ALL this routine does is change things like LU.LU. to L2.
698   // it does NOT change LU.LU.LU. to LD. nor does it strip out things
699   // like L2.L2.  Use concise() for that.
700   string a = s;
701   char slice, dir, slice_next, dir_next;
702   for (int i = 1; i <= (int)(a.length() / 3) - 1; i++)
703   {
704     slice = a.at(i * 3 - 3);
705     dir = a.at(i * 3 - 2);
706     slice_next = a.at(i * 3);
707     dir_next = a.at(i * 3 + 1);
708     if (slice == 'C' || dir == '2') continue;
709     if (slice == slice_next && dir == dir_next)
710     {
711       a.at(i * 3 - 2) = '2';
712       a.erase(i * 3, 3);
713       // change mov[] if necessary
714       if (b) {
715         shortenmov(i);
716       }
717       //
718       i--;
719     }
720   }
721   return a;
722 }
723 // strip out redundant moves from a solution string
concise(string s,int b=0)724 const string cu2::concise(string s, int b=0)
725 {
726   int strips = 0;
727   // total revamp, Nov/04
728   string a = std_to_metr(s);
729   int redundancies;
730   // step 1: interpolate whole cube moves, e.g., CL,LU,FC, to FA,RU,
731   {
732     char slice, dir;
733     int sUD, sLR, sFB;
734     char dL, dR, dU, dD, dC, dA;
735     for (int i = 1; i <= (int)(a.length() / 3); i++)
736     {
737       slice = a.at(i * 3 - 3);
738       if (slice == 'C')
739       {
740         dir = a.at(i * 3 - 2);
741         sUD = 1; sLR = 1; sFB = 1;
742         dL = 'L'; dR = 'R'; dU = 'U'; dD = 'D'; dC = 'C'; dA = 'A';
743         switch (dir)
744         {
745         case 'L':
746           sFB = -1; dU = 'A'; dD = 'C'; dC = 'U'; dA = 'D'; break;
747         case 'R':
748           sLR = -1; dU = 'C'; dD = 'A'; dC = 'D'; dA = 'U'; break;
749         case 'U':
750           sUD = -1; dL = 'C'; dR = 'A'; dC = 'R'; dA = 'L'; break;
751         case 'D':
752           sFB = -1; dL = 'A'; dR = 'C'; dC = 'L'; dA = 'R'; break;
753         case 'C':
754           sUD = -1; dL = 'D'; dR = 'U'; dU = 'L'; dD = 'R'; break;
755         case 'A':
756           sLR = -1; dL = 'U'; dR = 'D'; dU = 'R'; dD = 'L'; break;
757         }
758         a.erase(i * 3 - 3, 3);
759         // change mov[] if necessary
760         if (b) {
761           strips++; if (strips > b) shortenmov(i);
762         }
763         //
764         for (int j = i; j <= (int)(a.length() / 3); j++)
765         {
766           slice = a.at(j * 3 - 3);
767           dir = a.at(j * 3 - 2);
768           switch (dir)
769           {
770           case 'L':
771             if (sUD == -1 && slice != 'C') slice = ((N+1-(slice-'0'))+'0');
772             dir = dL; break;
773           case 'R':
774             if (sUD == -1 && slice != 'C') slice = ((N+1-(slice-'0'))+'0');
775             dir = dR; break;
776           case 'U':
777             if (sLR == -1 && slice != 'C') slice = ((N+1-(slice-'0'))+'0');
778             dir = dU; break;
779           case 'D':
780             if (sLR == -1 && slice != 'C') slice = ((N+1-(slice-'0'))+'0');
781             dir = dD; break;
782           case 'C':
783             if (sFB == -1 && slice != 'C') slice = ((N+1-(slice-'0'))+'0');
784             dir = dC; break;
785           case 'A':
786             if (sFB == -1 && slice != 'C') slice = ((N+1-(slice-'0'))+'0');
787             dir = dA; break;
788           }
789           a.at(j * 3 - 3) = slice;
790           a.at(j * 3 - 2) = dir;
791         }
792         i--;
793       }
794     }
795   }
796   // the next steps are nested to make this condensation iterative
797   redundancies = 1;
798   while (redundancies)
799   {
800     redundancies = 0;
801     // step 2: re-order parallel slice groups, e.g., LU,RU,LD,RU, to LU,LD,RU,RU,
802     {
803       char slice, dir, slice_next, dir_next, dir_reverse='\0';
804       for (int i = 1; i <= (int)(a.length() / 3) - 2; i++)
805       {
806         slice = a.at(i * 3 - 3);
807         dir = a.at(i * 3 - 2);
808         slice_next = a.at(i * 3);
809         dir_next = a.at(i * 3 + 1);
810         if (slice_next == slice) continue;
811         switch (dir)
812         {
813           case 'L': dir_reverse = 'R'; break;
814           case 'R': dir_reverse = 'L'; break;
815           case 'U': dir_reverse = 'D'; break;
816           case 'D': dir_reverse = 'U'; break;
817           case 'C': dir_reverse = 'A'; break;
818           case 'A': dir_reverse = 'C'; break;
819         }
820         for
821         (int j = i + 2;
822          j <= (int)(a.length() / 3) && (dir_next == dir || dir_next == dir_reverse);
823          j++ )
824         {
825           slice_next = a.at(j * 3 - 3);
826           dir_next = a.at(j * 3 - 2);
827           if
828           (slice_next == slice && (dir_next == dir || dir_next == dir_reverse))
829           {
830             for (int k = j; k >= i + 2; k--)
831             {
832               a.at(k * 3 - 3) = a.at(k * 3 - 6);
833               a.at(k * 3 - 2) = a.at(k * 3 - 5);
834             }
835             a.at(i * 3) = slice_next;
836             a.at(i * 3 + 1) = dir_next;
837             i++;
838           }
839         }
840       }
841     }
842     // step 3: change 3/4 turns to 1/4 turn, e.g., LU,LU,LU, to LD,
843     {
844       char slice, dir, slice_next, dir_next, slice_after, dir_after, dir_reverse='\0';
845       for (int i = 1; i <= (int)(a.length() / 3) - 2; i++)
846       {
847         slice = a.at(i * 3 - 3);
848         dir = a.at(i * 3 - 2);
849         slice_next = a.at(i * 3);
850         dir_next = a.at(i * 3 + 1);
851         slice_after = a.at(i * 3 + 3);
852         dir_after = a.at(i * 3 + 4);
853         if
854         ((slice == slice_next) && (slice == slice_after) &&
855          (dir == dir_next) && (dir == dir_after) )
856         {
857           switch (dir)
858           {
859             case 'L': dir_reverse = 'R'; break;
860             case 'R': dir_reverse = 'L'; break;
861             case 'U': dir_reverse = 'D'; break;
862             case 'D': dir_reverse = 'U'; break;
863             case 'C': dir_reverse = 'A'; break;
864             case 'A': dir_reverse = 'C'; break;
865           }
866           a.at(i * 3 - 2) = dir_reverse;
867           a.erase(i * 3, 6);
868           // change mov[] if necessary
869           if (b) {
870             strips++; if (strips > b) shortenmov(i);
871             strips++; if (strips > b) shortenmov(i);
872           }
873           //
874           i -= 2; if (i < 0) i = 0;
875           redundancies++;
876         }
877       }
878     }
879     // step 4: remove contradicting moves, e.g., LU,LD,
880     {
881       char slice, dir, slice_next, dir_next, dir_reverse='\0';
882       for (int i = 1; i <= (int)(a.length() / 3) - 1; i++)
883       {
884         slice = a.at(i * 3 - 3);
885         dir = a.at(i * 3 - 2);
886         slice_next = a.at(i * 3);
887         dir_next = a.at(i * 3 + 1);
888         switch (dir)
889         {
890           case 'L': dir_reverse = 'R'; break;
891           case 'R': dir_reverse = 'L'; break;
892           case 'U': dir_reverse = 'D'; break;
893           case 'D': dir_reverse = 'U'; break;
894           case 'C': dir_reverse = 'A'; break;
895           case 'A': dir_reverse = 'C'; break;
896         }
897         if (slice == slice_next && dir_next == dir_reverse)
898         {
899           a.erase(i * 3 - 3, 6);
900           // change mov[] if necessary
901           if (b) {
902             strips++; if (strips > b) shortenmov(i);
903             strips++; if (strips > b) shortenmov(i);
904           }
905           //
906           i -= 2; if (i < 0) i = 0;
907           redundancies++;
908         }
909       }
910     }
911     // now try again until no redundancies are found.
912   }
913   // something to consider adding to this algorithm:
914   // seek out patterns like "UL.uL.dL.DL." and change them to "CL." and start over, or
915   // changing "UL.uL.dL." to "CL.DR." and starting over...
916   return metr_to_std(a);
917 }
918 // shorten mov[]
shortenmov(int m)919 const void cu2::shortenmov(int m)
920 {
921   int tot = 0, cur = 0;
922   for (int i = 1; i <= MOV; i++) {
923     tot += mov[i];
924     while (tot >= m && cur < 1) {
925       mov[i]--;
926       tot--;
927       cur++;
928     }
929   }
930 }
931 // solve the cube
solvecube()932 const int cu2::solvecube()
933 {
934   // possible return codes:
935   // 0, ERR_MISPAINTED, ERR_NONDESCRIPT,
936   // ERR_PARITY_CORNER_ROTATION, ERR_PARITY_EDGE_SWAP, ERR_PARITY_EDGE_FLIP
937   if (!inited) // make sure cube is initialized
938     return (erval = ERR_NOTINITED);
939   erval = 0;
940   int tcube[N+2][N+2][N+2];
941   int tmov[MOV+1], curmoves;
942   int U=0, D=0, L=0, R=0, F=0, B=0;
943   int cen[7];
944   string tsolution = "";
945   string prefix = "";
946   string cursolution;
947   // clear mov[] and solution
948   solution = "";
949   for (int i = 0; i <= MOV; i++)
950     mov[i] = 0;
951   for (int i = 1; i <= MOV; i++)
952     tmov[i] = 0;
953   tmov[0] = -1;
954   // step 1(ish) back up original cube
955   for (int i = 0; i <= N+1; i++)
956     for (int j = 0; j <= N+1; j++)
957       for (int k = 0; k <= N+1; k++)
958         tcube[i][j][k] = cube[i][j][k];
959   // make sure there is the right number of each color
960   for (int i = 0; i <= 6; i++)
961     cen[i] = 0;
962   for (int i = 0; i <= N+1; i++)
963     for (int j = 0; j <= N+1; j++)
964       for (int k = 0; k <= N+1; k++)
965         if (cube[i][j][k] >= 1 && cube[i][j][k] <= 6)
966           cen[cube[i][j][k]]++;
967   for (int i = 1; i <= 6; i++)
968     if (cen[i] != N * N)
969       return (erval = ERR_MISPAINTED);
970   // set up interpolation table so U,D,L,R,F,B=1,2,3,4,5,6
971   for (int i = 1; i <= 6; i++)
972     cen[i] = 0;
973   U = cube[1][N+1][1];
974   L = cube[0][N][1];
975   F = cube[1][N][0];
976   for (int i = 1; i <= 6; i++)
977   {
978     if (i != U && i != L && i != F)
979     {
980       if      (findcorner_c(F,U,i)) R = i;
981       else if (findcorner_c(U,L,i)) B = i;
982       else if (findcorner_c(L,F,i)) D = i;
983       else if (findcorner_a(F,U,i)) R = i; // normally there'd just be findcorner_c,
984       else if (findcorner_a(U,L,i)) B = i; // but I added _a to find backward corner
985       else if (findcorner_a(L,F,i)) D = i; // parity errors...
986     }
987   }
988   // make sure we have different colors for every face
989   if (U == L || L == F || F == U || R == 0 || D == 0 || B == 0)
990     return (erval = ERR_MISPAINTED);
991   cen[U] = 1; cen[L] = 2; cen[F] = 3;
992   cen[R] = 4; cen[B] = 5; cen[D] = 6;
993   // apply interpolation
994   for (int i = 1; i <= N; i++)
995   {
996     for (int j = 1; j <= N; j++)
997     {
998       cube[i][N+1][j] = cen[cube[i][N+1][j]];
999       cube[0][i][j]   = cen[cube[0][i][j]];
1000       cube[i][j][0]   = cen[cube[i][j][0]];
1001       cube[N+1][i][j] = cen[cube[N+1][i][j]];
1002       cube[i][j][N+1] = cen[cube[i][j][N+1]];
1003       cube[i][0][j]   = cen[cube[i][0][j]];
1004     }
1005   }
1006   // step 2(ish) make sure all cubelets are present (e.g., cube all there)
1007   cen[0] = 0;
1008   for (int i = 2; i <= 5 && !erval; i++)
1009   {
1010     if (!findcorner_c(1, (i<5?i+1:i-3), i)) {
1011       if (findcorner_a(1, (i<5?i+1:i-3), i)) cen[0]++;
1012       else erval = ERR_MISPAINTED;
1013     }
1014     if (!findcorner_c(6, i, (i<5?i+1:i-3))) {
1015       if (findcorner_a(6, i, (i<5?i+1:i-3))) cen[0]++;
1016       else erval = ERR_MISPAINTED;
1017     }
1018   }
1019   if (cen[0] > 0 && !erval)
1020     erval = ERR_PARITY_CORNER_BACKWARD;
1021   for (int i = 0; i <= N+1; i++)
1022     for (int j = 0; j <= N+1; j++)
1023       for (int k = 0; k <= N+1; k++)
1024         cube[i][j][k] = tcube[i][j][k];
1025   // the cube appears solvable (unless there's a parity error); try solution
1026   if (erval) return erval;
1027   // step 3(ish) start from each possible orientation to find shortest solution
1028   for (int h = 1; h <= 6; h++)
1029   {
1030     for (int g = 1; g <= 4; g++)
1031     {
1032       for (int i = 0; i <= N+1; i++)
1033         for (int j = 0; j <= N+1; j++)
1034           for (int k = 0; k <= N+1; k++)
1035             tcube[i][j][k] = cube[i][j][k];
1036       // step 4(ish) set up interpolation table so U,D,L,R,F,B=1,2,3,4,5,6
1037       for (int i = 1; i <= 6; i++)
1038         cen[i] = 0;
1039       U = cube[1][N+1][1];
1040       L = cube[0][N][1];
1041       F = cube[1][N][0];
1042       for (int i = 1; i <= 6; i++)
1043       {
1044         if (i != U && i != L && i != F)
1045         {
1046           if      (findcorner_c(F,U,i)) R = i;
1047           else if (findcorner_c(L,F,i)) D = i;
1048           else if (findcorner_c(U,L,i)) B = i;
1049         }
1050       }
1051       // now set the matrix
1052       cen[U] = 1; cen[L] = 2; cen[F] = 3;
1053       cen[R] = 4; cen[B] = 5; cen[D] = 6;
1054       // apply interpolation
1055       for (int i = 1; i <= N; i++)
1056       {
1057         for (int j = 1; j <= N; j++)
1058         {
1059           cube[i][N+1][j] = cen[cube[i][N+1][j]];
1060           cube[0][i][j]   = cen[cube[0][i][j]];
1061           cube[i][j][0]   = cen[cube[i][j][0]];
1062           cube[N+1][i][j] = cen[cube[N+1][i][j]];
1063           cube[i][j][N+1] = cen[cube[i][j][N+1]];
1064           cube[i][0][j]   = cen[cube[i][0][j]];
1065         }
1066       }
1067       if (!erval)
1068       {
1069         // step 5(ish) (FINALLLLLY): find a solution
1070         cursolution = findsolution();
1071         // strip redundancies from solution...
1072         if (shorten >= SHORTEN_STRIP_ALL)
1073         {
1074           string allmov = prefix + cursolution;
1075           int prelen = (int)prefix.length() / 3;
1076           if (prelen == 0) prelen = -1;
1077           cursolution = concise(allmov, prelen);
1078         }
1079         // see if the current solution is shorter than best solution
1080         curmoves = (int)cursolution.length() / 3;
1081         if (curmoves < tmov[0] || tmov[0] < 0)
1082         {
1083           tsolution = cursolution;
1084           for (int i = 1; i <= MOV; i++)
1085             tmov[i] = mov[i];
1086           tmov[0] = curmoves;
1087         }
1088       }
1089       for (int i = 0; i <= N+1; i++)
1090         for (int j = 0; j <= N+1; j++)
1091           for (int k = 0; k <= N+1; k++)
1092             cube[i][j][k] = tcube[i][j][k];
1093       // now try the next orientation
1094       if (shorten < SHORTEN_STRIP_ROTATE_ALL) break;
1095       prefix += "CL."; CL();
1096     }
1097     if (shorten < SHORTEN_STRIP_ROTATE_SOME) break;
1098     if (h % 2) {
1099       prefix += "CU."; CU();
1100     }
1101     else {
1102       prefix += "CA."; CA();
1103     }
1104   }
1105   // step 6(ish) set the members appropriately and return
1106   if (erval) return erval;
1107   for (int i = 0; i <= MOV; i++)
1108     mov[i] = tmov[i];
1109   solution = tsolution;
1110   return 0;
1111 }
1112 // find a solution for a prepared cube
findsolution()1113 const string cu2::findsolution()
1114 {
1115   string s = "";
1116   int step = 0;
1117   // step 1: top corners
1118   {
1119     step++;
1120     string a = "";
1121     int iter = 0;
1122     // fix
1123     while
1124     (!erval &&
1125      !((findcorner_c(1,3,2) == POSY && fx == 1 && fz == 1) &&
1126        (findcorner_c(1,4,3) == POSY && fx == 2 && fz == 1) &&
1127        (findcorner_c(1,5,4) == POSY && fx == 2 && fz == 2) &&
1128        (findcorner_c(1,2,5) == POSY && fx == 1 && fz == 2) ) )
1129     {
1130       for (int i = 1; i <= 4; i++)
1131       {
1132         switch (findcorner_c(1, (i<4?i+2:i-2), (i+1)))
1133         {
1134         case POSY:
1135           if      (fx == 1 && fz == 1) ;
1136           else if (fx == 1 && fz == 2) {
1137             a += "BA.DR.BC.FA.DL.FC.";
1138             BA(); DR(); BC(); FA(); DL(); FC();
1139           }
1140           else if (fx == 2 && fz == 1) {
1141             a += "RD.DL.RU.LD.DR.LU.";
1142             RD(); DL(); RU(); LD(); DR(); LU();
1143           }
1144           else if (fx == 2 && fz == 2) {
1145             a += "BC.DL.BA.DL.LD.DR.LU.";
1146             BC(); DL(); BA(); DL(); LD(); DR(); LU();
1147           }
1148           break;
1149         case NEGY:
1150           if      (fx == 1 && fz == 1) ;
1151           else if (fx == 1 && fz == 2) {
1152             a += "DR.";
1153             DR();
1154           }
1155           else if (fx == 2 && fz == 1) {
1156             a += "DL.";
1157             DL();
1158           }
1159           else if (fx == 2 && fz == 2) {
1160             a += "DL.DL.";
1161             DL(); DL();
1162           }
1163           a += "FA.DR.FC.DL.LD.DL.LU.";
1164           FA(); DR(); FC(); DL(); LD(); DL(); LU();
1165           break;
1166         case NEGX:
1167           if      (fy == 1 && fz == 1) {
1168             a += "LD.DR.LU.";
1169             LD(); DR(); LU();
1170           }
1171           else if (fy == 1 && fz == 2) {
1172             a += "DR.FA.DL.FC.";
1173             DR(); FA(); DL(); FC();
1174           }
1175           else if (fy == 2 && fz == 1) {
1176             a += "LD.DR.LU.DL.LD.DR.LU.";
1177             LD(); DR(); LU(); DL(); LD(); DR(); LU();
1178           }
1179           else if (fy == 2 && fz == 2) {
1180             a += "LU.DL.LD.DL.LD.DL.LU.";
1181             LU(); DL(); LD(); DL(); LD(); DL(); LU();
1182           }
1183           break;
1184         case NEGZ:
1185           if      (fx == 1 && fy == 1) {
1186             a += "FA.DL.FC.";
1187             FA(); DL(); FC();
1188           }
1189           else if (fx == 1 && fy == 2) {
1190             a += "FA.DL.FC.DR.FA.DL.FC.";
1191             FA(); DL(); FC(); DR(); FA(); DL(); FC();
1192           }
1193           else if (fx == 2 && fy == 1) {
1194             a += "DL.LD.DR.LU.";
1195             DL(); LD(); DR(); LU();
1196           }
1197           else if (fx == 2 && fy == 2) {
1198             a += "FC.DR.FA.DR.FA.DR.FC.";
1199             FC(); DR(); FA(); DR(); FA(); DR(); FC();
1200           }
1201           break;
1202         case POSX:
1203           if      (fy == 1 && fz == 1) {
1204             a += "LD.DL.LU.";
1205             LD(); DL(); LU();
1206           }
1207           else if (fy == 1 && fz == 2) {
1208             a += "DR.FA.DR.FC.";
1209             DR(); FA(); DR(); FC();
1210           }
1211           else if (fy == 2 && fz == 1) {
1212             a += "RD.LD.DL.RU.LU.";
1213             RD(); LD(); DL(); RU(); LU();
1214           }
1215           else if (fy == 2 && fz == 2) {
1216             a += "RU.DR.RD.FA.DR.FC.";
1217             RU(); DR(); RD(); FA(); DR(); FC();
1218           }
1219           break;
1220         case POSZ:
1221           if      (fx == 1 && fy == 1) {
1222             a += "FA.DR.FC.";
1223             FA(); DR(); FC();
1224           }
1225           else if (fx == 1 && fy == 2) {
1226             a += "BA.FA.DR.BC.FC.";
1227             BA(); FA(); DR(); BC(); FC();
1228           }
1229           else if (fx == 2 && fy == 1) {
1230             a += "DL.LD.DL.LU.";
1231             DL(); LD(); DL(); LU();
1232           }
1233           else if (fx == 2 && fy == 2) {
1234             a += "BC.DL.BA.LD.DL.LU.";
1235             BC(); DL(); BA(); LD(); DL(); LU();
1236           }
1237           break;
1238         }
1239         a += "CL."; CL();
1240       }
1241       iter++;
1242       if (iter >= ITER_THRESHOLD) erval = ERR_NONDESCRIPT;
1243     }
1244     // check for trouble
1245     if (erval)
1246       return "";
1247     if (shorten >= SHORTEN_STRIP_SOME)
1248       a = concise(a);
1249     mov[step] = a.length() / 3;
1250     s += a;
1251   }
1252   // step 2: bottom corners positioning
1253   {
1254     step++;
1255     string a = "";
1256     int iter = 0;
1257     // fix
1258     int good, corn[4];
1259     good = 0; for (int i = 0; i < 4; i++) corn[i] = 0;
1260     findcorner_c(6,2,3); if (fx <= 1 && fz <= 1) { corn[0]=1; good++; }
1261     findcorner_c(6,3,4); if (fx >= 2 && fz <= 1) { corn[1]=1; good++; }
1262     findcorner_c(6,4,5); if (fx >= 2 && fz >= 2) { corn[2]=1; good++; }
1263     findcorner_c(6,5,2); if (fx <= 1 && fz >= 2) { corn[3]=1; good++; }
1264     for (int i = 1; i <= 4 && good < 2; i++)
1265     {
1266       a += "DR."; DR();
1267       good = 0; for (int j = 0; j < 4; j++) corn[j] = 0;
1268       findcorner_c(6,2,3); if (fx <= 1 && fz <= 1) { corn[0]=1; good++; }
1269       findcorner_c(6,3,4); if (fx >= 2 && fz <= 1) { corn[1]=1; good++; }
1270       findcorner_c(6,4,5); if (fx >= 2 && fz >= 2) { corn[2]=1; good++; }
1271       findcorner_c(6,5,2); if (fx <= 1 && fz >= 2) { corn[3]=1; good++; }
1272     }
1273     //if (good < 2) erval = ERR_NONDESCRIPT;
1274     while (!erval && good < 4)
1275     {
1276       for (int i = 0; i < 4; i++)
1277       {
1278         if (corn[i] && corn[i<3?i+1:i-3])
1279         {
1280           switch (i)
1281           {
1282           case 0: a += "CR.CR."; CR(); CR(); break;
1283           case 1: a += "CR."; CR(); break;
1284           case 2: break;
1285           case 3: a += "CL."; CL(); break;
1286           }
1287           a += "RD.DL.RU.FC.DR.FA.RD.DR.RU.DR.DR.";
1288           RD(); DL(); RU(); FC(); DR(); FA(); RD(); DR(); RU(); DR(); DR();
1289           switch (i)
1290           {
1291           case 0: a += "CL.CL."; CL(); CL(); break;
1292           case 1: a += "CL."; CL(); break;
1293           case 2: break;
1294           case 3: a += "CR."; CR(); break;
1295           }
1296           break;
1297         }
1298         else if (corn[i] && corn[i<2?i+2:i-2])
1299         {
1300           switch (i)
1301           {
1302           case 0: break;
1303           case 1: a += "CL."; CL(); break;
1304           case 2: break;
1305           case 3: a += "CR."; CR(); break;
1306           }
1307           a += "RD.DL.RU.FC.DR.FA.RD.DR.RU.DR.CL."
1308                "RD.DL.RU.FC.DR.FA.RD.DR.RU.DR.DR.CR.";
1309           RD(); DL(); RU(); FC(); DR(); FA(); RD(); DR(); RU(); DR(); CL();
1310           RD(); DL(); RU(); FC(); DR(); FA(); RD(); DR(); RU(); DR(); DR(); CR();
1311           switch (i)
1312           {
1313           case 0: break;
1314           case 1: a += "CR."; CR(); break;
1315           case 2: break;
1316           case 3: a += "CL."; CL(); break;
1317           }
1318           break;
1319         }
1320       }
1321       good = 0; for (int i = 0; i < 4; i++) corn[i] = 0;
1322       findcorner_c(6,2,3); if (fx <= 1 && fz <= 1) { corn[0]=1; good++; }
1323       findcorner_c(6,3,4); if (fx >= 2 && fz <= 1) { corn[1]=1; good++; }
1324       findcorner_c(6,4,5); if (fx >= 2 && fz >= 2) { corn[2]=1; good++; }
1325       findcorner_c(6,5,2); if (fx <= 1 && fz >= 2) { corn[3]=1; good++; }
1326       for (int i = 1; i <= 4 && good < 2; i++)
1327       {
1328         a += "DR."; DR();
1329         good = 0; for (int j = 0; j < 4; j++) corn[j] = 0;
1330         findcorner_c(6,2,3); if (fx <= 1 && fz <= 1) { corn[0]=1; good++; }
1331         findcorner_c(6,3,4); if (fx >= 2 && fz <= 1) { corn[1]=1; good++; }
1332         findcorner_c(6,4,5); if (fx >= 2 && fz >= 2) { corn[2]=1; good++; }
1333         findcorner_c(6,5,2); if (fx <= 1 && fz >= 2) { corn[3]=1; good++; }
1334       }
1335       iter++;
1336       if (iter >= ITER_THRESHOLD) erval = ERR_NONDESCRIPT;
1337     }
1338     // check for trouble
1339     if (erval)
1340       return "";
1341     if (shorten >= SHORTEN_STRIP_SOME)
1342       a = concise(a);
1343     mov[step] = a.length() / 3;
1344     s += a;
1345   }
1346   // step 3: bottom corners orienting
1347   {
1348     step++;
1349     string a = "";
1350     int iter = 0;
1351     // fix
1352     int good, corn[4];
1353     good = 0;
1354     if ((corn[0] = findcorner_c(6,2,3)) == NEGY) good++;
1355     if ((corn[1] = findcorner_c(6,3,4)) == NEGY) good++;
1356     if ((corn[2] = findcorner_c(6,4,5)) == NEGY) good++;
1357     if ((corn[3] = findcorner_c(6,5,2)) == NEGY) good++;
1358     while (!erval && good < 4)
1359     {
1360       if      (good == 3)
1361       {
1362         erval = ERR_PARITY_CORNER_ROTATION;
1363         break;
1364       }
1365       switch (good)
1366       {
1367       case 0:
1368         {
1369         int f = 0;
1370         for (int i = 0; i < 4; i++)
1371         {
1372           if (corn[i] == corn[i>0?i-1:i+3] || corn[i] == -(corn[i>0?i-1:i+3]))
1373           {
1374             f = 1;
1375             switch (i)
1376             {
1377             case 0: a += "CR.CR."; CR(); CR(); break;
1378             case 1: a += "CR."; CR(); break;
1379             case 2: break;
1380             case 3: a += "CL."; CL(); break;
1381             }
1382             if (cube[3][1][1] == 6)
1383             {
1384               a += "RD.DL.DL.RU.DR.RD.DR.RU."
1385                    "LD.DR.DR.LU.DL.LD.DL.LU.";
1386               RD(); DL(); DL(); RU(); DR(); RD(); DR(); RU();
1387               LD(); DR(); DR(); LU(); DL(); LD(); DL(); LU();
1388            }
1389             else // if (cube[2][1][0] == 6)
1390             {
1391               a += "LD.DR.LU.DR.LD.DL.DL.LU."
1392                    "RD.DL.RU.DL.RD.DR.DR.RU.";
1393               LD(); DR(); LU(); DR(); LD(); DL(); DL(); LU();
1394               RD(); DL(); RU(); DL(); RD(); DR(); DR(); RU();
1395             }
1396             switch (i)
1397             {
1398             case 0: a += "CL.CL."; CL(); CL(); break;
1399             case 1: a += "CL."; CL(); break;
1400             case 2: break;
1401             case 3: a += "CR."; CR(); break;
1402             }
1403             break;
1404           }
1405         }
1406         if (!f)
1407         {
1408           erval = ERR_PARITY_CORNER_ROTATION;
1409           /*
1410           // the slightly lazy way.....
1411           a += "RD.DL.RU.DL.RD.DR.DR.RU.DR.DR.";
1412           RD(); DL(); RU(); DL(); RD(); DR(); DR(); RU(); DR(); DR();
1413           */
1414         }
1415         } // ya i know... just so we could squeeze int f inside a case.
1416         break;
1417       case 1:
1418         for (int i = 0; i < 4; i++)
1419         {
1420           if (corn[i] == NEGY)
1421           {
1422             switch (i)
1423             {
1424             case 0: break;
1425             case 1: a += "CL."; CL(); break;
1426             case 2: a += "CR.CR."; CR(); CR(); break;
1427             case 3: a += "CR."; CR(); break;
1428             }
1429             if (cube[2][1][0] == 6)
1430             {
1431               a += "RD.DL.RU.DL.RD.DR.DR.RU.DR.DR.";
1432               RD(); DL(); RU(); DL(); RD(); DR(); DR(); RU(); DR(); DR();
1433             }
1434             else // if (cube[3][1][1] == 6)
1435             {
1436               a += "DL.DL.RD.DL.DL.RU.DR.RD.DR.RU.";
1437               DL(); DL(); RD(); DL(); DL(); RU(); DR(); RD(); DR(); RU();
1438             }
1439             switch (i)
1440             {
1441             case 0: break;
1442             case 1: a += "CR."; CR(); break;
1443             case 2: a += "CL.CL."; CL(); CL(); break;
1444             case 3: a += "CL."; CL(); break;
1445             }
1446             break;
1447           }
1448         }
1449         break;
1450       case 2:
1451         for (int i = 0; i < 4; i++)
1452         {
1453           if (corn[i] == NEGY && corn[i>0?i-1:i+3] == NEGY)
1454           {
1455             switch (i)
1456             {
1457             case 0: break;
1458             case 1: a += "CL."; CL(); break;
1459             case 2: a += "CR.CR."; CR(); CR(); break;
1460             case 3: a += "CR."; CR(); break;
1461             }
1462             if (cube[3][1][1] == 6)
1463             {
1464               a += "RD.DL.DL.RU.DR.RD.DR.RU."
1465                    "LD.DR.DR.LU.DL.LD.DL.LU.";
1466               RD(); DL(); DL(); RU(); DR(); RD(); DR(); RU();
1467               LD(); DR(); DR(); LU(); DL(); LD(); DL(); LU();
1468             }
1469             else // if (cube[2][1][0] == 6)
1470             {
1471               a += "LD.DR.LU.DR.LD.DL.DL.LU."
1472                    "RD.DL.RU.DL.RD.DR.DR.RU.";
1473               LD(); DR(); LU(); DR(); LD(); DL(); DL(); LU();
1474               RD(); DL(); RU(); DL(); RD(); DR(); DR(); RU();
1475             }
1476             switch (i)
1477             {
1478             case 0: break;
1479             case 1: a += "CR."; CR(); break;
1480             case 2: a += "CL.CL."; CL(); CL(); break;
1481             case 3: a += "CL."; CL(); break;
1482             }
1483             break;
1484           }
1485           else if (corn[i] == NEGY && corn[i<2?i+2:i-2] == NEGY)
1486           {
1487             switch (i)
1488             {
1489             case 0: break;
1490             case 1: a += "CL."; CL(); break;
1491             case 2: break;
1492             case 3: a += "CR."; CR(); break;
1493             }
1494             if (cube[2][1][0] == 6)
1495             {
1496               a += "CL.LD.DR.LU.DR.LD.DL.DL.LU."
1497                    "RD.DL.RU.DL.RD.DR.DR.RU."
1498                    "CR.LD.DR.LU.DR.LD.DL.DL.LU."
1499                    "RD.DL.RU.DL.RD.DR.DR.RU.";
1500               CL(); LD(); DR(); LU(); DR(); LD(); DL(); DL(); LU();
1501               RD(); DL(); RU(); DL(); RD(); DR(); DR(); RU();
1502               CR(); LD(); DR(); LU(); DR(); LD(); DL(); DL(); LU();
1503               RD(); DL(); RU(); DL(); RD(); DR(); DR(); RU();
1504             }
1505             else // if (cube[3][1][1] == 6)
1506             {
1507               a += "RD.DL.DL.RU.DR.RD.DR.RU."
1508                    "LD.DR.DR.LU.DL.LD.DL.LU.CL."
1509                    "RD.DL.DL.RU.DR.RD.DR.RU."
1510                    "LD.DR.DR.LU.DL.LD.DL.LU.CR.";
1511               RD(); DL(); DL(); RU(); DR(); RD(); DR(); RU();
1512               LD(); DR(); DR(); LU(); DL(); LD(); DL(); LU(); CL();
1513               RD(); DL(); DL(); RU(); DR(); RD(); DR(); RU();
1514               LD(); DR(); DR(); LU(); DL(); LD(); DL(); LU(); CR();
1515             }
1516             switch (i)
1517             {
1518             case 0: break;
1519             case 1: a += "CR."; CR(); break;
1520             case 2: break;
1521             case 3: a += "CL."; CL(); break;
1522             }
1523             break;
1524           }
1525         }
1526         break;
1527       }
1528       good = 0;
1529       if ((corn[0] = findcorner_c(6,2,3)) == NEGY) good++;
1530       if ((corn[1] = findcorner_c(6,3,4)) == NEGY) good++;
1531       if ((corn[2] = findcorner_c(6,4,5)) == NEGY) good++;
1532       if ((corn[3] = findcorner_c(6,5,2)) == NEGY) good++;
1533       iter++;
1534       if (iter >= ITER_THRESHOLD) erval = ERR_NONDESCRIPT;
1535     }
1536     // check for trouble
1537     if (erval)
1538       return "";
1539     if (shorten >= SHORTEN_STRIP_SOME)
1540       a = concise(a);
1541     mov[step] = a.length() / 3;
1542     s += a;
1543   }
1544   /*
1545   // step X: center rotation
1546   {
1547     step++;
1548     string a = "";
1549     int iter = 0;
1550     // fix
1551     //
1552     // check for trouble
1553     if (erval)
1554       return "";
1555     if (shorten >= SHORTEN_STRIP_SOME)
1556       a = concise(a);
1557     mov[step] = a.length() / 3;
1558     s += a;
1559   }
1560   */
1561   /*
1562   if (!issolved())
1563   {
1564     erval = ERR_NONDESCRIPT;
1565     return "";
1566   }
1567   */
1568   return s;
1569 }
1570 
1571 // end of cu2 class definition
1572 
1573 //
1574