source: research/2008-rubik/rubikutils/rubik.c @ 2739

Last change on this file since 2739 was 2739, checked in by kali, 14 years ago
  • introduce Michael Reid's optimal solver code in its original state

(a.out, no work on cpushare integration here)

  • introduce rubikutils, basicaly MR's structures and cube functions, but

adding cube orientation to the cube structure

  • rubikutils' main() inputs and validate a cube with center faces.
  • input order is:

F R U B L D UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
File size: 16.9 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3
4#define  MAX_CHECK_PERM_N                   24
5
6#define  CORNER_UFR                          0
7#define  CORNER_URB                          1
8#define  CORNER_UBL                          2
9#define  CORNER_ULF                          3
10#define  CORNER_DRF                          4
11#define  CORNER_DFL                          5
12#define  CORNER_DLB                          6
13#define  CORNER_DBR                          7
14
15#define  CORNER_FRU                          8
16#define  CORNER_RBU                          9
17#define  CORNER_BLU                         10
18#define  CORNER_LFU                         11
19#define  CORNER_RFD                         12
20#define  CORNER_FLD                         13
21#define  CORNER_LBD                         14
22#define  CORNER_BRD                         15
23
24#define  CORNER_RUF                         16
25#define  CORNER_BUR                         17
26#define  CORNER_LUB                         18
27#define  CORNER_FUL                         19
28#define  CORNER_FDR                         20
29#define  CORNER_LDF                         21
30#define  CORNER_BDL                         22
31#define  CORNER_RDB                         23
32
33
34#define  EDGE_UF                             0
35#define  EDGE_UR                             1
36#define  EDGE_UB                             2
37#define  EDGE_UL                             3
38#define  EDGE_DF                             4
39#define  EDGE_DR                             5
40#define  EDGE_DB                             6
41#define  EDGE_DL                             7
42#define  EDGE_FR                             8
43#define  EDGE_FL                             9
44#define  EDGE_BR                            10
45#define  EDGE_BL                            11
46
47#define  EDGE_FU                            12
48#define  EDGE_RU                            13
49#define  EDGE_BU                            14
50#define  EDGE_LU                            15
51#define  EDGE_FD                            16
52#define  EDGE_RD                            17
53#define  EDGE_BD                            18
54#define  EDGE_LD                            19
55#define  EDGE_RF                            20
56#define  EDGE_LF                            21
57#define  EDGE_RB                            22
58#define  EDGE_LB                            23
59
60#define  FACE_F                              0
61#define  FACE_R                              1
62#define  FACE_U                              2
63#define  FACE_B                              3
64#define  FACE_L                              4
65#define  FACE_D                              5
66
67
68typedef struct cube
69        {
70        int             centers[6];
71        int             edges[24];
72        int             corners[24];
73        }
74        Cube;
75
76
77static char            *center_cubie_str[] = {"F", "R", "U",
78                                              "B", "L", "D"};
79
80static char            *edge_cubie_str[] = {"UF", "UR", "UB", "UL",
81                                            "DF", "DR", "DB", "DL",
82                                            "FR", "FL", "BR", "BL",
83                                            "FU", "RU", "BU", "LU",
84                                            "FD", "RD", "BD", "LD",
85                                            "RF", "LF", "RB", "LB"};
86
87static char            *corner_cubie_str[] = {"UFR", "URB", "UBL", "ULF",
88                                              "DRF", "DFL", "DLB", "DBR",
89                                              "FRU", "RBU", "BLU", "LFU",
90                                              "RFD", "FLD", "LBD", "BRD",
91                                              "RUF", "BUR", "LUB", "FUL",
92                                              "FDR", "LDF", "BDL", "RDB"};
93
94/* ========================================================================= */
95   void  two_cycle(int  array[], int  ind0, int  ind1)
96/* ------------------------------------------------------------------------- */
97
98{
99int                     temp;
100
101
102temp = array[ind0];
103array[ind0] = array[ind1];
104array[ind1] = temp;
105
106return;
107}
108
109
110/* ========================================================================= */
111   void  three_cycle(int  array[], int  ind0, int  ind1, int  ind2)
112/* ------------------------------------------------------------------------- */
113
114{
115int                     temp;
116
117
118temp = array[ind0];
119array[ind0] = array[ind1];
120array[ind1] = array[ind2];
121array[ind2] = temp;
122
123return;
124}
125
126
127/* ========================================================================= */
128   void  four_cycle(int  array[], int  ind0, int  ind1, int  ind2, int  ind3)
129/* ------------------------------------------------------------------------- */
130
131{
132int                     temp;
133
134
135temp = array[ind0];
136array[ind0] = array[ind1];
137array[ind1] = array[ind2];
138array[ind2] = array[ind3];
139array[ind3] = temp;
140
141return;
142}
143
144
145/* ========================================================================= */
146   void  print_cube(Cube  *p_cube)
147/* ------------------------------------------------------------------------- */
148
149{
150printf("%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s\n",
151 center_cubie_str[p_cube->centers[0]], center_cubie_str[p_cube->centers[1]],
152 center_cubie_str[p_cube->centers[2]], center_cubie_str[p_cube->centers[3]],
153 center_cubie_str[p_cube->centers[4]], center_cubie_str[p_cube->centers[5]],
154       edge_cubie_str[p_cube->edges[0]], edge_cubie_str[p_cube->edges[1]],
155       edge_cubie_str[p_cube->edges[2]], edge_cubie_str[p_cube->edges[3]],
156       edge_cubie_str[p_cube->edges[4]], edge_cubie_str[p_cube->edges[5]],
157       edge_cubie_str[p_cube->edges[6]], edge_cubie_str[p_cube->edges[7]],
158       edge_cubie_str[p_cube->edges[8]], edge_cubie_str[p_cube->edges[9]],
159       edge_cubie_str[p_cube->edges[10]], edge_cubie_str[p_cube->edges[11]],
160   corner_cubie_str[p_cube->corners[0]], corner_cubie_str[p_cube->corners[1]],
161   corner_cubie_str[p_cube->corners[2]], corner_cubie_str[p_cube->corners[3]],
162   corner_cubie_str[p_cube->corners[4]], corner_cubie_str[p_cube->corners[5]],
163   corner_cubie_str[p_cube->corners[6]], corner_cubie_str[p_cube->corners[7]]);
164
165return;
166}
167
168/* ========================================================================= */
169   void  perm_n_init(int  nn, int  array_out[])
170/* ------------------------------------------------------------------------- */
171
172{
173int                     ii;
174
175
176for (ii = 0; ii < nn; ii++)
177    array_out[ii] = ii;
178
179return;
180}
181
182
183/* ========================================================================= */
184   void  cube_init(Cube  *p_cube)
185/* ------------------------------------------------------------------------- */
186
187{
188perm_n_init(6, p_cube->centers);
189perm_n_init(24, p_cube->edges);
190perm_n_init(24, p_cube->corners);
191
192return;
193}
194
195/* ========================================================================= */
196   int  cube_compare(Cube  *cube0, Cube  *cube1)
197/* ------------------------------------------------------------------------- */
198
199{
200int           ii;
201
202for (ii = 0; ii < 6; ii++)
203    {
204    if (cube0->centers[ii] < cube1->centers[ii])
205       return -1;
206    else if (cube0->centers[ii] > cube1->centers[ii])
207       return 1;
208    }
209
210for (ii = 0; ii < 24; ii++)
211    {
212    if (cube0->edges[ii] < cube1->edges[ii])
213       return -1;
214    else if (cube0->edges[ii] > cube1->edges[ii])
215       return 1;
216    }
217
218for (ii = 0; ii < 24; ii++)
219    {
220    if (cube0->corners[ii] < cube1->corners[ii])
221       return -1;
222    else if (cube0->corners[ii] > cube1->corners[ii])
223       return 1;
224    }
225
226return 0;
227}
228
229#if 0
230/* ========================================================================= */
231   void  cube_compose(Cube  *in_cube0, Cube  *in_cube1, Cube  *out_cube)
232/* ------------------------------------------------------------------------- */
233
234{
235perm_n_compose(6, in_cube0->centers, in_cube1->centers, out_cube->centers);
236perm_n_compose(24, in_cube0->edges, in_cube1->edges, out_cube->edges);
237perm_n_compose(24, in_cube0->corners, in_cube1->corners, out_cube->corners);
238
239return;
240}
241#endif
242
243/* ========================================================================= */
244   int  perm_n_check(int  nn, int  array_in[])
245/* ------------------------------------------------------------------------- */
246
247{
248int                     count[MAX_CHECK_PERM_N], ii;
249
250
251for (ii = 0; ii < nn; ii++)
252    count[ii] = 0;
253
254for (ii = 0; ii < nn; ii++)
255    {
256    if ((array_in[ii] < 0) || (array_in[ii] >= nn))
257       return 1;
258
259    count[array_in[ii]]++;
260    }
261
262for (ii = 0; ii < nn; ii++)
263    if (count[ii] != 1)
264       return 1;
265
266return 0;
267}
268
269/* ========================================================================= */
270   int  perm_n_parity(int  nn, int  array_in[])
271/* ------------------------------------------------------------------------- */
272
273{
274int                     temp_array[MAX_CHECK_PERM_N];
275int                     ii, jj, n_cycles;
276
277
278for (ii = 0; ii < nn; ii++)
279    temp_array[ii] = 0;
280
281n_cycles = 0;
282
283for (ii = 0; ii < nn; ii++)
284    if (temp_array[ii] == 0)
285       {
286       n_cycles++;
287       jj = ii;
288       while (temp_array[jj] == 0)
289             {
290             temp_array[jj] = 1;
291             jj = array_in[jj];
292             }
293       }
294
295return (n_cycles + nn) % 2;
296}
297
298
299
300/* ========================================================================= */
301   int  centers_check(int  array_in[])
302/* return -1 if invalid, 0 if even cube configuration, 1 for odd */
303/* ------------------------------------------------------------------------- */
304
305{
306    int parity = 0;
307    int i;
308
309    int clone[6];
310    for(i = 0; i < 6; i++)
311        clone[i] = array_in[i];
312
313    // put FACE_UP upwards
314    for (i = 0; i<6; i++)
315        if(clone[i] == FACE_U)
316            break;
317
318    switch(i) {
319        case FACE_U:
320            break;
321        case FACE_F:
322            four_cycle(clone, FACE_U, FACE_F, FACE_D, FACE_B);
323            parity++;
324            break;
325        case FACE_L:
326            four_cycle(clone, FACE_U, FACE_L, FACE_D, FACE_R);
327            parity++;
328            break;
329        case FACE_R:
330            four_cycle(clone, FACE_U, FACE_R, FACE_D, FACE_L);
331            parity++;
332            break;
333        case FACE_B:
334            four_cycle(clone, FACE_U, FACE_B, FACE_D, FACE_F);
335            parity++;
336            break;
337        case FACE_D:
338            two_cycle(clone, FACE_U, FACE_D);
339            two_cycle(clone, FACE_F, FACE_B);
340            break;
341        case 6:
342            return -1;
343    }
344
345    // now put FACE_FRONT in place
346    for (i = 0; i<6; i++)
347        if(clone[i] == FACE_F)
348            break;
349    switch(i) {
350        case FACE_F:
351            break;
352        case FACE_L:
353            four_cycle(clone, FACE_F, FACE_L, FACE_B, FACE_R);
354            parity++;
355            break;
356        case FACE_R:
357            four_cycle(clone, FACE_F, FACE_R, FACE_B, FACE_L);
358            parity++;
359            break;
360        case FACE_B:
361            two_cycle(clone, FACE_F, FACE_B);
362            two_cycle(clone, FACE_L, FACE_R);
363            break;
364        case FACE_U: // this is not possible
365        case FACE_D:
366        case 6:
367            return -1;
368    }
369
370    if(clone[FACE_R] != FACE_R || clone[FACE_L] != FACE_L
371        || clone[FACE_B] != FACE_B || clone[FACE_D] != FACE_D)
372        return -1;
373
374    return parity & 1;
375}
376
377/* ========================================================================= */
378   int  string_to_cube(char  string[], Cube  *p_cube, int  give_err_msg)
379/* ------------------------------------------------------------------------- */
380
381/*  input:  string[]  */
382
383{
384char                    center_str[6][2], edge_str[12][3], corner_str[8][4];
385int                     center_arr[6], edge_arr[12], corner_arr[8];
386int                     ii, jj, twist, flip, edge_par, corner_par, center_par;
387int                     stat;
388
389
390stat = 0;
391
392if (sscanf(string, "%1s %1s %1s %1s %1s %1s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %3s %3s %3s %3s %3s %3s %3s %3s",
393           center_str[0], center_str[1], center_str[2],
394           center_str[3], center_str[4], center_str[5],
395           edge_str[0], edge_str[1], edge_str[2], edge_str[3],
396           edge_str[4], edge_str[5], edge_str[6], edge_str[7],
397           edge_str[8], edge_str[9], edge_str[10], edge_str[11],
398           corner_str[0], corner_str[1], corner_str[2], corner_str[3],
399           corner_str[4], corner_str[5], corner_str[6], corner_str[7]) < 20)
400   {
401   if (give_err_msg)
402      printf("invalid input!\n");
403   return 1;
404   }
405
406for (ii = 0; ii < 6  ; ii++)
407    {
408    for (jj = 0; jj < 6; jj++)
409        if(strcmp(center_str[ii], center_cubie_str[jj]) == 0)
410        {
411            p_cube->centers[ii] = jj;
412            break;
413        }
414        if(jj == 6)
415       {
416       if (give_err_msg)
417          printf("invalid center cubie: %s\n", center_str[ii]);
418       stat = 1;
419       }
420    }
421
422for (ii = 0; ii < 12; ii++)
423    {
424    for (jj = 0; jj < 24; jj++)
425        if (strcmp(edge_str[ii], edge_cubie_str[jj]) == 0)
426           {
427           p_cube->edges[ii] = jj;
428           break;
429           }
430    if (jj == 24)
431       {
432       if (give_err_msg)
433          printf("invalid edge cubie: %s\n", edge_str[ii]);
434       stat = 1;
435       }
436    }
437
438for (ii = 0; ii < 8; ii++)
439    {
440    for (jj = 0; jj < 24; jj++)
441        if (strcmp(corner_str[ii], corner_cubie_str[jj]) == 0)
442           {
443           p_cube->corners[ii] = jj;
444           break;
445           }
446    if (jj == 24)
447       {
448       if (give_err_msg)
449          printf("invalid corner cubie: %s\n", corner_str[ii]);
450       stat = 1;
451       }
452    }
453
454if (stat)
455   return stat;
456
457/*  fill out the remaining oriented edges and corners  */
458
459for (ii = 12; ii < 24; ii++)
460    p_cube->edges[ii] = (12 + p_cube->edges[ii - 12]) % 24;
461
462for (ii = 8; ii < 24; ii++)
463    p_cube->corners[ii] = (8 + p_cube->corners[ii - 8]) % 24;
464
465/*  now check to see that it's a legal cube  */
466
467center_par = centers_check(p_cube->centers);
468if (center_par == -1)
469    {
470   if (give_err_msg)
471      printf("bad center cubies\n");
472   stat = 1;
473    }
474
475if (perm_n_check(24, p_cube->edges))
476   {
477   if (give_err_msg)
478      printf("bad edge cubies\n");
479   stat = 1;
480   }
481
482if (perm_n_check(24, p_cube->corners))
483   {
484   if (give_err_msg)
485      printf("bad corner cubies\n");
486   stat = 1;
487   }
488
489if (stat)
490   return stat;
491
492flip = 0;
493for (ii = 0; ii < 12; ii++)
494    flip += (p_cube->edges[ii] / 12);
495
496if ((flip % 2) != 0)
497   {
498   if (give_err_msg)
499      printf("flip any edge cubie!\n");
500   stat = 1;
501   }
502
503twist = 0;
504for (ii = 0; ii < 8; ii++)
505    twist += (p_cube->corners[ii] / 8);
506
507twist %= 3;
508
509if (twist != 0)
510   {
511   if (give_err_msg)
512      printf("twist any corner cubie %sclockwise!\n",
513              (twist == 1) ? "counter" : "");
514   stat = 1;
515   }
516
517for (ii = 0; ii < 12; ii++)
518    edge_arr[ii] = p_cube->edges[ii] % 12;
519
520edge_par = perm_n_parity(12, edge_arr);
521
522for (ii = 0; ii < 8; ii++)
523    corner_arr[ii] = p_cube->corners[ii] % 8;
524
525corner_par = perm_n_parity(8, corner_arr);
526
527if (((edge_par +  corner_par + center_par) & 1) == 1)
528   {
529   if (give_err_msg)
530      printf("swap any two edge cubies or any two corner cubies!\n");
531   stat = 1;
532   }
533
534return stat;
535}
536
537
538/* ========================================================================= */
539   int  user_enters_cube(Cube  *p_cube)
540/* ------------------------------------------------------------------------- */
541
542{
543char                     line_str[256];
544
545
546printf("\nenter cube (Ctrl-D to exit):\n");
547
548line_str[0] = '\n';
549
550while (line_str[0] == '\n')           /*  ignore blank lines  */
551      {
552      if (fgets(line_str, 256, stdin) == NULL)
553         return -1;
554
555      if (line_str[0] == '%')         /*  echo comments  */
556         {
557         printf("%s", line_str);
558         line_str[0] = '\n';
559         }
560      }
561
562return string_to_cube(line_str, p_cube, 1);
563}
564
565
566
567/* ========================================================================= */
568   void  pretty_print_unsigned_int(unsigned int  nn)
569/* ------------------------------------------------------------------------- */
570
571{
572int                     digits[4], ii, started;
573
574
575for (ii = 0; ii < 4; ii++)
576    {
577    digits[ii] = nn % 1000;
578    nn /= 1000;
579    }
580
581started = 0;
582
583for (ii = 3; ii >= 0; ii--)
584    {
585    if (started)
586       {
587       if (digits[ii] >= 100)
588          printf("%3d", digits[ii]);
589       else if (digits[ii] >= 10)
590               printf("0%2d", digits[ii]);
591       else
592          printf("00%1d", digits[ii]);
593       }
594    else
595       {
596       if (digits[ii] >= 100)
597          {
598          printf("%3d", digits[ii]);
599          started = 1;
600          }
601       else if (digits[ii] >= 10)
602               {
603               printf(" %2d", digits[ii]);
604               started = 1;
605               }
606       else if ((digits[ii] >= 1) || (ii == 0))
607               {
608               printf("  %1d", digits[ii]);
609               started = 1;
610               }
611       else
612          printf("   ");
613       }
614
615    if (ii > 0)
616       printf("%c", started ? ',' : ' ');
617    }
618
619return;
620}
621
622
623/* ========================================================================= */
624   int  main(void)
625/* ------------------------------------------------------------------------- */
626
627{
628Cube                    cube_struct;
629int                     stat;
630
631while (1)
632      {
633      stat = user_enters_cube(&cube_struct);
634      if (stat < 0)
635         break;
636    }
637exit(EXIT_SUCCESS);
638
639return 0;  /*  haha  */
640}
Note: See TracBrowser for help on using the repository browser.