1
2 /*-
3 # X-BASED RUBIK'S CUBE(tm)
4 #
5 # RubikS.c
6 ###
7 #
8 # Taken from code originally written by
9 # Michael B. Martin <martinm@sps1.phys.vt.edu>
10 # From cubist10.c-- for IBM PC.
11 # Used by permission.
12 # Taken from the algorithm in the Ideal Solution book.
13 #
14 # Copyright (c) 1994 - 99 David Albert Bagley, bagleyd@tux.org
15 #
16 # All Rights Reserved
17 #
18 # Permission to use, copy, modify, and distribute this software and
19 # its documentation for any purpose and without fee is hereby granted,
20 # provided that the above copyright notice appear in all copies and
21 # that both that copyright notice and this permission notice appear in
22 # supporting documentation, and that the name of the author not be
23 # used in advertising or publicity pertaining to distribution of the
24 # software without specific, written prior permission.
25 #
26 # This program is distributed in the hope that it will be "playable",
27 # but WITHOUT ANY WARRANTY; without even the implied warranty of
28 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
29 #
30 */
31
32 /* Solver file for Rubik */
33
34 #include <stdio.h>
35 #include <X11/IntrinsicP.h>
36 #include <X11/Intrinsic.h>
37 #include <X11/StringDefs.h>
38 #include <X11/CoreP.h>
39 #include "RubikP.h"
40 #include "Rubik2dP.h"
41 #include "Rubik3dP.h"
42
43 /* Mappings of Ideal notation to my General nxnxn cube notation */
44 #define RotateLeft(w) MoveRubik(w,2,0,LEFT,TRUE)
45 #define RotateRight(w) MoveRubik(w,2,0,RIGHT,TRUE)
46 #define RotateUp(w) MoveRubik(w,2,0,TOP,TRUE)
47 #define RotateDown(w) MoveRubik(w,2,0,BOTTOM,TRUE)
48 #define RotateCw(w) MoveRubik(w,0,0,RIGHT,TRUE)
49 #define RotateCcw(w) MoveRubik(w,0,0,LEFT,TRUE)
50
51 #define RotateTopLeft(w) MoveRubik(w,2,0,LEFT,FALSE)
52 #define RotateCenterLeft(w) MoveRubik(w,2,w->rubik.sizex,LEFT,FALSE)
53 #define RotateBottomLeft(w) MoveRubik(w,2,w->rubik.sizex*(w->rubik.sizex-1),LEFT,FALSE)
54 #define RotateTopRight(w) MoveRubik(w,2,0,RIGHT,FALSE)
55 #define RotateCenterRight(w) MoveRubik(w,2,w->rubik.sizex,RIGHT,FALSE)
56 #define RotateBottomRight(w) MoveRubik(w,2,w->rubik.sizex*(w->rubik.sizex-1),RIGHT,FALSE)
57 #define RotateLeftUp(w) MoveRubik(w,2,0,TOP,FALSE)
58 #define RotateCenterUp(w) MoveRubik(w,2,1,TOP,FALSE)
59 #define RotateRightUp(w) MoveRubik(w,2,w->rubik.sizex-1,TOP,FALSE)
60 #define RotateLeftDown(w) MoveRubik(w,2,0,BOTTOM,FALSE)
61 #define RotateCenterDown(w) MoveRubik(w,2,1,BOTTOM,FALSE)
62 #define RotateRightDown(w) MoveRubik(w,2,w->rubik.sizex-1,BOTTOM,FALSE)
63 #define RotateFrontCw(w) MoveRubik(w,0,w->rubik.sizex*(w->rubik.sizex-1),RIGHT,FALSE)
64 #define RotateFrontCcw(w) MoveRubik(w,0,w->rubik.sizex*(w->rubik.sizex-1),LEFT,FALSE)
65
66 #define BLUE 0
67 #define WHITE 1
68 #define RED 2
69 #define YELLOW 3
70 #define GREEN 4
71 #define ORANGE 5
72
73 #ifdef DEBUG
74 static int mapGeneralToIdeal[MAXFACES] =
75 {5, 4, 1, 2, 6, 3};
76
77 #endif
78 static int mapIdealToGeneral[MAXFACES] =
79 {2, 3, 5, 1, 0, 4}; /* Remember to subtract 1 */
80
81 static int Side(RubikWidget w, int m, int c);
82 static int FindCorner(RubikWidget w, int color1, int color2, int color3);
83 static int FindEdge(RubikWidget w, int color1, int color2);
84 static void PlaceEdge(RubikWidget w, int edge, int top_color);
85 static void SolveTop(RubikWidget w);
86 static void AlignCorners(RubikWidget w);
87 static void SwapBottomCorners(RubikWidget w);
88 static void SolveBottom(RubikWidget w);
89 static void Solve_2_2(RubikWidget w);
90 static void SolveBottomEdges(RubikWidget w);
91 static void AlignLastEdge(RubikWidget w);
92 static void ColorAlignFront(RubikWidget w);
93 static void AlignEdges(RubikWidget w);
94 static void ShuffleEdges(RubikWidget w);
95 static void RecolorTopEdges(RubikWidget w);
96
97 static int
Side(RubikWidget w,int m,int c)98 Side(RubikWidget w, int m, int c)
99 {
100 int d, i, j;
101
102 d = mapIdealToGeneral[m - 1];
103 i = c % 3;
104 j = c / 3;
105 if (i == 2)
106 i = w->rubik.sizex - 1;
107 if (j == 2)
108 j = w->rubik.sizex - 1;
109 return w->rubik.cubeLoc[d][j * w->rubik.sizex + i].face;
110 }
111
112 /* This procedure finds the location of a specified corner. An */
113 /* improperly-specified color combination will result in a return */
114 /* value of 9. */
115 static int
FindCorner(RubikWidget w,int color1,int color2,int color3)116 FindCorner(RubikWidget w, int color1, int color2, int color3)
117 {
118 int corner = 0, temp = 1;
119
120 do {
121 if (Side(w, 5, 6) == color1) {
122 if (Side(w, 1, 0) == color2)
123 if (Side(w, 4, 2) == color3)
124 corner = temp;
125 } else if (Side(w, 5, 6) == color2) {
126 if (Side(w, 1, 0) == color3)
127 if (Side(w, 4, 2) == color1)
128 corner = temp;
129 } else if (Side(w, 5, 6) == color3) {
130 if (Side(w, 1, 0) == color1)
131 if (Side(w, 4, 2) == color2)
132 corner = temp;
133 }
134 if (corner == 0) {
135 if (temp < 4)
136 RotateLeft(w);
137 else if (temp == 4) {
138 RotateCw(w);
139 RotateCw(w);
140 } else if (temp < 8)
141 RotateRight(w);
142 else if (temp == 8)
143 corner = 9;
144 temp++;
145 }
146 } while (corner == 0);
147
148 /* put the cube back to the way it was */
149 if (corner == 2)
150 RotateRight(w);
151 else if (corner == 3) {
152 RotateRight(w);
153 RotateRight(w);
154 } else if (corner == 4)
155 RotateLeft(w);
156 else if (corner == 5) {
157 RotateCw(w);
158 RotateCw(w);
159 RotateLeft(w);
160 } else if (corner == 6) {
161 RotateCw(w);
162 RotateCw(w);
163 } else if (corner == 7) {
164 RotateCw(w);
165 RotateCw(w);
166 RotateRight(w);
167 } else if (corner == 8) {
168 RotateCw(w);
169 RotateCw(w);
170 RotateRight(w);
171 RotateRight(w);
172 }
173 return (corner);
174 }
175
176 /* This procedure finds the location of a specified edge. An */
177 /* improperly-specified color combination will result in a return */
178 /* value of 13. */
179 static int
FindEdge(RubikWidget w,int color1,int color2)180 FindEdge(RubikWidget w, int color1, int color2)
181 {
182 int edge = 0, temp = 1;
183
184 do {
185 if (Side(w, 5, 7) == color1) {
186 if (Side(w, 1, 1) == color2)
187 edge = temp;
188 } else if (Side(w, 5, 7) == color2) {
189 if (Side(w, 1, 1) == color1)
190 edge = temp;
191 }
192 if (edge == 0) {
193 if (temp < 4)
194 RotateLeft(w);
195 else if (temp == 4) {
196 RotateLeft(w);
197 RotateCw(w);
198 } else if (temp < 8)
199 RotateUp(w);
200 else if (temp == 8) {
201 RotateUp(w);
202 RotateCw(w);
203 } else if (temp < 12)
204 RotateRight(w);
205 else if (temp == 12)
206 edge = 13; /* end condition, just in case */
207 temp++;
208 }
209 } while (edge == 0);
210
211 /* put the cube back to the way it was */
212 if (edge == 2) {
213 RotateRight(w);
214 } else if (edge == 3) {
215 RotateRight(w);
216 RotateRight(w);
217 } else if (edge == 4) {
218 RotateLeft(w);
219 } else if (edge == 5) {
220 RotateCcw(w);
221 } else if (edge == 6) {
222 RotateCcw(w);
223 RotateRight(w);
224 } else if (edge == 7) {
225 RotateCcw(w);
226 RotateRight(w);
227 RotateRight(w);
228 } else if (edge == 8) {
229 RotateCcw(w);
230 RotateLeft(w);
231 } else if (edge == 9) {
232 RotateCcw(w);
233 RotateCcw(w);
234 } else if (edge == 10) {
235 RotateCcw(w);
236 RotateCcw(w);
237 RotateRight(w);
238 } else if (edge == 11) {
239 RotateUp(w);
240 RotateUp(w);
241 } else if (edge == 12) {
242 RotateUp(w);
243 RotateUp(w);
244 RotateRight(w);
245 }
246 return (edge);
247 }
248
249 /* This procedure places the specified edge piece in edge position */
250 /* #1 (front top). */
251 static void
PlaceEdge(RubikWidget w,int edge,int top_color)252 PlaceEdge(RubikWidget w, int edge, int top_color)
253 {
254 /* first put the edge piece in position #8 (center row, left rear) */
255 if (edge == 1) {
256 if (Side(w, 5, 7) == top_color)
257 return; /* already in place */
258 else {
259 RotateFrontCcw(w);
260 RotateCenterLeft(w);
261 RotateFrontCw(w);
262 }
263 } else if (edge == 2) {
264 RotateTopLeft(w);
265 RotateFrontCcw(w);
266 RotateCenterLeft(w);
267 RotateFrontCw(w);
268 RotateTopRight(w);
269 } else if (edge == 3) {
270 RotateTopLeft(w);
271 RotateTopLeft(w);
272 RotateFrontCcw(w);
273 RotateCenterLeft(w);
274 RotateFrontCw(w);
275 RotateTopRight(w);
276 RotateTopRight(w);
277 } else if (edge == 4) {
278 RotateTopRight(w);
279 RotateFrontCcw(w);
280 RotateCenterLeft(w);
281 RotateFrontCw(w);
282 RotateTopLeft(w);
283 } else if (edge == 5) {
284 RotateCenterLeft(w);
285 } else if (edge == 6) {
286 RotateCenterLeft(w);
287 RotateCenterLeft(w);
288 } else if (edge == 7) {
289 RotateCenterRight(w);
290 } else if (edge == 9) {
291 RotateFrontCw(w);
292 RotateCenterLeft(w);
293 RotateFrontCcw(w);
294 } else if (edge == 10) {
295 RotateBottomLeft(w);
296 RotateFrontCw(w);
297 RotateCenterLeft(w);
298 RotateFrontCcw(w);
299 RotateBottomRight(w);
300 } else if (edge == 11) {
301 RotateBottomLeft(w);
302 RotateBottomLeft(w);
303 RotateFrontCw(w);
304 RotateCenterLeft(w);
305 RotateFrontCcw(w);
306 RotateBottomRight(w);
307 RotateBottomRight(w);
308 } else if (edge == 12) {
309 RotateBottomRight(w);
310 RotateFrontCw(w);
311 RotateCenterLeft(w);
312 RotateFrontCcw(w);
313 RotateBottomLeft(w);
314 }
315 /* put the piece in place */
316 if (Side(w, 4, 3) == top_color) {
317 RotateFrontCw(w);
318 RotateCenterRight(w);
319 RotateCenterRight(w);
320 RotateFrontCcw(w);
321 } else {
322 RotateFrontCcw(w);
323 RotateCenterRight(w);
324 RotateFrontCw(w);
325 }
326 }
327
328 /* This procedure solves the top (BLUE) side, except for one edge. */
329 static void
SolveTop(RubikWidget w)330 SolveTop(RubikWidget w)
331 {
332 int corner, edge;
333
334 /* put the blue face on the top */
335 if (Side(w, 1, 4) == BLUE)
336 RotateUp(w);
337 else if (Side(w, 2, 4) == BLUE)
338 RotateCcw(w);
339 else if (Side(w, 3, 4) == BLUE)
340 RotateDown(w);
341 else if (Side(w, 4, 4) == BLUE)
342 RotateCw(w);
343 else if (Side(w, 6, 4) == BLUE) {
344 RotateUp(w);
345 RotateUp(w);
346 }
347 /* first find the blue-red-white corner and place it */
348 corner = FindCorner(w, BLUE, RED, WHITE);
349 if (corner == 1) {
350 if (Side(w, 5, 6) == RED) {
351 RotateFrontCw(w);
352 RotateTopLeft(w);
353 } else if (Side(w, 5, 6) == WHITE) {
354 RotateLeftUp(w);
355 RotateTopRight(w);
356 }
357 } else if (corner == 2) {
358 if (Side(w, 5, 8) == BLUE)
359 RotateTopLeft(w);
360 else if (Side(w, 5, 8) == RED) {
361 RotateRightUp(w);
362 RotateTopLeft(w);
363 RotateTopLeft(w);
364 } else if (Side(w, 5, 8) == WHITE)
365 RotateFrontCcw(w);
366 } else if (corner == 3) {
367 if (Side(w, 5, 2) == BLUE) {
368 RotateTopLeft(w);
369 RotateTopLeft(w);
370 } else if (Side(w, 5, 2) == RED) {
371 RotateTopRight(w);
372 RotateLeftDown(w);
373 } else if (Side(w, 5, 2) == WHITE) {
374 RotateRightDown(w);
375 RotateTopLeft(w);
376 }
377 } else if (corner == 4) {
378 if (Side(w, 5, 0) == BLUE)
379 RotateTopRight(w);
380 else if (Side(w, 5, 0) == RED)
381 RotateLeftDown(w);
382 else if (Side(w, 5, 0) == WHITE) {
383 RotateTopRight(w);
384 RotateLeftUp(w);
385 RotateTopRight(w);
386 }
387 } else if (corner == 5) {
388 if (Side(w, 6, 0) == BLUE) {
389 RotateBottomLeft(w);
390 RotateLeftUp(w);
391 RotateLeftUp(w);
392 } else if (Side(w, 6, 0) == RED)
393 RotateLeftUp(w);
394 else if (Side(w, 6, 0) == WHITE)
395 RotateFrontCw(w);
396 } else if (corner == 6) {
397 if (Side(w, 6, 2) == BLUE) {
398 RotateFrontCw(w);
399 RotateFrontCw(w);
400 } else if (Side(w, 6, 2) == RED) {
401 RotateBottomLeft(w);
402 RotateLeftUp(w);
403 } else if (Side(w, 6, 2) == WHITE) {
404 RotateBottomLeft(w);
405 RotateFrontCw(w);
406 }
407 } else if (corner == 7) {
408 if (Side(w, 6, 8) == BLUE) {
409 RotateBottomLeft(w);
410 RotateFrontCw(w);
411 RotateFrontCw(w);
412 } else if (Side(w, 6, 8) == RED) {
413 RotateBottomLeft(w);
414 RotateBottomLeft(w);
415 RotateLeftUp(w);
416 } else if (Side(w, 6, 8) == WHITE) {
417 RotateBottomLeft(w);
418 RotateBottomLeft(w);
419 RotateFrontCw(w);
420 }
421 } else if (corner == 8) {
422 if (Side(w, 6, 6) == BLUE) {
423 RotateLeftUp(w);
424 RotateLeftUp(w);
425 } else if (Side(w, 6, 6) == RED) {
426 RotateBottomRight(w);
427 RotateLeftUp(w);
428 } else if (Side(w, 6, 6) == WHITE) {
429 RotateBottomRight(w);
430 RotateFrontCw(w);
431 }
432 }
433 /* now find the blue-yellow-red corner and place it */
434 RotateLeft(w);
435 corner = FindCorner(w, BLUE, YELLOW, RED);
436 if (corner == 1) {
437 if (Side(w, 5, 6) == YELLOW) {
438 RotateFrontCcw(w);
439 RotateBottomRight(w);
440 RotateFrontCcw(w);
441 RotateFrontCcw(w);
442 } else if (Side(w, 5, 6) == RED) {
443 RotateFrontCw(w);
444 RotateFrontCw(w);
445 RotateBottomLeft(w);
446 RotateFrontCw(w);
447 }
448 } else if (corner == 2) {
449 if (Side(w, 5, 8) == BLUE) {
450 RotateRightDown(w);
451 RotateBottomLeft(w);
452 RotateFrontCw(w);
453 } else if (Side(w, 5, 8) == YELLOW) {
454 RotateRightDown(w);
455 RotateFrontCw(w);
456 RotateFrontCw(w);
457 } else if (Side(w, 5, 8) == RED)
458 RotateFrontCcw(w);
459 } else if (corner == 3) {
460 if (Side(w, 5, 2) == BLUE) {
461 RotateRightDown(w);
462 RotateRightDown(w);
463 RotateFrontCw(w);
464 RotateFrontCw(w);
465 } else if (Side(w, 5, 2) == YELLOW) {
466 RotateRightDown(w);
467 RotateFrontCcw(w);
468 } else if (Side(w, 5, 2) == RED) {
469 RotateRightDown(w);
470 RotateRightDown(w);
471 RotateBottomLeft(w);
472 RotateFrontCw(w);
473 }
474 } else if (corner == 5) {
475 if (Side(w, 6, 0) == BLUE) {
476 RotateBottomRight(w);
477 RotateFrontCw(w);
478 RotateFrontCw(w);
479 } else if (Side(w, 6, 0) == YELLOW) {
480 RotateBottomRight(w);
481 RotateRightUp(w);
482 RotateFrontCcw(w);
483 } else if (Side(w, 6, 0) == RED)
484 RotateFrontCw(w);
485 } else if (corner == 6) {
486 if (Side(w, 6, 2) == BLUE) {
487 RotateFrontCw(w);
488 RotateFrontCw(w);
489 } else if (Side(w, 6, 2) == YELLOW) {
490 RotateRightUp(w);
491 RotateFrontCcw(w);
492 } else if (Side(w, 6, 2) == RED) {
493 RotateBottomLeft(w);
494 RotateFrontCw(w);
495 }
496 } else if (corner == 7) {
497 if (Side(w, 6, 8) == BLUE) {
498 RotateBottomLeft(w);
499 RotateFrontCw(w);
500 RotateFrontCw(w);
501 } else if (Side(w, 6, 8) == YELLOW) {
502 RotateBottomLeft(w);
503 RotateRightUp(w);
504 RotateFrontCcw(w);
505 } else if (Side(w, 6, 8) == RED) {
506 RotateBottomLeft(w);
507 RotateBottomLeft(w);
508 RotateFrontCw(w);
509 }
510 } else if (corner == 8) {
511 if (Side(w, 6, 6) == BLUE) {
512 RotateBottomRight(w);
513 RotateBottomRight(w);
514 RotateFrontCw(w);
515 RotateFrontCw(w);
516 } else if (Side(w, 6, 6) == YELLOW) {
517 RotateBottomRight(w);
518 RotateBottomRight(w);
519 RotateRightUp(w);
520 RotateFrontCcw(w);
521 } else if (Side(w, 6, 6) == RED) {
522 RotateBottomRight(w);
523 RotateFrontCw(w);
524 }
525 }
526 /* now find the blue-orange-yellow corner and place it */
527 RotateLeft(w);
528 corner = FindCorner(w, BLUE, ORANGE, YELLOW);
529 if (corner == 1) {
530 if (Side(w, 5, 6) == ORANGE) {
531 RotateFrontCcw(w);
532 RotateBottomRight(w);
533 RotateFrontCcw(w);
534 RotateFrontCcw(w);
535 } else if (Side(w, 5, 6) == YELLOW) {
536 RotateFrontCw(w);
537 RotateFrontCw(w);
538 RotateBottomLeft(w);
539 RotateFrontCw(w);
540 }
541 } else if (corner == 2) {
542 if (Side(w, 5, 8) == BLUE) {
543 RotateRightDown(w);
544 RotateBottomLeft(w);
545 RotateRightUp(w);
546 RotateFrontCw(w);
547 } else if (Side(w, 5, 8) == ORANGE) {
548 RotateFrontCw(w);
549 RotateBottomLeft(w);
550 RotateFrontCw(w);
551 } else if (Side(w, 5, 8) == YELLOW)
552 RotateFrontCcw(w);
553 } else if (corner == 5) {
554 if (Side(w, 6, 0) == BLUE) {
555 RotateBottomRight(w);
556 RotateFrontCw(w);
557 RotateFrontCw(w);
558 } else if (Side(w, 6, 0) == ORANGE) {
559 RotateRightDown(w);
560 RotateBottomRight(w);
561 RotateRightUp(w);
562 RotateFrontCcw(w);
563 } else if (Side(w, 6, 0) == YELLOW)
564 RotateFrontCw(w);
565 } else if (corner == 6) {
566 if (Side(w, 6, 2) == BLUE) {
567 RotateFrontCw(w);
568 RotateFrontCw(w);
569 } else if (Side(w, 6, 2) == ORANGE) {
570 RotateBottomLeft(w);
571 RotateRightDown(w);
572 RotateBottomRight(w);
573 RotateRightUp(w);
574 RotateFrontCcw(w);
575 } else if (Side(w, 6, 2) == YELLOW) {
576 RotateBottomLeft(w);
577 RotateFrontCw(w);
578 }
579 } else if (corner == 7) {
580 if (Side(w, 6, 8) == BLUE) {
581 RotateBottomLeft(w);
582 RotateFrontCw(w);
583 RotateFrontCw(w);
584 } else if (Side(w, 6, 8) == ORANGE) {
585 RotateBottomLeft(w);
586 RotateBottomLeft(w);
587 RotateRightDown(w);
588 RotateBottomRight(w);
589 RotateRightUp(w);
590 RotateFrontCcw(w);
591 } else if (Side(w, 6, 8) == YELLOW) {
592 RotateBottomLeft(w);
593 RotateBottomLeft(w);
594 RotateFrontCw(w);
595 }
596 } else if (corner == 8) {
597 if (Side(w, 6, 6) == BLUE) {
598 RotateBottomRight(w);
599 RotateBottomRight(w);
600 RotateFrontCw(w);
601 RotateFrontCw(w);
602 } else if (Side(w, 6, 6) == ORANGE) {
603 RotateRightDown(w);
604 RotateBottomRight(w);
605 RotateBottomRight(w);
606 RotateRightUp(w);
607 RotateFrontCcw(w);
608 } else if (Side(w, 6, 6) == YELLOW) {
609 RotateBottomRight(w);
610 RotateFrontCw(w);
611 }
612 }
613 /* and now find the blue-white-orange corner and place it */
614 RotateLeft(w);
615 corner = FindCorner(w, BLUE, WHITE, ORANGE);
616 if (corner == 1) {
617 if (Side(w, 5, 6) == WHITE) {
618 RotateLeftDown(w);
619 RotateBottomRight(w);
620 RotateLeftUp(w);
621 RotateBottomLeft(w);
622 RotateBottomLeft(w);
623 RotateFrontCcw(w);
624 RotateBottomRight(w);
625 RotateFrontCw(w);
626 } else if (Side(w, 5, 6) == ORANGE) {
627 RotateFrontCcw(w);
628 RotateBottomLeft(w);
629 RotateFrontCw(w);
630 RotateBottomRight(w);
631 RotateBottomRight(w);
632 RotateLeftDown(w);
633 RotateBottomLeft(w);
634 RotateLeftUp(w);
635 }
636 } else if (corner == 5) {
637 if (Side(w, 6, 0) == BLUE) {
638 RotateBottomRight(w);
639 RotateLeftDown(w);
640 RotateBottomLeft(w);
641 RotateBottomLeft(w);
642 RotateLeftUp(w);
643 RotateBottomRight(w);
644 RotateLeftDown(w);
645 RotateBottomLeft(w);
646 RotateLeftUp(w);
647 } else if (Side(w, 6, 0) == WHITE) {
648 RotateBottomRight(w);
649 RotateLeftDown(w);
650 RotateBottomLeft(w);
651 RotateLeftUp(w);
652 } else if (Side(w, 6, 0) == ORANGE) {
653 RotateBottomLeft(w);
654 RotateFrontCcw(w);
655 RotateBottomRight(w);
656 RotateFrontCw(w);
657 }
658 } else if (corner == 6) {
659 if (Side(w, 6, 2) == BLUE) {
660 RotateBottomRight(w);
661 RotateFrontCcw(w);
662 RotateBottomLeft(w);
663 RotateFrontCw(w);
664 RotateBottomLeft(w);
665 RotateFrontCcw(w);
666 RotateBottomRight(w);
667 RotateFrontCw(w);
668 } else if (Side(w, 6, 2) == WHITE) {
669 RotateLeftDown(w);
670 RotateBottomLeft(w);
671 RotateLeftUp(w);
672 } else if (Side(w, 6, 2) == ORANGE) {
673 RotateBottomLeft(w);
674 RotateBottomLeft(w);
675 RotateFrontCcw(w);
676 RotateBottomRight(w);
677 RotateFrontCw(w);
678 }
679 } else if (corner == 7) {
680 if (Side(w, 6, 8) == BLUE) {
681 RotateLeftDown(w);
682 RotateBottomRight(w);
683 RotateLeftUp(w);
684 RotateBottomRight(w);
685 RotateLeftDown(w);
686 RotateBottomLeft(w);
687 RotateLeftUp(w);
688 } else if (Side(w, 6, 8) == WHITE) {
689 RotateLeftDown(w);
690 RotateBottomLeft(w);
691 RotateBottomLeft(w);
692 RotateLeftUp(w);
693 } else if (Side(w, 6, 8) == ORANGE) {
694 RotateFrontCcw(w);
695 RotateBottomLeft(w);
696 RotateBottomLeft(w);
697 RotateFrontCw(w);
698 }
699 } else if (corner == 8) {
700 if (Side(w, 6, 6) == BLUE) {
701 RotateFrontCcw(w);
702 RotateBottomRight(w);
703 RotateBottomRight(w);
704 RotateFrontCw(w);
705 RotateBottomLeft(w);
706 RotateFrontCcw(w);
707 RotateBottomRight(w);
708 RotateFrontCw(w);
709 } else if (Side(w, 6, 6) == WHITE) {
710 RotateBottomRight(w);
711 RotateBottomRight(w);
712 RotateLeftDown(w);
713 RotateBottomLeft(w);
714 RotateLeftUp(w);
715 } else if (Side(w, 6, 6) == ORANGE) {
716 RotateFrontCcw(w);
717 RotateBottomRight(w);
718 RotateFrontCw(w);
719 }
720 }
721 RotateLeft(w);
722
723 /* find the blue-red edge and place it */
724 edge = FindEdge(w, BLUE, RED);
725 PlaceEdge(w, edge, BLUE);
726 RotateLeft(w);
727
728 /* find the blue-yellow edge and place it */
729 edge = FindEdge(w, BLUE, YELLOW);
730 PlaceEdge(w, edge, BLUE);
731 RotateLeft(w);
732
733 /* find the blue-orange edge and place it */
734 edge = FindEdge(w, BLUE, ORANGE);
735 PlaceEdge(w, edge, BLUE);
736 RotateLeft(w);
737
738 RotateUp(w); /* put the blue side to the back */
739 }
740
741 /* This procedure places the front (GREEN) four corners into */
742 /* their correct positions. */
743 static void
AlignCorners(RubikWidget w)744 AlignCorners(RubikWidget w)
745 {
746 int corner;
747
748 /* find and place the green-orange-white corner (upper left) */
749 corner = FindCorner(w, GREEN, ORANGE, WHITE);
750 if (corner == 2)
751 RotateFrontCcw(w);
752 else if (corner == 5)
753 RotateFrontCw(w);
754 else if (corner == 6) {
755 RotateFrontCw(w);
756 RotateFrontCw(w);
757 }
758 /* find and place the green-yellow-orange corner (lower left) */
759 corner = FindCorner(w, GREEN, YELLOW, ORANGE);
760 if (corner == 2) {
761 RotateCw(w);
762 SwapBottomCorners(w);
763 RotateCcw(w);
764 SwapBottomCorners(w);
765 } else if (corner == 6)
766 SwapBottomCorners(w);
767
768 /* find and place the green-red-yellow corner (lower right) */
769 corner = FindCorner(w, GREEN, RED, YELLOW);
770 if (corner == 2) {
771 RotateCw(w);
772 SwapBottomCorners(w);
773 RotateCcw(w);
774 }
775 }
776
777 /* This procedure swaps the the bottom front corners. */
778 static void
SwapBottomCorners(RubikWidget w)779 SwapBottomCorners(RubikWidget w)
780 {
781 RotateTopRight(w);
782 RotateFrontCw(w);
783 RotateTopLeft(w);
784 RotateLeftUp(w);
785 RotateTopLeft(w);
786 RotateLeftDown(w);
787 RotateTopRight(w);
788 RotateFrontCw(w);
789 RotateFrontCw(w);
790 }
791
792 /* This procedure completes the GREEN side by color-aligning the GREEN */
793 /* corners and putting the GREEN edges in place. */
794 static void
SolveBottom(RubikWidget w)795 SolveBottom(RubikWidget w)
796 {
797 int aligned;
798
799 /* the GREEN corners (currently in the front) should now be in their */
800 /* proper locations; next, we color align them, and then move the */
801 /* bottom edges into place */
802 do {
803 aligned = 0;
804 if (Side(w, 1, 0) == GREEN)
805 aligned++;
806 if (Side(w, 1, 2) == GREEN)
807 aligned++;
808 if (Side(w, 1, 6) == GREEN)
809 aligned++;
810 if (Side(w, 1, 8) == GREEN)
811 aligned++;
812
813 if (aligned == 0) {
814 ColorAlignFront(w);
815 } else if (aligned == 1) {
816 /* place aligned corner in upper right */
817 if (Side(w, 1, 0) == GREEN)
818 RotateFrontCw(w);
819 if (Side(w, 1, 6) == GREEN) {
820 RotateFrontCw(w);
821 RotateFrontCw(w);
822 }
823 if (Side(w, 1, 8) == GREEN)
824 RotateFrontCcw(w);
825 ColorAlignFront(w);
826 } else if (aligned == 2) {
827 if (Side(w, 1, 0) != GREEN)
828 RotateFrontCw(w);
829 else if (Side(w, 1, 2) == GREEN)
830 RotateFrontCw(w);
831 if (Side(w, 1, 0) != GREEN)
832 RotateFrontCw(w);
833 ColorAlignFront(w);
834 } else if (aligned == 3) /* not sure if this is possible */
835 ColorAlignFront(w);
836 } while (aligned < 4);
837 }
838
839 static void
Solve_2_2(RubikWidget w)840 Solve_2_2(RubikWidget w)
841 {
842 int i;
843
844 for (i = 0; i < 3; i++) /* This is not always efficient */
845 if (!CheckSolved(w))
846 RotateFrontCw(w);
847 }
848
849 static void
SolveBottomEdges(RubikWidget w)850 SolveBottomEdges(RubikWidget w)
851 {
852 int edge, color;
853
854 /* next we move the bottom edges into place */
855 RotateDown(w); /* put the green face on top */
856 RotateCw(w);
857 RotateCw(w);
858
859 color = Side(w, 1, 0); /* get upper front corner color */
860 edge = FindEdge(w, GREEN, color);
861 PlaceEdge(w, edge, GREEN);
862 RotateTopRight(w);
863
864 color = Side(w, 1, 0); /* get upper front corner color */
865 edge = FindEdge(w, GREEN, color);
866 PlaceEdge(w, edge, GREEN);
867 RotateTopRight(w);
868
869 color = Side(w, 1, 0); /* get upper front corner color */
870 edge = FindEdge(w, GREEN, color);
871 PlaceEdge(w, edge, GREEN);
872 RotateTopRight(w);
873
874 color = Side(w, 1, 0); /* get upper front corner color */
875 edge = FindEdge(w, GREEN, color);
876 PlaceEdge(w, edge, GREEN);
877 RotateTopRight(w);
878
879 /* now, align the fourth blue edge piece (if necessary) */
880 RotateCw(w);
881 RotateCw(w);
882 edge = FindEdge(w, BLUE, WHITE);
883 if (edge == 1) {
884 if (Side(w, 1, 1) == BLUE) {
885 RotateFrontCcw(w);
886 RotateCenterLeft(w);
887 RotateFrontCw(w);
888 RotateCenterLeft(w);
889 RotateFrontCw(w);
890 RotateCenterLeft(w);
891 RotateFrontCcw(w);
892 }
893 } else {
894 if (edge == 5)
895 RotateCenterRight(w);
896 else if (edge == 7)
897 RotateCenterLeft(w);
898 else if (edge == 8) {
899 RotateCenterRight(w);
900 RotateCenterRight(w);
901 }
902 AlignLastEdge(w);
903 }
904 }
905
906 /* This procedure moves the remaining BLUE edge piece into position */
907 /* from edge position #6. */
908 static void
AlignLastEdge(RubikWidget w)909 AlignLastEdge(RubikWidget w)
910 {
911 /* edge piece should be in edge position #6 */
912 /* check its orientation and decide which sequence to perform */
913 if (Side(w, 1, 5) == BLUE) {
914 RotateCenterLeft(w);
915 RotateFrontCw(w);
916 RotateCenterRight(w);
917 RotateFrontCcw(w);
918 RotateCenterLeft(w);
919 RotateFrontCcw(w);
920 RotateCenterRight(w);
921 RotateFrontCw(w);
922 } else {
923 RotateFrontCcw(w);
924 RotateCenterLeft(w);
925 RotateFrontCw(w);
926 RotateCenterRight(w);
927 RotateFrontCw(w);
928 RotateCenterLeft(w);
929 RotateFrontCcw(w);
930 }
931 }
932
933 /* This procedure aligns the bottom corner colors (may need to be repeated). */
934 static void
ColorAlignFront(RubikWidget w)935 ColorAlignFront(RubikWidget w)
936 {
937 RotateTopRight(w);
938 RotateFrontCw(w);
939 RotateFrontCw(w);
940 RotateTopLeft(w);
941 RotateFrontCw(w);
942 RotateTopRight(w);
943 RotateFrontCw(w);
944 RotateTopLeft(w);
945 RotateFrontCw(w);
946 RotateFrontCw(w);
947 }
948
949 /* This procedure completes the solution process by placing the */
950 /* remaining edges in place and alignment. */
951 static void
AlignEdges(RubikWidget w)952 AlignEdges(RubikWidget w)
953 {
954 int aligned, color, edge;
955
956 /* move the red side to the front */
957 if (Side(w, 1, 4) == YELLOW)
958 RotateRight(w);
959 else if (Side(w, 1, 4) == ORANGE) {
960 RotateRight(w);
961 RotateRight(w);
962 } else if (Side(w, 1, 4) == WHITE)
963 RotateLeft(w);
964
965 /* rotate the top until its aligned with the center colors */
966 edge = FindEdge(w, BLUE, RED);
967 if (edge == 2)
968 RotateTopLeft(w);
969 else if (edge == 3) {
970 RotateTopLeft(w);
971 RotateTopLeft(w);
972 } else if (edge == 4)
973 RotateTopRight(w);
974
975 /* rotate the bottom until its aligned with the center colors */
976 edge = FindEdge(w, GREEN, RED);
977 if (edge == 10)
978 RotateBottomLeft(w);
979 else if (edge == 11) {
980 RotateBottomLeft(w);
981 RotateBottomLeft(w);
982 } else if (edge == 12)
983 RotateBottomRight(w);
984
985 if (CheckSolved(w))
986 return;
987
988 RotateCcw(w); /* place unaligned edges vertically */
989
990 /* see if any edges are in correct position */
991 aligned = 0;
992 edge = FindEdge(w, RED, YELLOW);
993 if (edge == 1)
994 aligned++;
995 edge = FindEdge(w, YELLOW, ORANGE);
996 if (edge == 3)
997 aligned++;
998 edge = FindEdge(w, ORANGE, WHITE);
999 if (edge == 11)
1000 aligned++;
1001 edge = FindEdge(w, WHITE, RED);
1002 if (edge == 9)
1003 aligned++;
1004
1005 if (aligned == 0) {
1006 ShuffleEdges(w); /* put one edge into position */
1007 aligned++;
1008 }
1009 if (aligned == 1) {
1010 /* find the correct piece and move it to the back bottom edge */
1011 edge = FindEdge(w, RED, YELLOW);
1012 if (edge == 1) {
1013 RotateDown(w);
1014 RotateDown(w);
1015 } else {
1016 edge = FindEdge(w, YELLOW, ORANGE);
1017 if (edge == 3)
1018 RotateUp(w);
1019 else {
1020 edge = FindEdge(w, WHITE, RED);
1021 if (edge == 9)
1022 RotateDown(w);
1023 }
1024 }
1025
1026 /* shuffle */
1027 color = Side(w, 1, 4);
1028 if (Side(w, 1, 7) == color) {
1029 RotateRight(w);
1030 RotateRight(w);
1031 RotateDown(w);
1032 ShuffleEdges(w);
1033 } else if (Side(w, 6, 1) == color) {
1034 RotateRight(w);
1035 RotateRight(w);
1036 RotateDown(w);
1037 ShuffleEdges(w);
1038 } else
1039 ShuffleEdges(w);
1040 }
1041 /* pieces should be in place; complete color alignment */
1042 /* find number of unaligned edge pieces and fix them */
1043 aligned = 0;
1044 if (Side(w, 1, 1) == Side(w, 1, 4))
1045 aligned++;
1046 if (Side(w, 1, 7) == Side(w, 1, 4))
1047 aligned++;
1048 if (Side(w, 3, 1) == Side(w, 3, 4))
1049 aligned++;
1050 if (Side(w, 3, 7) == Side(w, 3, 4))
1051 aligned++;
1052 if (aligned == 0) {
1053 RecolorTopEdges(w);
1054 RotateDown(w);
1055 RotateDown(w);
1056 RecolorTopEdges(w);
1057 } else if (aligned == 2) {
1058 if (Side(w, 1, 1) == Side(w, 1, 4))
1059 do {
1060 RotateDown(w);
1061 } while (Side(w, 1, 1) == Side(w, 1, 4));
1062 if (Side(w, 1, 7) != Side(w, 1, 4))
1063 RotateUp(w);
1064 RecolorTopEdges(w);
1065 if (!CheckSolved(w)) {
1066 RotateDown(w);
1067 RecolorTopEdges(w);
1068 }
1069 }
1070 }
1071
1072 /* This procedure "shuffles" the three center edges on the front and */
1073 /* top faces. */
1074 static void
ShuffleEdges(RubikWidget w)1075 ShuffleEdges(RubikWidget w)
1076 {
1077 RotateCenterUp(w);
1078 RotateTopRight(w);
1079 RotateTopRight(w);
1080 RotateCenterDown(w);
1081 RotateTopRight(w);
1082 RotateTopRight(w);
1083 }
1084
1085 /* This procedure should be used when the two opposing top front and back */
1086 /* edge pieces are in position but not color aligned (this sequence is */
1087 /* known as Rubik's Maneuver). */
1088 static void
RecolorTopEdges(RubikWidget w)1089 RecolorTopEdges(RubikWidget w)
1090 {
1091 RotateCenterUp(w);
1092 RotateTopRight(w);
1093 RotateCenterUp(w);
1094 RotateTopRight(w);
1095 RotateCenterUp(w);
1096 RotateTopRight(w);
1097 RotateTopRight(w);
1098 RotateCenterDown(w);
1099 RotateTopRight(w);
1100 RotateCenterDown(w);
1101 RotateTopRight(w);
1102 RotateCenterDown(w);
1103 RotateTopRight(w);
1104 RotateTopRight(w);
1105 }
1106
1107 /* This procedure coordinates the solution process. */
1108 void
SolvePolyhedrons(RubikWidget w)1109 SolvePolyhedrons(RubikWidget w)
1110 {
1111 rubikCallbackStruct cb;
1112
1113 cb.reason = RUBIK_RESET;
1114 XtCallCallbacks((Widget) w, XtNselectCallback, &cb);
1115 if (!CheckSolved(w)) {
1116 SolveTop(w);
1117 AlignCorners(w);
1118 SolveBottom(w);
1119 if (w->rubik.sizex > 2) {
1120 SolveBottomEdges(w);
1121 AlignEdges(w);
1122 } else if (w->rubik.sizex == 2)
1123 Solve_2_2(w);
1124 }
1125 cb.reason = RUBIK_COMPUTED;
1126 XtCallCallbacks((Widget) w, XtNselectCallback, &cb);
1127 }
1128