source: research/2008-rubik/solver/optimal/optimal.c @ 2739

Last change on this file since 2739 was 2739, checked in by kali, 12 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: 130.0 KB
Line 
1/*  optimal cube solver  by  michael reid  reid@math.ucf.edu  */
2/*  version 2.1  june 3, 2004  */
3/*  symmetry mechanism added  */
4/*  malloc.h removed, long string fixed  */
5
6
7#define  USE_METRIC        QUARTER_TURN_METRIC
8#define  SEARCH_LIMIT                        0
9#define  USE_SYMMETRY                        1
10#define  ONE_SOLUTION_ONLY                   0
11
12
13#include  <stdio.h>
14#include  <stdlib.h>
15#include  <string.h>
16#include  <setjmp.h>
17#include  <signal.h>
18
19
20#define  QUARTER_TURN_METRIC                 0
21#define  FACE_TURN_METRIC                    1
22
23#define  N_SYM                              16
24#define  N_TWIST                            18
25#define  N_CORNER                         2187
26#define  N_ELOC                            495
27#define  N_ELOC_CONV                      4096
28#define  N_EFLIP                          2048
29#define  N_FULLEDGE         (N_ELOC * N_EFLIP)
30#define  N_EDGEQUOT                      64430
31#define  N_CORNERPERM                    40320
32#define  N_SLICEEDGE                     11880
33
34#define  N_CUBESYM                          48
35#define  N_SYMSUBGRP                        98
36#define  SUBGRP_TRIVIAL                     97
37
38#define  N_DIST_CHARS                  ((N_EDGEQUOT * N_CORNER) / 2)
39#define  BACKWARDS_SWITCH_POINT    ((2 * N_EDGEQUOT * N_CORNER) / 5)
40
41#define  CORNER_START                        0
42#define  EDGE_START                      64244
43#define  CORNERPERM_START                    0
44#define  UD_SLICEEDGE_START                494
45#define  RL_SLICEEDGE_START                 54
46#define  FB_SLICEEDGE_START                209
47
48#define  MAX_PERM_N                         12
49#define  MAX_CHECK_PERM_N                   24
50
51#define  MAX_TWISTS                         43
52
53#define  TWIST_F                             0
54#define  TWIST_F2                            1
55#define  TWIST_F3                            2
56#define  TWIST_R                             3
57#define  TWIST_R2                            4
58#define  TWIST_R3                            5
59#define  TWIST_U                             6
60#define  TWIST_U2                            7
61#define  TWIST_U3                            8
62#define  TWIST_B                             9
63#define  TWIST_B2                           10
64#define  TWIST_B3                           11
65#define  TWIST_L                            12
66#define  TWIST_L2                           13
67#define  TWIST_L3                           14
68#define  TWIST_D                            15
69#define  TWIST_D2                           16
70#define  TWIST_D3                           17
71
72#define  CORNER_UFR                          0
73#define  CORNER_URB                          1
74#define  CORNER_UBL                          2
75#define  CORNER_ULF                          3
76#define  CORNER_DRF                          4
77#define  CORNER_DFL                          5
78#define  CORNER_DLB                          6
79#define  CORNER_DBR                          7
80
81#define  CORNER_FRU                          8
82#define  CORNER_RBU                          9
83#define  CORNER_BLU                         10
84#define  CORNER_LFU                         11
85#define  CORNER_RFD                         12
86#define  CORNER_FLD                         13
87#define  CORNER_LBD                         14
88#define  CORNER_BRD                         15
89
90#define  CORNER_RUF                         16
91#define  CORNER_BUR                         17
92#define  CORNER_LUB                         18
93#define  CORNER_FUL                         19
94#define  CORNER_FDR                         20
95#define  CORNER_LDF                         21
96#define  CORNER_BDL                         22
97#define  CORNER_RDB                         23
98
99
100#define  EDGE_UF                             0
101#define  EDGE_UR                             1
102#define  EDGE_UB                             2
103#define  EDGE_UL                             3
104#define  EDGE_DF                             4
105#define  EDGE_DR                             5
106#define  EDGE_DB                             6
107#define  EDGE_DL                             7
108#define  EDGE_FR                             8
109#define  EDGE_FL                             9
110#define  EDGE_BR                            10
111#define  EDGE_BL                            11
112
113#define  EDGE_FU                            12
114#define  EDGE_RU                            13
115#define  EDGE_BU                            14
116#define  EDGE_LU                            15
117#define  EDGE_FD                            16
118#define  EDGE_RD                            17
119#define  EDGE_BD                            18
120#define  EDGE_LD                            19
121#define  EDGE_RF                            20
122#define  EDGE_LF                            21
123#define  EDGE_RB                            22
124#define  EDGE_LB                            23
125
126
127#define  FACE_F                              0
128#define  FACE_R                              1
129#define  FACE_U                              2
130#define  FACE_B                              3
131#define  FACE_L                              4
132#define  FACE_D                              5
133
134
135#define  N_FOLLOW                          873
136
137#define  FOLLOW_INVALID                      0
138
139#define  N_SYLLABLE                         32
140
141#define  SYLLABLE_INVALID                    0
142#define  SYLLABLE_NONE                       1
143#define  SYLLABLE_F                          2
144#define  SYLLABLE_F2                         3
145#define  SYLLABLE_F3                         4
146#define  SYLLABLE_R                          5
147#define  SYLLABLE_R2                         6
148#define  SYLLABLE_R3                         7
149#define  SYLLABLE_U                          8
150#define  SYLLABLE_U2                         9
151#define  SYLLABLE_U3                        10
152#define  SYLLABLE_B                         11
153#define  SYLLABLE_B2                        12
154#define  SYLLABLE_B3                        13
155#define  SYLLABLE_L                         14
156#define  SYLLABLE_L2                        15
157#define  SYLLABLE_L3                        16
158#define  SYLLABLE_D                         17
159#define  SYLLABLE_D2                        18
160#define  SYLLABLE_D3                        19
161#define  SYLLABLE_FB                        20
162#define  SYLLABLE_FB2                       21
163#define  SYLLABLE_FB3                       22
164#define  SYLLABLE_F2B2                      23
165#define  SYLLABLE_RL                        24
166#define  SYLLABLE_RL2                       25
167#define  SYLLABLE_RL3                       26
168#define  SYLLABLE_R2L2                      27
169#define  SYLLABLE_UD                        28
170#define  SYLLABLE_UD2                       29
171#define  SYLLABLE_UD3                       30
172#define  SYLLABLE_U2D2                      31
173
174
175
176#define  DIST(c, e)     (((e) & 0x1) ? (((int)distance[c][(e) >> 1]) >> 4)   \
177                                     : (((int)distance[c][(e) >> 1]) & 0xF))
178
179
180typedef struct cube
181        {
182        int             edges[24];
183        int             corners[24];
184        }
185        Cube;
186
187
188typedef struct coset_coord
189        {
190        int             corner_state;
191        int             edge_state;
192        int             sym_state;
193        }
194        Coset_coord;
195
196
197typedef struct full_cube
198        {
199        Cube            cubies;
200        int             cornerperm;
201        int             ud_sliceedge;
202        int             rl_sliceedge;
203        int             fb_sliceedge;
204        Coset_coord     ud;
205        Coset_coord     rl;
206        Coset_coord     fb;
207        int             parity;
208        int             sym_subgrp;
209        }
210        Full_cube;
211
212
213typedef struct search_data
214        {
215        int             depth;
216        int             found;
217        int             found_quot;
218        int            *multiplicities;
219        int            *stabilizers;
220        }
221        Search_data;
222
223
224typedef struct search_node
225        {
226        int             remain_depth;
227        int             twist;
228        int             follow_type;
229        Coset_coord     ud;
230        Coset_coord     rl;
231        Coset_coord     fb;
232        }
233        Search_node;
234
235
236typedef struct metric_data
237        {
238        int             metric;
239        char            metric_char;
240        int             twist_length[N_TWIST];
241        int             increment;
242        }
243        Metric_data;
244
245
246typedef struct options
247        {
248        int             use_symmetry;
249        int             search_limit;
250        int             one_solution_only;
251        }
252        Options;
253
254
255typedef struct subgroup_list
256        {
257        int             n_subgroups;
258        int           (*subgroups)[N_CUBESYM];
259        }
260        Subgroup_list;
261
262
263
264static unsigned char   *sym_x_invsym_to_sym[N_SYM];
265
266static unsigned char   *invsym_on_twist_ud[N_SYM];
267static unsigned char   *invsym_on_twist_rl[N_SYM];
268static unsigned char   *invsym_on_twist_fb[N_SYM];
269
270static unsigned short  *twist_on_corner[N_TWIST];
271static unsigned short  *sym_on_corner[N_SYM];
272
273static unsigned short  *fulledge_to_edge;
274static unsigned char   *fulledge_to_sym;
275
276static unsigned short  *twist_on_edge[N_TWIST];
277static unsigned char   *twist_x_edge_to_sym[N_TWIST];
278
279static unsigned short  *twist_on_cornerperm[N_TWIST];
280static unsigned short  *twist_on_sliceedge[N_TWIST];
281
282static unsigned short  *twist_on_follow[N_TWIST];
283
284static unsigned char   *distance[N_CORNER];
285
286static char            *edge_cubie_str[] = {"UF", "UR", "UB", "UL",
287                                            "DF", "DR", "DB", "DL",
288                                            "FR", "FL", "BR", "BL",
289                                            "FU", "RU", "BU", "LU",
290                                            "FD", "RD", "BD", "LD",
291                                            "RF", "LF", "RB", "LB"};
292
293static char            *corner_cubie_str[] = {"UFR", "URB", "UBL", "ULF",
294                                              "DRF", "DFL", "DLB", "DBR",
295                                              "FRU", "RBU", "BLU", "LFU",
296                                              "RFD", "FLD", "LBD", "BRD",
297                                              "RUF", "BUR", "LUB", "FUL",
298                                              "FDR", "LDF", "BDL", "RDB"};
299
300static Metric_data     *p_current_metric;
301static Options         *p_current_options;
302
303static unsigned int     n_nodes;
304static unsigned int     n_tests;
305static int              sol_found;
306
307static sigjmp_buf       jump_env;
308
309
310/* ========================================================================= */
311   void  exit_w_error_message(char  *msg)
312/* ------------------------------------------------------------------------- */
313
314{
315printf("\n%s\n", msg);
316exit(EXIT_FAILURE);
317
318return;
319}
320
321
322/* ========================================================================= */
323   void  user_interrupt(int  unused_arg)
324/* ------------------------------------------------------------------------- */
325
326{
327printf("\n-- user interrupt --\n");
328fflush(stdout);
329siglongjmp(jump_env, 1);
330
331return;
332}
333
334
335/* ========================================================================= */
336   void  perm_n_unpack(int  nn, int  indx, int  array_out[])
337/* ------------------------------------------------------------------------- */
338
339{
340int                     ii, jj;
341
342
343for (ii = nn - 1; ii >= 0; ii--)
344    {
345    array_out[ii] = indx % (nn - ii);
346    indx /= (nn - ii);
347
348    for (jj = ii + 1; jj < nn; jj++)
349        if (array_out[jj] >= array_out[ii])
350           array_out[jj]++;
351    }
352
353return;
354}
355
356
357/* ========================================================================= */
358   int  perm_n_pack(int  nn, int  array_in[])
359/* ------------------------------------------------------------------------- */
360
361{
362int                     indx, ii, jj;
363
364
365indx = 0;
366
367for (ii = 0; ii < nn; ii++)
368    {
369    indx *= (nn - ii);
370
371    for (jj = ii + 1; jj < nn; jj++)
372        if (array_in[jj] < array_in[ii])
373           indx++;
374    }
375
376return indx;
377}
378
379
380/* ========================================================================= */
381   int  perm_n_check(int  nn, int  array_in[])
382/* ------------------------------------------------------------------------- */
383
384{
385int                     count[MAX_CHECK_PERM_N], ii;
386
387
388for (ii = 0; ii < nn; ii++)
389    count[ii] = 0;
390
391for (ii = 0; ii < nn; ii++)
392    {
393    if ((array_in[ii] < 0) || (array_in[ii] >= nn))
394       return 1;
395
396    count[array_in[ii]]++;
397    }
398
399for (ii = 0; ii < nn; ii++)
400    if (count[ii] != 1)
401       return 1;
402
403return 0;
404}
405
406
407/* ========================================================================= */
408   int  perm_n_parity(int  nn, int  array_in[])
409/* ------------------------------------------------------------------------- */
410
411{
412int                     temp_array[MAX_CHECK_PERM_N];
413int                     ii, jj, n_cycles;
414
415
416for (ii = 0; ii < nn; ii++)
417    temp_array[ii] = 0;
418
419n_cycles = 0;
420
421for (ii = 0; ii < nn; ii++)
422    if (temp_array[ii] == 0)
423       {
424       n_cycles++;
425       jj = ii;
426       while (temp_array[jj] == 0)
427             {
428             temp_array[jj] = 1;
429             jj = array_in[jj];
430             }
431       }
432
433return (n_cycles + nn) % 2;
434}
435
436
437/* ========================================================================= */
438   void  perm_n_init(int  nn, int  array_out[])
439/* ------------------------------------------------------------------------- */
440
441{
442int                     ii;
443
444
445for (ii = 0; ii < nn; ii++)
446    array_out[ii] = ii;
447
448return;
449}
450
451
452/* ========================================================================= */
453   void  perm_n_compose(int  nn, int  perm0_in[], int  perm1_in[],
454                                                  int  perm_out[])
455/* ------------------------------------------------------------------------- */
456
457{
458int                     ii;
459
460
461for (ii = 0; ii < nn; ii++)
462    perm_out[ii] = perm0_in[perm1_in[ii]];
463
464return;
465}
466
467
468/* ========================================================================= */
469   void  perm_n_conjugate(int  nn, int  arr_in[], int  conjugator[],
470                                                  int  array_out[])
471/* ------------------------------------------------------------------------- */
472
473{
474int                     ii;
475
476
477for (ii = 0; ii < nn; ii++)
478    array_out[conjugator[ii]] = conjugator[arr_in[ii]];
479
480return;
481}
482
483
484/* ========================================================================= */
485   void  two_cycle(int  array[], int  ind0, int  ind1)
486/* ------------------------------------------------------------------------- */
487
488{
489int                     temp;
490
491
492temp = array[ind0];
493array[ind0] = array[ind1];
494array[ind1] = temp;
495
496return;
497}
498
499
500/* ========================================================================= */
501   void  three_cycle(int  array[], int  ind0, int  ind1, int  ind2)
502/* ------------------------------------------------------------------------- */
503
504{
505int                     temp;
506
507
508temp = array[ind0];
509array[ind0] = array[ind1];
510array[ind1] = array[ind2];
511array[ind2] = temp;
512
513return;
514}
515
516
517/* ========================================================================= */
518   void  four_cycle(int  array[], int  ind0, int  ind1, int  ind2, int  ind3)
519/* ------------------------------------------------------------------------- */
520
521{
522int                     temp;
523
524
525temp = array[ind0];
526array[ind0] = array[ind1];
527array[ind1] = array[ind2];
528array[ind2] = array[ind3];
529array[ind3] = temp;
530
531return;
532}
533
534
535/* ========================================================================= */
536   void  print_cube(Cube  *p_cube)
537/* ------------------------------------------------------------------------- */
538
539{
540printf("%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s\n",
541       edge_cubie_str[p_cube->edges[0]], edge_cubie_str[p_cube->edges[1]],
542       edge_cubie_str[p_cube->edges[2]], edge_cubie_str[p_cube->edges[3]],
543       edge_cubie_str[p_cube->edges[4]], edge_cubie_str[p_cube->edges[5]],
544       edge_cubie_str[p_cube->edges[6]], edge_cubie_str[p_cube->edges[7]],
545       edge_cubie_str[p_cube->edges[8]], edge_cubie_str[p_cube->edges[9]],
546       edge_cubie_str[p_cube->edges[10]], edge_cubie_str[p_cube->edges[11]],
547   corner_cubie_str[p_cube->corners[0]], corner_cubie_str[p_cube->corners[1]],
548   corner_cubie_str[p_cube->corners[2]], corner_cubie_str[p_cube->corners[3]],
549   corner_cubie_str[p_cube->corners[4]], corner_cubie_str[p_cube->corners[5]],
550   corner_cubie_str[p_cube->corners[6]], corner_cubie_str[p_cube->corners[7]]);
551
552return;
553}
554
555
556/* ========================================================================= */
557   void  cube_init(Cube  *p_cube)
558/* ------------------------------------------------------------------------- */
559
560{
561perm_n_init(24, p_cube->edges);
562perm_n_init(24, p_cube->corners);
563
564return;
565}
566
567
568/* ========================================================================= */
569   int  cube_compare(Cube  *cube0, Cube  *cube1)
570/* ------------------------------------------------------------------------- */
571
572{
573int           ii;
574
575for (ii = 0; ii < 24; ii++)
576    {
577    if (cube0->edges[ii] < cube1->edges[ii])
578       return -1;
579    else if (cube0->edges[ii] > cube1->edges[ii])
580       return 1;
581    }
582
583for (ii = 0; ii < 24; ii++)
584    {
585    if (cube0->corners[ii] < cube1->corners[ii])
586       return -1;
587    else if (cube0->corners[ii] > cube1->corners[ii])
588       return 1;
589    }
590
591return 0;
592}
593
594
595/* ========================================================================= */
596   void  cube_compose(Cube  *in_cube0, Cube  *in_cube1, Cube  *out_cube)
597/* ------------------------------------------------------------------------- */
598
599{
600perm_n_compose(24, in_cube0->edges, in_cube1->edges, out_cube->edges);
601perm_n_compose(24, in_cube0->corners, in_cube1->corners, out_cube->corners);
602
603return;
604}
605
606
607/* ========================================================================= */
608   void  cube_conjugate(Cube  *p_cube_in, Cube  *p_conjugator,
609                                          Cube  *p_cube_out)
610/* ------------------------------------------------------------------------- */
611
612{
613perm_n_conjugate(24, p_cube_in->edges, p_conjugator->edges, p_cube_out->edges);
614perm_n_conjugate(24, p_cube_in->corners, p_conjugator->corners,
615                                                          p_cube_out->corners);
616
617return;
618}
619
620
621/* ========================================================================= */
622   int  cube_is_solved(Cube  *p_cube)
623/* ------------------------------------------------------------------------- */
624
625{
626Cube                    temp_cube;
627
628
629cube_init(&temp_cube);
630
631return (cube_compare(p_cube, &temp_cube) == 0);
632}
633
634
635/* ========================================================================= */
636   int  metric_q_length(int  twist)
637/* ------------------------------------------------------------------------- */
638
639{
640if ((twist == TWIST_F) || (twist == TWIST_F3) ||
641    (twist == TWIST_R) || (twist == TWIST_R3) ||
642    (twist == TWIST_U) || (twist == TWIST_U3) ||
643    (twist == TWIST_B) || (twist == TWIST_B3) ||
644    (twist == TWIST_L) || (twist == TWIST_L3) ||
645    (twist == TWIST_D) || (twist == TWIST_D3))
646   return 1;
647else if ((twist == TWIST_F2) || (twist == TWIST_R2) || (twist == TWIST_U2) ||
648         (twist == TWIST_B2) || (twist == TWIST_L2) || (twist == TWIST_D2))
649        return 2;
650else
651   exit_w_error_message("metric_q_length : invalid twist");
652
653return 0;
654}
655
656
657/* ========================================================================= */
658   int  metric_f_length(int  twist)
659/* ------------------------------------------------------------------------- */
660
661{
662if ((twist == TWIST_F) || (twist == TWIST_F2) || (twist == TWIST_F3) ||
663    (twist == TWIST_R) || (twist == TWIST_R2) || (twist == TWIST_R3) ||
664    (twist == TWIST_U) || (twist == TWIST_U2) || (twist == TWIST_U3) ||
665    (twist == TWIST_B) || (twist == TWIST_B2) || (twist == TWIST_B3) ||
666    (twist == TWIST_L) || (twist == TWIST_L2) || (twist == TWIST_L3) ||
667    (twist == TWIST_D) || (twist == TWIST_D2) || (twist == TWIST_D3))
668   return 1;
669else
670   exit_w_error_message("metric_f_length : invalid twist");
671
672return 0;
673}
674
675
676/* ========================================================================= */
677   void  calc_metric_q_length(int  lengths[N_TWIST])
678/* ------------------------------------------------------------------------- */
679
680{
681int                     twist;
682
683
684for (twist = 0; twist < N_TWIST; twist++)
685    lengths[twist] = metric_q_length(twist);
686
687return;
688}
689
690
691/* ========================================================================= */
692   void  calc_metric_f_length(int  lengths[N_TWIST])
693/* ------------------------------------------------------------------------- */
694
695{
696int                     twist;
697
698
699for (twist = 0; twist < N_TWIST; twist++)
700    lengths[twist] = metric_f_length(twist);
701
702return;
703}
704
705
706/* ========================================================================= */
707   void  init_metric(Metric_data  *p_metric_data, int  use_metric)
708/* ------------------------------------------------------------------------- */
709
710{
711if ((use_metric != QUARTER_TURN_METRIC) && (use_metric != FACE_TURN_METRIC))
712   exit_w_error_message("init_metric : unknown metric");
713
714p_metric_data->metric = use_metric;
715
716if (p_metric_data->metric == QUARTER_TURN_METRIC)
717   {
718   printf("using quarter turn metric\n");
719   p_metric_data->metric_char = 'q';
720   calc_metric_q_length(p_metric_data->twist_length);
721   p_metric_data->increment = 2;
722   }
723else
724   {
725   printf("using face turn metric\n");
726   p_metric_data->metric_char = 'f';
727   calc_metric_f_length(p_metric_data->twist_length);
728   p_metric_data->increment = 1;
729   }
730
731p_current_metric = p_metric_data;
732
733return;
734}
735
736
737/* ========================================================================= */
738   void  init_options(Metric_data  *p_metric_data, Options  *p_user_options)
739/* ------------------------------------------------------------------------- */
740
741{
742init_metric(p_metric_data, USE_METRIC);
743
744p_user_options->search_limit = SEARCH_LIMIT;
745if (p_user_options->search_limit <= 0)
746   printf("no search limit\n");
747else
748   printf("search limit: %d%c\n", p_user_options->search_limit,
749                                                p_current_metric->metric_char);
750
751p_user_options->use_symmetry = USE_SYMMETRY;
752if (p_user_options->use_symmetry)
753   printf("using symmetry reductions\n");
754else
755   printf("not using symmetry reductions\n");
756
757p_user_options->one_solution_only = ONE_SOLUTION_ONLY;
758if (p_user_options->one_solution_only)
759   printf("only finding one solution\n");
760else
761   printf("finding all solutions\n");
762
763printf("\n");
764p_current_options = p_user_options;
765
766return;
767}
768
769
770/* ========================================================================= */
771   void  calc_group_table(int  group_table[N_CUBESYM][N_CUBESYM])
772/* ------------------------------------------------------------------------- */
773
774{
775int                     sym_array[N_CUBESYM][6];
776int                     sym_pack[N_CUBESYM];
777int                     temp_array[6];
778int                     ii, jj, kk, pack;
779
780
781perm_n_init(6, sym_array[0]);
782perm_n_init(6, sym_array[1]);
783
784four_cycle(sym_array[1], FACE_F, FACE_L, FACE_B, FACE_R);
785
786for (ii = 2; ii < 4; ii++)
787    perm_n_compose(6, sym_array[1], sym_array[ii - 1], sym_array[ii]);
788
789perm_n_init(6, sym_array[4]);
790
791two_cycle(sym_array[4], FACE_U, FACE_D);
792two_cycle(sym_array[4], FACE_R, FACE_L);
793
794for (ii = 5; ii < 8; ii++)
795    perm_n_compose(6, sym_array[4], sym_array[ii - 4], sym_array[ii]);
796
797perm_n_init(6, sym_array[8]);
798
799two_cycle(sym_array[8], FACE_U, FACE_D);
800
801for (ii = 9; ii < 16; ii++)
802    perm_n_compose(6, sym_array[8], sym_array[ii - 8], sym_array[ii]);
803
804perm_n_init(6, sym_array[16]);
805
806three_cycle(sym_array[16], FACE_U, FACE_F, FACE_R);
807three_cycle(sym_array[16], FACE_D, FACE_B, FACE_L);
808
809for (ii = 17; ii < 48; ii++)
810    perm_n_compose(6, sym_array[16], sym_array[ii - 16], sym_array[ii]);
811
812for (ii = 0; ii < N_CUBESYM; ii++)
813    sym_pack[ii] = perm_n_pack(6, sym_array[ii]);
814
815for (ii = 0; ii < N_CUBESYM; ii++)
816    for (jj = 0; jj < N_CUBESYM; jj++)
817        {
818        perm_n_compose(6, sym_array[ii], sym_array[jj], temp_array);
819        pack = perm_n_pack(6, temp_array);
820
821        for (kk = 0; kk < N_CUBESYM; kk++)
822            if (sym_pack[kk] == pack)
823               {
824               group_table[ii][jj] = kk;
825               break;
826               }
827
828        if (kk == N_CUBESYM)
829           exit_w_error_message("calc_group_table : product not found");
830        }
831
832return;
833}
834
835
836/* ========================================================================= */
837   void  init_sym_x_invsym_to_sym(void)
838/* ------------------------------------------------------------------------- */
839
840{
841unsigned char         (*mem_ptr)[N_SYM];
842int                     group_table[N_CUBESYM][N_CUBESYM];
843int                     group_inverse[N_CUBESYM];
844int                     ii, jj;
845
846
847/*  initialize global array   sym_x_invsym_to_sym   */
848
849mem_ptr =
850        (unsigned char (*)[N_SYM])malloc(sizeof(unsigned char [N_SYM][N_SYM]));
851if (mem_ptr == NULL)
852   exit_w_error_message("init_sym_x_invsym_to_sym : couldn't get memory");
853
854for (ii = 0; ii < N_SYM; ii++)
855    sym_x_invsym_to_sym[ii] = mem_ptr[ii];
856
857calc_group_table(group_table);
858
859for (ii = 0; ii < N_SYM; ii++)
860    {
861    for (jj = 0; jj < N_SYM; jj++)
862        if (group_table[ii][jj] == 0)
863           {
864           group_inverse[ii] = jj;
865           break;
866           }
867
868    if (jj == N_SYM)
869       exit_w_error_message("init_sym_x_invsym_to_sym : inverse not found");
870    }
871
872for (ii = 0; ii < N_SYM; ii++)
873    for (jj = 0; jj < N_SYM; jj++)
874        sym_x_invsym_to_sym[ii][jj] =
875                             (unsigned char)group_table[ii][group_inverse[jj]];
876
877return;
878}
879
880
881/* ========================================================================= */
882   void  calc_sym_on_twist(int  sym_on_twist[N_CUBESYM][N_TWIST])
883/* ------------------------------------------------------------------------- */
884
885{
886int                     sym;
887
888
889perm_n_init(N_TWIST, sym_on_twist[0]);
890perm_n_init(N_TWIST, sym_on_twist[1]);
891
892four_cycle(sym_on_twist[1], TWIST_F , TWIST_L , TWIST_B , TWIST_R );
893four_cycle(sym_on_twist[1], TWIST_F2, TWIST_L2, TWIST_B2, TWIST_R2);
894four_cycle(sym_on_twist[1], TWIST_F3, TWIST_L3, TWIST_B3, TWIST_R3);
895
896for (sym = 2; sym < 4; sym++)
897    perm_n_compose(N_TWIST, sym_on_twist[1], sym_on_twist[sym - 1],
898                                                            sym_on_twist[sym]);
899
900perm_n_init(N_TWIST, sym_on_twist[4]);
901
902two_cycle(sym_on_twist[4], TWIST_R , TWIST_L );
903two_cycle(sym_on_twist[4], TWIST_R2, TWIST_L2);
904two_cycle(sym_on_twist[4], TWIST_R3, TWIST_L3);
905two_cycle(sym_on_twist[4], TWIST_U , TWIST_D );
906two_cycle(sym_on_twist[4], TWIST_U2, TWIST_D2);
907two_cycle(sym_on_twist[4], TWIST_U3, TWIST_D3);
908
909for (sym = 5; sym < 8; sym++)
910    perm_n_compose(N_TWIST, sym_on_twist[4], sym_on_twist[sym - 4],
911                                                            sym_on_twist[sym]);
912
913perm_n_init(N_TWIST, sym_on_twist[8]);
914
915two_cycle(sym_on_twist[8], TWIST_F, TWIST_F3);
916two_cycle(sym_on_twist[8], TWIST_R, TWIST_R3);
917two_cycle(sym_on_twist[8], TWIST_B, TWIST_B3);
918two_cycle(sym_on_twist[8], TWIST_L, TWIST_L3);
919two_cycle(sym_on_twist[8], TWIST_U , TWIST_D3);
920two_cycle(sym_on_twist[8], TWIST_U2, TWIST_D2);
921two_cycle(sym_on_twist[8], TWIST_U3, TWIST_D );
922
923for (sym = 9; sym < 16; sym++)
924    perm_n_compose(N_TWIST, sym_on_twist[8], sym_on_twist[sym - 8],
925                                                            sym_on_twist[sym]);
926
927perm_n_init(N_TWIST, sym_on_twist[16]);
928
929three_cycle(sym_on_twist[16], TWIST_F , TWIST_R , TWIST_U );
930three_cycle(sym_on_twist[16], TWIST_F2, TWIST_R2, TWIST_U2);
931three_cycle(sym_on_twist[16], TWIST_F3, TWIST_R3, TWIST_U3);
932three_cycle(sym_on_twist[16], TWIST_B , TWIST_L , TWIST_D );
933three_cycle(sym_on_twist[16], TWIST_B2, TWIST_L2, TWIST_D2);
934three_cycle(sym_on_twist[16], TWIST_B3, TWIST_L3, TWIST_D3);
935
936for (sym = 17; sym < 48; sym++)
937    perm_n_compose(N_TWIST, sym_on_twist[16], sym_on_twist[sym - 16],
938                                                            sym_on_twist[sym]);
939
940return;
941}
942
943
944/* ========================================================================= */
945   void  init_invsym_on_twist(void)
946/* ------------------------------------------------------------------------- */
947
948{
949unsigned char         (*mem_ptr)[N_SYM][N_TWIST];
950int                     sym_on_twist[N_CUBESYM][N_TWIST];
951int                     ud_to_rl[N_TWIST], sym, twist;
952
953
954/*   allocate and initialize global arrays                                 */
955/*   invsym_on_twist_ud ,  invsym_on_twist_fb   and   invsym_on_twist_rl   */
956
957mem_ptr = (unsigned char (*)[N_SYM][N_TWIST])
958                             malloc(sizeof(unsigned char [3][N_SYM][N_TWIST]));
959if (mem_ptr == NULL)
960   exit_w_error_message("init_invsym_on_twist : couldn't get memory");
961
962for (sym = 0; sym < N_SYM; sym++)
963    {
964    invsym_on_twist_ud[sym] = mem_ptr[0][sym];
965    invsym_on_twist_rl[sym] = mem_ptr[1][sym];
966    invsym_on_twist_fb[sym] = mem_ptr[2][sym];
967    }
968
969calc_sym_on_twist(sym_on_twist);
970
971for (sym = 0; sym < N_SYM; sym++)
972    for (twist = 0; twist < N_TWIST; twist++)
973        invsym_on_twist_ud[sym][twist] =
974          (unsigned char)sym_on_twist[(int)sym_x_invsym_to_sym[0][sym]][twist];
975
976perm_n_init(N_TWIST, ud_to_rl);
977
978three_cycle(ud_to_rl, TWIST_F , TWIST_R , TWIST_U );
979three_cycle(ud_to_rl, TWIST_F2, TWIST_R2, TWIST_U2);
980three_cycle(ud_to_rl, TWIST_F3, TWIST_R3, TWIST_U3);
981three_cycle(ud_to_rl, TWIST_B , TWIST_L , TWIST_D );
982three_cycle(ud_to_rl, TWIST_B2, TWIST_L2, TWIST_D2);
983three_cycle(ud_to_rl, TWIST_B3, TWIST_L3, TWIST_D3);
984
985for (sym = 0; sym < N_SYM; sym++)
986    for (twist = 0; twist < N_TWIST; twist++)
987        invsym_on_twist_rl[sym][twist] =
988                                      invsym_on_twist_ud[sym][ud_to_rl[twist]];
989
990for (sym = 0; sym < N_SYM; sym++)
991    for (twist = 0; twist < N_TWIST; twist++)
992        invsym_on_twist_fb[sym][twist] =
993                                      invsym_on_twist_rl[sym][ud_to_rl[twist]];
994
995return;
996}
997
998
999/* ========================================================================= */
1000   void  generate_subgroup(int  group_table[N_CUBESYM][N_CUBESYM],
1001                           int   gen_set[N_CUBESYM])
1002/* ------------------------------------------------------------------------- */
1003
1004/*  gen_set[]  is both input and output  */
1005
1006{
1007int                 found, ii, jj;
1008
1009
1010gen_set[0] = 1;
1011found = 1;
1012
1013while (found)
1014      {
1015      found = 0;
1016
1017      for (ii = 0; ii < N_CUBESYM; ii++)
1018          if (gen_set[ii] != 0)
1019             for (jj = 0; jj < N_CUBESYM; jj++)
1020                 if ((gen_set[jj] != 0) && (gen_set[group_table[ii][jj]] == 0))
1021                    {
1022                    gen_set[group_table[ii][jj]] = 1;
1023                    found = 1;
1024                    }
1025      }
1026
1027return;
1028}
1029
1030
1031/* ========================================================================= */
1032   void  calc_subgroups_recursive(int  group_table[N_CUBESYM][N_CUBESYM],
1033                                  int  contain_list[N_CUBESYM],
1034                                  int  avoid_list[N_CUBESYM],
1035                                  Subgroup_list  *p_output)
1036/* ------------------------------------------------------------------------- */
1037
1038{
1039int                 local_contain_list[N_CUBESYM], ii, jj;
1040
1041
1042for (ii = 0; ii < N_CUBESYM; ii++)
1043    if (contain_list[ii] && avoid_list[ii])
1044       return;
1045
1046for (ii = 0; ii < N_CUBESYM; ii++)
1047    if ((contain_list[ii] == 0) && (avoid_list[ii] == 0))
1048       break;
1049
1050if (ii < N_CUBESYM)
1051   {
1052   for (jj = 0; jj < N_CUBESYM; jj++)
1053       local_contain_list[jj] = contain_list[jj];
1054   local_contain_list[ii] = 1;
1055   generate_subgroup(group_table, local_contain_list);
1056   calc_subgroups_recursive(group_table, local_contain_list, avoid_list,
1057                                                                     p_output);
1058   avoid_list[ii] = 1;
1059   calc_subgroups_recursive(group_table, contain_list, avoid_list, p_output);
1060   avoid_list[ii] = 0;
1061   }
1062else
1063   {
1064   if (p_output->n_subgroups >= N_SYMSUBGRP)
1065      exit_w_error_message("calc_subgroups_recursive : too many subgroups");
1066
1067   for (ii = 0; ii < N_CUBESYM; ii++)
1068       p_output->subgroups[p_output->n_subgroups][ii] = contain_list[ii];
1069
1070   p_output->n_subgroups++;
1071   }
1072
1073return;
1074}
1075
1076
1077/* ========================================================================= */
1078   void  calc_subgroup_list(int  subgroup_list[N_SYMSUBGRP][N_CUBESYM])
1079/* ------------------------------------------------------------------------- */
1080
1081{
1082Subgroup_list   output_list;
1083int             group_table[N_CUBESYM][N_CUBESYM];
1084int             contain_list[N_CUBESYM];
1085int             avoid_list[N_CUBESYM];
1086int             ii;
1087
1088
1089calc_group_table(group_table);
1090
1091output_list.n_subgroups = 0;
1092output_list.subgroups = subgroup_list;
1093
1094contain_list[0] = 1;
1095
1096for (ii = 1; ii < N_CUBESYM; ii++)
1097    contain_list[ii] = 0;
1098
1099for (ii = 0; ii < N_CUBESYM; ii++)
1100    avoid_list[ii] = 0;
1101
1102calc_subgroups_recursive(group_table, contain_list, avoid_list, &output_list);
1103
1104if (output_list.n_subgroups != N_SYMSUBGRP)
1105   exit_w_error_message("calc_subgroup_list : wrong number of subgroups");
1106
1107return;
1108}
1109
1110
1111/* ========================================================================= */
1112   int  is_single_twist(int  syllable)
1113/* ------------------------------------------------------------------------- */
1114
1115{
1116if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
1117                                (syllable == SYLLABLE_F3) ||
1118    (syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
1119                                (syllable == SYLLABLE_R3) ||
1120    (syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
1121                                (syllable == SYLLABLE_U3) ||
1122    (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1123                                (syllable == SYLLABLE_B3) ||
1124    (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1125                                (syllable == SYLLABLE_L3) ||
1126    (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1127                                (syllable == SYLLABLE_D3))
1128   return 1;
1129
1130return 0;
1131}
1132
1133
1134/* ========================================================================= */
1135   int  syllable_to_twist(int  syllable)
1136/* ------------------------------------------------------------------------- */
1137
1138{
1139if (syllable == SYLLABLE_F)
1140   return TWIST_F;
1141else if (syllable == SYLLABLE_F2)
1142        return TWIST_F2;
1143else if (syllable == SYLLABLE_F3)
1144        return TWIST_F3;
1145else if (syllable == SYLLABLE_R)
1146        return TWIST_R;
1147else if (syllable == SYLLABLE_R2)
1148        return TWIST_R2;
1149else if (syllable == SYLLABLE_R3)
1150        return TWIST_R3;
1151else if (syllable == SYLLABLE_U)
1152        return TWIST_U;
1153else if (syllable == SYLLABLE_U2)
1154        return TWIST_U2;
1155else if (syllable == SYLLABLE_U3)
1156        return TWIST_U3;
1157else if (syllable == SYLLABLE_B)
1158        return TWIST_B;
1159else if (syllable == SYLLABLE_B2)
1160        return TWIST_B2;
1161else if (syllable == SYLLABLE_B3)
1162        return TWIST_B3;
1163else if (syllable == SYLLABLE_L)
1164        return TWIST_L;
1165else if (syllable == SYLLABLE_L2)
1166        return TWIST_L2;
1167else if (syllable == SYLLABLE_L3)
1168        return TWIST_L3;
1169else if (syllable == SYLLABLE_D)
1170        return TWIST_D;
1171else if (syllable == SYLLABLE_D2)
1172        return TWIST_D2;
1173else if (syllable == SYLLABLE_D3)
1174        return TWIST_D3;
1175else
1176   exit_w_error_message("syllable_to_twist : invalid input");
1177
1178return -1;
1179}
1180
1181
1182/* ========================================================================= */
1183   void  syllable_to_two_twists(int  syllable, int  twists_out[2])
1184/* ------------------------------------------------------------------------- */
1185
1186{
1187if (syllable == SYLLABLE_FB)
1188   {
1189   twists_out[0] = TWIST_F;
1190   twists_out[1] = TWIST_B;
1191   }
1192else if (syllable == SYLLABLE_FB2)
1193        {
1194        twists_out[0] = TWIST_F;
1195        twists_out[1] = TWIST_B2;
1196        }
1197else if (syllable == SYLLABLE_FB3)
1198        {
1199        twists_out[0] = TWIST_F;
1200        twists_out[1] = TWIST_B3;
1201        }
1202else if (syllable == SYLLABLE_F2B2)
1203        {
1204        twists_out[0] = TWIST_F2;
1205        twists_out[1] = TWIST_B2;
1206        }
1207else if (syllable == SYLLABLE_RL)
1208        {
1209        twists_out[0] = TWIST_R;
1210        twists_out[1] = TWIST_L;
1211        }
1212else if (syllable == SYLLABLE_RL2)
1213        {
1214        twists_out[0] = TWIST_R;
1215        twists_out[1] = TWIST_L2;
1216        }
1217else if (syllable == SYLLABLE_RL3)
1218        {
1219        twists_out[0] = TWIST_R;
1220        twists_out[1] = TWIST_L3;
1221        }
1222else if (syllable == SYLLABLE_R2L2)
1223        {
1224        twists_out[0] = TWIST_R2;
1225        twists_out[1] = TWIST_L2;
1226        }
1227else if (syllable == SYLLABLE_UD)
1228        {
1229        twists_out[0] = TWIST_U;
1230        twists_out[1] = TWIST_D;
1231        }
1232else if (syllable == SYLLABLE_UD2)
1233        {
1234        twists_out[0] = TWIST_U;
1235        twists_out[1] = TWIST_D2;
1236        }
1237else if (syllable == SYLLABLE_UD3)
1238        {
1239        twists_out[0] = TWIST_U;
1240        twists_out[1] = TWIST_D3;
1241        }
1242else if (syllable == SYLLABLE_U2D2)
1243        {
1244        twists_out[0] = TWIST_U2;
1245        twists_out[1] = TWIST_D2;
1246        }
1247else
1248   exit_w_error_message("syllable_to_two_twists : invalid input");
1249
1250return;
1251}
1252
1253
1254/* ========================================================================= */
1255   int  twists_in_wrong_order(int  twists[2])
1256/* ------------------------------------------------------------------------- */
1257
1258{
1259if (((twists[0] == TWIST_B) || (twists[0] == TWIST_B2) ||
1260                                   (twists[0] == TWIST_B3)) &&
1261    ((twists[1] == TWIST_F) || (twists[1] == TWIST_F2) ||
1262                                   (twists[1] == TWIST_F3)))
1263   return 1;
1264
1265if (((twists[0] == TWIST_L) || (twists[0] == TWIST_L2) ||
1266                                   (twists[0] == TWIST_L3)) &&
1267    ((twists[1] == TWIST_R) || (twists[1] == TWIST_R2) ||
1268                                   (twists[1] == TWIST_R3)))
1269   return 1;
1270
1271if (((twists[0] == TWIST_D) || (twists[0] == TWIST_D2) ||
1272                                   (twists[0] == TWIST_D3)) &&
1273    ((twists[1] == TWIST_U) || (twists[1] == TWIST_U2) ||
1274                                   (twists[1] == TWIST_U3)))
1275   return 1;
1276
1277return 0;
1278}
1279
1280
1281/* ========================================================================= */
1282   void  clean_up_sequence(int  twist_sequence[], int  n_twists)
1283/* ------------------------------------------------------------------------- */
1284
1285{
1286int             ii;
1287
1288
1289for (ii = 1; ii < n_twists; ii++)
1290    if (twists_in_wrong_order(&twist_sequence[ii - 1]) != 0)
1291       two_cycle(twist_sequence, ii - 1, ii);
1292
1293return;
1294}
1295
1296
1297/* ========================================================================= */
1298   int  which_subgroup(int  subgroup[N_CUBESYM],
1299                       int  subgroup_list[N_SYMSUBGRP][N_CUBESYM])
1300/* ------------------------------------------------------------------------- */
1301
1302{
1303int             subgrp, sym;
1304
1305
1306for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1307    {
1308    for (sym = 0; sym < N_CUBESYM; sym++)
1309        if ((subgroup[sym] == 0) != (subgroup_list[subgrp][sym] == 0))
1310           break;
1311
1312    if (sym == N_CUBESYM)
1313       return subgrp;
1314    }
1315
1316return -1;
1317}
1318
1319
1320/* ========================================================================= */
1321   void  calc_syllable_on_sym(int  subgroup_list[N_SYMSUBGRP][N_CUBESYM],
1322                              int  sym_on_twist[N_CUBESYM][N_TWIST],
1323                              int  syllable_on_sym[N_SYLLABLE][N_SYMSUBGRP])
1324/* ------------------------------------------------------------------------- */
1325
1326{
1327int             subgroup[N_CUBESYM], temp_subgroup[N_CUBESYM];
1328int             twist_arr[2], temp_arr[2];
1329int             syllable, sym, subgrp, twist;
1330
1331
1332for (syllable = 0; syllable < N_SYLLABLE; syllable++)
1333    {
1334    if ((syllable == SYLLABLE_INVALID) || (syllable == SYLLABLE_NONE))
1335       {
1336       subgroup[0] = 1;
1337       for (sym = 1; sym < N_CUBESYM; sym++)
1338           subgroup[sym] = 0;
1339       }
1340    else if (is_single_twist(syllable))
1341            {
1342            twist = syllable_to_twist(syllable);
1343            for (sym = 0; sym < N_CUBESYM; sym++)
1344                subgroup[sym] = (sym_on_twist[sym][twist] == twist);
1345            }
1346    else
1347       {
1348       syllable_to_two_twists(syllable, twist_arr);
1349
1350       for (sym = 0; sym < N_CUBESYM; sym++)
1351           {
1352           temp_arr[0] = sym_on_twist[sym][twist_arr[0]];
1353           temp_arr[1] = sym_on_twist[sym][twist_arr[1]];
1354           clean_up_sequence(temp_arr, 2);
1355           if ((temp_arr[0] == twist_arr[0]) &&
1356               (temp_arr[1] == twist_arr[1]))
1357              subgroup[sym] = 1;
1358           else
1359              subgroup[sym] = 0;
1360           }
1361       }
1362
1363    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1364        {
1365        for (sym = 0; sym < N_CUBESYM; sym++)
1366            temp_subgroup[sym] = (subgroup[sym] && subgroup_list[subgrp][sym]);
1367
1368        syllable_on_sym[syllable][subgrp] = which_subgroup(temp_subgroup,
1369                                                                subgroup_list);
1370        if (syllable_on_sym[syllable][subgrp] < 0)
1371           exit_w_error_message("calc_syllable_on_sym : subgroup not found");
1372        }
1373    }
1374
1375return;
1376}
1377
1378
1379/* ========================================================================= */
1380   int  twist_on_syllable(int  twist, int  syllable)
1381/* ------------------------------------------------------------------------- */
1382
1383{
1384if (syllable == SYLLABLE_INVALID)
1385   return SYLLABLE_INVALID;
1386
1387if (twist == TWIST_F)
1388   {
1389   if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
1390                                   (syllable == SYLLABLE_F3) ||
1391       (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1392                                   (syllable == SYLLABLE_B3) ||
1393       (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
1394       (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
1395      return SYLLABLE_INVALID;
1396   else
1397      return SYLLABLE_F;
1398   }
1399else if (twist == TWIST_F2)
1400        {
1401        if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
1402                                        (syllable == SYLLABLE_F3) ||
1403            (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1404                                        (syllable == SYLLABLE_B3) ||
1405            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
1406            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
1407           return SYLLABLE_INVALID;
1408        else
1409           return SYLLABLE_F2;
1410        }
1411else if (twist == TWIST_F3)
1412        {
1413        if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
1414                                        (syllable == SYLLABLE_F3) ||
1415            (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1416                                        (syllable == SYLLABLE_B3) ||
1417            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
1418            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
1419           return SYLLABLE_INVALID;
1420        else
1421           return SYLLABLE_F3;
1422        }
1423else if (twist == TWIST_R)
1424        {
1425        if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
1426                                        (syllable == SYLLABLE_R3) ||
1427            (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1428                                        (syllable == SYLLABLE_L3) ||
1429            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
1430            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
1431           return SYLLABLE_INVALID;
1432        else
1433           return SYLLABLE_R;
1434        }
1435else if (twist == TWIST_R2)
1436        {
1437        if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
1438                                        (syllable == SYLLABLE_R3) ||
1439            (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1440                                        (syllable == SYLLABLE_L3) ||
1441            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
1442            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
1443           return SYLLABLE_INVALID;
1444        else
1445           return SYLLABLE_R2;
1446        }
1447else if (twist == TWIST_R3)
1448        {
1449        if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
1450                                        (syllable == SYLLABLE_R3) ||
1451            (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1452                                        (syllable == SYLLABLE_L3) ||
1453            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
1454            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
1455           return SYLLABLE_INVALID;
1456        else
1457           return SYLLABLE_R3;
1458        }
1459else if (twist == TWIST_U)
1460        {
1461        if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
1462                                        (syllable == SYLLABLE_U3) ||
1463            (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1464                                        (syllable == SYLLABLE_D3) ||
1465            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
1466            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
1467           return SYLLABLE_INVALID;
1468        else
1469           return SYLLABLE_U;
1470        }
1471else if (twist == TWIST_U2)
1472        {
1473        if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
1474                                        (syllable == SYLLABLE_U3) ||
1475            (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1476                                        (syllable == SYLLABLE_D3) ||
1477            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
1478            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
1479           return SYLLABLE_INVALID;
1480        else
1481           return SYLLABLE_U2;
1482        }
1483else if (twist == TWIST_U3)
1484        {
1485        if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
1486                                        (syllable == SYLLABLE_U3) ||
1487            (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1488                                        (syllable == SYLLABLE_D3) ||
1489            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
1490            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
1491           return SYLLABLE_INVALID;
1492        else
1493           return SYLLABLE_U3;
1494        }
1495else if (twist == TWIST_B)
1496        {
1497        if ((syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1498                                        (syllable == SYLLABLE_B3) ||
1499            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
1500            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
1501           return SYLLABLE_INVALID;
1502        else if (syllable == SYLLABLE_F)
1503                return SYLLABLE_FB;
1504        else if (syllable == SYLLABLE_F2)
1505                return SYLLABLE_FB2;
1506        else if (syllable == SYLLABLE_F3)
1507                return SYLLABLE_FB3;
1508        else
1509           return SYLLABLE_B;
1510        }
1511else if (twist == TWIST_B2)
1512        {
1513        if ((syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1514                                        (syllable == SYLLABLE_B3) ||
1515            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
1516            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
1517           return SYLLABLE_INVALID;
1518        else if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F3))
1519                return SYLLABLE_FB2;
1520        else if (syllable == SYLLABLE_F2)
1521                return SYLLABLE_F2B2;
1522        else
1523           return SYLLABLE_B2;
1524        }
1525else if (twist == TWIST_B3)
1526        {
1527        if ((syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
1528                                        (syllable == SYLLABLE_B3) ||
1529            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
1530            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
1531           return SYLLABLE_INVALID;
1532        else if (syllable == SYLLABLE_F)
1533                return SYLLABLE_FB3;
1534        else if (syllable == SYLLABLE_F2)
1535                return SYLLABLE_FB2;
1536        else if (syllable == SYLLABLE_F3)
1537                return SYLLABLE_FB;
1538        else
1539           return SYLLABLE_B3;
1540        }
1541else if (twist == TWIST_L)
1542        {
1543        if ((syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1544                                        (syllable == SYLLABLE_L3) ||
1545            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
1546            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
1547           return SYLLABLE_INVALID;
1548        else if (syllable == SYLLABLE_R)
1549                return SYLLABLE_RL;
1550        else if (syllable == SYLLABLE_R2)
1551                return SYLLABLE_RL2;
1552        else if (syllable == SYLLABLE_R3)
1553                return SYLLABLE_RL3;
1554        else
1555           return SYLLABLE_L;
1556        }
1557else if (twist == TWIST_L2)
1558        {
1559        if ((syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1560                                        (syllable == SYLLABLE_L3) ||
1561            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
1562            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
1563           return SYLLABLE_INVALID;
1564        else if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R3))
1565                return SYLLABLE_RL2;
1566        else if (syllable == SYLLABLE_R2)
1567                return SYLLABLE_R2L2;
1568        else
1569           return SYLLABLE_L2;
1570        }
1571else if (twist == TWIST_L3)
1572        {
1573        if ((syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
1574                                        (syllable == SYLLABLE_L3) ||
1575            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
1576            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
1577           return SYLLABLE_INVALID;
1578        else if (syllable == SYLLABLE_R)
1579                return SYLLABLE_RL3;
1580        else if (syllable == SYLLABLE_R2)
1581                return SYLLABLE_RL2;
1582        else if (syllable == SYLLABLE_R3)
1583                return SYLLABLE_RL;
1584        else
1585           return SYLLABLE_L3;
1586        }
1587else if (twist == TWIST_D)
1588        {
1589        if ((syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1590                                        (syllable == SYLLABLE_D3) ||
1591            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
1592            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
1593           return SYLLABLE_INVALID;
1594        else if (syllable == SYLLABLE_U)
1595                return SYLLABLE_UD;
1596        else if (syllable == SYLLABLE_U2)
1597                return SYLLABLE_UD2;
1598        else if (syllable == SYLLABLE_U3)
1599                return SYLLABLE_UD3;
1600        else
1601           return SYLLABLE_D;
1602        }
1603else if (twist == TWIST_D2)
1604        {
1605        if ((syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1606                                        (syllable == SYLLABLE_D3) ||
1607            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
1608            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
1609           return SYLLABLE_INVALID;
1610        else if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U3))
1611                return SYLLABLE_UD2;
1612        else if (syllable == SYLLABLE_U2)
1613                return SYLLABLE_U2D2;
1614        else
1615           return SYLLABLE_D2;
1616        }
1617else if (twist == TWIST_D3)
1618        {
1619        if ((syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
1620                                        (syllable == SYLLABLE_D3) ||
1621            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
1622            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
1623           return SYLLABLE_INVALID;
1624        else if (syllable == SYLLABLE_U)
1625                return SYLLABLE_UD3;
1626        else if (syllable == SYLLABLE_U2)
1627                return SYLLABLE_UD2;
1628        else if (syllable == SYLLABLE_U3)
1629                return SYLLABLE_UD;
1630        else
1631           return SYLLABLE_D3;
1632        }
1633else
1634   exit_w_error_message("twist_on_syllable : invalid twist");
1635
1636return SYLLABLE_INVALID;
1637}
1638
1639
1640/* ========================================================================= */
1641   int  not_minimal_one_twist(int  subgroup[N_CUBESYM],
1642                              int  sym_on_twist[N_CUBESYM][N_TWIST],
1643                              int  twist)
1644/* ------------------------------------------------------------------------- */
1645
1646{
1647int                     sym;
1648
1649
1650for (sym = 0; sym < N_CUBESYM; sym++)
1651    if (subgroup[sym] && (sym_on_twist[sym][twist] < twist))
1652       return 1;
1653
1654return 0;
1655}
1656
1657
1658/* ========================================================================= */
1659   int  not_minimal_two_twists(int  subgroup[N_CUBESYM],
1660                               int  sym_on_twist[N_CUBESYM][N_TWIST],
1661                               int  twist0, int  twist1)
1662/* ------------------------------------------------------------------------- */
1663
1664{
1665int                     twist_arr[2], sym;
1666
1667
1668for (sym = 0; sym < N_CUBESYM; sym++)
1669    if (subgroup[sym])
1670       {
1671       twist_arr[0] = sym_on_twist[sym][twist0];
1672       twist_arr[1] = sym_on_twist[sym][twist1];
1673       clean_up_sequence(twist_arr, 2);
1674       if ((twist_arr[0] < twist0) ||
1675           ((twist_arr[0] == twist0) && (twist_arr[1] < twist1)))
1676          return 1;
1677       }
1678
1679return 0;
1680}
1681
1682
1683/* ========================================================================= */
1684   void  calc_twist_on_sylsubgrp(int
1685                           tw_on_sylsubgrp[N_TWIST][N_SYLLABLE * N_SYMSUBGRP])
1686/* ------------------------------------------------------------------------- */
1687
1688{
1689int             subgroup_list[N_SYMSUBGRP][N_CUBESYM];
1690int             sym_on_twist[N_CUBESYM][N_TWIST];
1691int             syllable_on_subgrp[N_SYLLABLE][N_SYMSUBGRP];
1692int             syllable, subgrp, subgrp_before, subgrp_after, twist;
1693int             new_syllable, new_subgrp;
1694
1695
1696calc_subgroup_list(subgroup_list);
1697calc_sym_on_twist(sym_on_twist);
1698calc_syllable_on_sym(subgroup_list, sym_on_twist, syllable_on_subgrp);
1699
1700for (syllable = 0; syllable < N_SYLLABLE; syllable++)
1701    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1702        {
1703        if (is_single_twist(syllable))
1704           {
1705           subgrp_before = subgrp;
1706           subgrp_after = syllable_on_subgrp[syllable][subgrp];
1707           }
1708        else
1709           {
1710           subgrp_before = SUBGRP_TRIVIAL;
1711
1712           if (syllable == SYLLABLE_INVALID)
1713              subgrp_after = SUBGRP_TRIVIAL;
1714           else
1715              subgrp_after = subgrp;
1716           }
1717
1718        for (twist = 0; twist < N_TWIST; twist++)
1719            {
1720            new_syllable = twist_on_syllable(twist, syllable);
1721
1722            if (is_single_twist(new_syllable))
1723               {
1724               if (not_minimal_one_twist(subgroup_list[subgrp_after],
1725                                sym_on_twist, syllable_to_twist(new_syllable)))
1726                  new_syllable = SYLLABLE_INVALID;
1727               }
1728            else if (new_syllable != SYLLABLE_INVALID)
1729                    {
1730                    if (not_minimal_two_twists(subgroup_list[subgrp_before],
1731                             sym_on_twist, syllable_to_twist(syllable), twist))
1732                       new_syllable = SYLLABLE_INVALID;
1733                    }
1734
1735            if (new_syllable == SYLLABLE_INVALID)
1736               new_subgrp = SUBGRP_TRIVIAL;
1737            else if (is_single_twist(new_syllable))
1738                    new_subgrp = subgrp_after;
1739            else
1740               new_subgrp = syllable_on_subgrp[new_syllable][subgrp_before];
1741
1742            tw_on_sylsubgrp[twist][syllable * N_SYMSUBGRP + subgrp] =
1743                                     new_syllable * N_SYMSUBGRP + new_subgrp;
1744            }
1745        }
1746
1747return;
1748}
1749
1750
1751/* ========================================================================= */
1752   void  init_twist_on_follow(void)
1753/* ------------------------------------------------------------------------- */
1754
1755{
1756unsigned short        (*mem_ptr)[N_FOLLOW];
1757int                     tw_on_sylsubgrp[N_TWIST][N_SYLLABLE * N_SYMSUBGRP];
1758int                     occurs[N_SYLLABLE * N_SYMSUBGRP];
1759int                     sylsubgrp_to_follow[N_SYLLABLE * N_SYMSUBGRP];
1760int                     follow_to_sylsubgrp[N_FOLLOW];
1761int                     syllable, subgrp, found, twist, count, follow;
1762
1763
1764calc_twist_on_sylsubgrp(tw_on_sylsubgrp);
1765
1766for (syllable = 0; syllable < N_SYLLABLE; syllable++)
1767    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1768        occurs[syllable * N_SYMSUBGRP + subgrp] = 0;
1769
1770for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1771    occurs[SYLLABLE_NONE * N_SYMSUBGRP + subgrp] = 1;
1772
1773found = 1;
1774
1775while (found)
1776      {
1777      found = 0;
1778      for (syllable = 0; syllable < N_SYLLABLE; syllable++)
1779          for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1780              for (twist = 0; twist < N_TWIST; twist++)
1781                  if (occurs[tw_on_sylsubgrp[twist]
1782                                     [syllable * N_SYMSUBGRP + subgrp]] == 0)
1783                     {
1784                     occurs[tw_on_sylsubgrp[twist]
1785                                      [syllable * N_SYMSUBGRP + subgrp]] = 1;
1786                     found = 1;
1787                     }
1788      }
1789
1790count = 0;
1791
1792for (syllable = 0; syllable < N_SYLLABLE; syllable++)
1793    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1794        {
1795        if (occurs[syllable * N_SYMSUBGRP + subgrp] == 0)
1796           sylsubgrp_to_follow[syllable * N_SYMSUBGRP + subgrp] = -1;
1797        else
1798           {
1799           sylsubgrp_to_follow[syllable * N_SYMSUBGRP + subgrp] = count;
1800           follow_to_sylsubgrp[count] = syllable * N_SYMSUBGRP + subgrp;
1801           count++;
1802           }
1803        }
1804
1805if (count != N_FOLLOW)
1806   exit_w_error_message("init_twist_on_follow : wrong number of  follow's");
1807
1808for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
1809    if (sylsubgrp_to_follow[SYLLABLE_NONE * N_SYMSUBGRP + subgrp]
1810                                                                 != 1 + subgrp)
1811       exit_w_error_message("init_twist_on_follow : indexing error");
1812
1813mem_ptr = (unsigned short (*)[N_FOLLOW])
1814                            malloc(sizeof(unsigned short [N_TWIST][N_FOLLOW]));
1815if (mem_ptr == NULL)
1816   exit_w_error_message("init_twist_on_follow : couldn't get memory");
1817
1818for (twist = 0; twist < N_TWIST; twist++)
1819    twist_on_follow[twist] = mem_ptr[twist];
1820
1821for (twist = 0; twist < N_TWIST; twist++)
1822    for (follow = 0; follow < N_FOLLOW; follow++)
1823        twist_on_follow[twist][follow] =
1824            (unsigned short)sylsubgrp_to_follow[tw_on_sylsubgrp[twist]
1825                                                [follow_to_sylsubgrp[follow]]];
1826
1827return;
1828}
1829
1830
1831/* ========================================================================= */
1832   void  corner_unpack(int  corner, int  array_out[8])
1833/* ------------------------------------------------------------------------- */
1834
1835/*  input:  corner
1836   output:  array_out[]  */
1837
1838{
1839int                     ii;
1840
1841
1842for (ii = 0; ii < 7; ii++)
1843    {
1844    array_out[ii] = corner % 3;
1845    corner = corner / 3;
1846    }
1847
1848array_out[7] = (2 * (array_out[0] + array_out[1] + array_out[2] + array_out[3]
1849                            + array_out[4] + array_out[5] + array_out[6])) % 3;
1850
1851return;
1852}
1853
1854
1855/* ========================================================================= */
1856   int  corner_pack(int  array_in[8])
1857/* ------------------------------------------------------------------------- */
1858
1859/*  input:  array_in[]  */
1860
1861{
1862int                     corner, ii;
1863
1864
1865corner = 0;
1866for (ii = 6; ii >= 0; ii--)
1867    corner = 3 * corner + array_in[ii];
1868
1869return corner;
1870}
1871
1872
1873/* ========================================================================= */
1874   void  corner_adjust(int  array[8], int  ind0, int  ind1, int  ind2,
1875                                                            int  ind3)
1876/* ------------------------------------------------------------------------- */
1877
1878{
1879array[ind0] = (array[ind0] + 1) % 3;
1880array[ind1] = (array[ind1] + 2) % 3;
1881array[ind2] = (array[ind2] + 1) % 3;
1882array[ind3] = (array[ind3] + 2) % 3;
1883
1884return;
1885}
1886
1887
1888/* ========================================================================= */
1889   int  twist_f_on_corner(int  corner)
1890/* ------------------------------------------------------------------------- */
1891
1892{
1893int                     temp_arr[8];
1894
1895
1896corner_unpack(corner, temp_arr);
1897four_cycle(temp_arr, CORNER_DFL, CORNER_DRF, CORNER_UFR, CORNER_ULF);
1898corner_adjust(temp_arr, CORNER_DFL, CORNER_DRF, CORNER_UFR, CORNER_ULF);
1899
1900return corner_pack(temp_arr);
1901}
1902
1903
1904/* ========================================================================= */
1905   int  twist_r_on_corner(int  corner)
1906/* ------------------------------------------------------------------------- */
1907
1908{
1909int                     temp_arr[8];
1910
1911
1912corner_unpack(corner, temp_arr);
1913four_cycle(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_URB, CORNER_UFR);
1914corner_adjust(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_URB, CORNER_UFR);
1915
1916return corner_pack(temp_arr);
1917}
1918
1919
1920/* ========================================================================= */
1921   int  twist_u_on_corner(int  corner)
1922/* ------------------------------------------------------------------------- */
1923
1924{
1925int                     temp_arr[8];
1926
1927
1928corner_unpack(corner, temp_arr);
1929four_cycle(temp_arr, CORNER_UFR, CORNER_URB, CORNER_UBL, CORNER_ULF);
1930
1931return corner_pack(temp_arr);
1932}
1933
1934
1935/* ========================================================================= */
1936   int  twist_b_on_corner(int  corner)
1937/* ------------------------------------------------------------------------- */
1938
1939{
1940int                     temp_arr[8];
1941
1942
1943corner_unpack(corner, temp_arr);
1944four_cycle(temp_arr, CORNER_DBR, CORNER_DLB, CORNER_UBL, CORNER_URB);
1945corner_adjust(temp_arr, CORNER_DBR, CORNER_DLB, CORNER_UBL, CORNER_URB);
1946
1947return corner_pack(temp_arr);
1948}
1949
1950
1951/* ========================================================================= */
1952   int  twist_l_on_corner(int  corner)
1953/* ------------------------------------------------------------------------- */
1954
1955{
1956int                     temp_arr[8];
1957
1958
1959corner_unpack(corner, temp_arr);
1960four_cycle(temp_arr, CORNER_DLB, CORNER_DFL, CORNER_ULF, CORNER_UBL);
1961corner_adjust(temp_arr, CORNER_DLB, CORNER_DFL, CORNER_ULF, CORNER_UBL);
1962
1963return corner_pack(temp_arr);
1964}
1965
1966
1967/* ========================================================================= */
1968   int  twist_d_on_corner(int  corner)
1969/* ------------------------------------------------------------------------- */
1970
1971{
1972int                     temp_arr[8];
1973
1974
1975corner_unpack(corner, temp_arr);
1976four_cycle(temp_arr, CORNER_DFL, CORNER_DLB, CORNER_DBR, CORNER_DRF);
1977
1978return corner_pack(temp_arr);
1979}
1980
1981
1982/* ========================================================================= */
1983   void  init_twist_on_corner(void)
1984/* ------------------------------------------------------------------------- */
1985
1986{
1987int                     twist, corner;
1988
1989
1990/*  allocate and initialize global array   twist_on_corner    */
1991
1992twist_on_corner[0] =
1993          (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_CORNER]));
1994if (twist_on_corner[0] == NULL)
1995   exit_w_error_message("init_twist_on_corner : couldn't get memory");
1996
1997for (twist = 1; twist < N_TWIST; twist++)
1998    twist_on_corner[twist] = &twist_on_corner[0][twist * N_CORNER];
1999
2000for (corner = 0; corner < N_CORNER; corner++)
2001    {
2002    twist_on_corner[TWIST_F][corner] =
2003                                     (unsigned short)twist_f_on_corner(corner);
2004    twist_on_corner[TWIST_R][corner] =
2005                                     (unsigned short)twist_r_on_corner(corner);
2006    twist_on_corner[TWIST_U][corner] =
2007                                     (unsigned short)twist_u_on_corner(corner);
2008    twist_on_corner[TWIST_B][corner] =
2009                                     (unsigned short)twist_b_on_corner(corner);
2010    twist_on_corner[TWIST_L][corner] =
2011                                     (unsigned short)twist_l_on_corner(corner);
2012    twist_on_corner[TWIST_D][corner] =
2013                                     (unsigned short)twist_d_on_corner(corner);
2014    }
2015for (corner = 0; corner < N_CORNER; corner++)
2016    {
2017    twist_on_corner[TWIST_F2][corner] =
2018              twist_on_corner[TWIST_F][(int)twist_on_corner[TWIST_F][corner]];
2019    twist_on_corner[TWIST_R2][corner] =
2020              twist_on_corner[TWIST_R][(int)twist_on_corner[TWIST_R][corner]];
2021    twist_on_corner[TWIST_U2][corner] =
2022              twist_on_corner[TWIST_U][(int)twist_on_corner[TWIST_U][corner]];
2023    twist_on_corner[TWIST_B2][corner] =
2024              twist_on_corner[TWIST_B][(int)twist_on_corner[TWIST_B][corner]];
2025    twist_on_corner[TWIST_L2][corner] =
2026              twist_on_corner[TWIST_L][(int)twist_on_corner[TWIST_L][corner]];
2027    twist_on_corner[TWIST_D2][corner] =
2028              twist_on_corner[TWIST_D][(int)twist_on_corner[TWIST_D][corner]];
2029    }
2030for (corner = 0; corner < N_CORNER; corner++)
2031    {
2032    twist_on_corner[TWIST_F3][corner] =
2033              twist_on_corner[TWIST_F2][(int)twist_on_corner[TWIST_F][corner]];
2034    twist_on_corner[TWIST_R3][corner] =
2035              twist_on_corner[TWIST_R2][(int)twist_on_corner[TWIST_R][corner]];
2036    twist_on_corner[TWIST_U3][corner] =
2037              twist_on_corner[TWIST_U2][(int)twist_on_corner[TWIST_U][corner]];
2038    twist_on_corner[TWIST_B3][corner] =
2039              twist_on_corner[TWIST_B2][(int)twist_on_corner[TWIST_B][corner]];
2040    twist_on_corner[TWIST_L3][corner] =
2041              twist_on_corner[TWIST_L2][(int)twist_on_corner[TWIST_L][corner]];
2042    twist_on_corner[TWIST_D3][corner] =
2043              twist_on_corner[TWIST_D2][(int)twist_on_corner[TWIST_D][corner]];
2044    }
2045
2046return;
2047}
2048
2049
2050/* ========================================================================= */
2051   int  sym_cu_on_corner(int  corner)
2052/* ------------------------------------------------------------------------- */
2053
2054{
2055int                     temp_arr[8];
2056
2057
2058corner_unpack(corner, temp_arr);
2059four_cycle(temp_arr, CORNER_UFR, CORNER_URB, CORNER_UBL, CORNER_ULF);
2060four_cycle(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_DLB, CORNER_DFL);
2061
2062return corner_pack(temp_arr);
2063}
2064
2065
2066/* ========================================================================= */
2067   int  sym_cf2_on_corner(int  corner)
2068/* ------------------------------------------------------------------------- */
2069
2070{
2071int                     temp_arr[8];
2072
2073
2074corner_unpack(corner, temp_arr);
2075two_cycle(temp_arr, CORNER_UFR, CORNER_DFL);
2076two_cycle(temp_arr, CORNER_ULF, CORNER_DRF);
2077two_cycle(temp_arr, CORNER_UBL, CORNER_DBR);
2078two_cycle(temp_arr, CORNER_URB, CORNER_DLB);
2079
2080return corner_pack(temp_arr);
2081}
2082
2083
2084/* ========================================================================= */
2085   int  sym_rud_on_corner(int  corner)
2086/* ------------------------------------------------------------------------- */
2087
2088{
2089int                     temp_arr[8], ii;
2090
2091
2092corner_unpack(corner, temp_arr);
2093two_cycle(temp_arr, CORNER_UFR, CORNER_DRF);
2094two_cycle(temp_arr, CORNER_ULF, CORNER_DFL);
2095two_cycle(temp_arr, CORNER_UBL, CORNER_DLB);
2096two_cycle(temp_arr, CORNER_URB, CORNER_DBR);
2097
2098for (ii = 0; ii < 8; ii++)
2099    temp_arr[ii] = (2 * temp_arr[ii]) % 3;
2100
2101return corner_pack(temp_arr);
2102}
2103
2104
2105/* ========================================================================= */
2106   void  init_sym_on_corner(void)
2107/* ------------------------------------------------------------------------- */
2108
2109{
2110int                     corner, sym;
2111
2112
2113/*  allocate and initialize global array   sym_on_corner    */
2114
2115sym_on_corner[0] =
2116            (unsigned short *)malloc(sizeof(unsigned short [N_SYM][N_CORNER]));
2117if (sym_on_corner[0] == NULL)
2118   exit_w_error_message("init_sym_on_corner : couldn't get memory");
2119
2120for (sym = 1; sym < N_SYM; sym++)
2121    sym_on_corner[sym] = &sym_on_corner[0][sym * N_CORNER];
2122
2123for (corner = 0; corner < N_CORNER; corner++)
2124    sym_on_corner[0][corner] = (unsigned short)corner;
2125
2126for (corner = 0; corner < N_CORNER; corner++)
2127    sym_on_corner[1][corner] = (unsigned short)sym_cu_on_corner(corner);
2128
2129for (sym = 2; sym < 4; sym++)
2130    for (corner = 0; corner < N_CORNER; corner++)
2131        sym_on_corner[sym][corner] =
2132                         sym_on_corner[1][(int)sym_on_corner[sym - 1][corner]];
2133
2134for (corner = 0; corner < N_CORNER; corner++)
2135    sym_on_corner[4][corner] = (unsigned short)sym_cf2_on_corner(corner);
2136
2137for (sym = 5; sym < 8; sym++)
2138    for (corner = 0; corner < N_CORNER; corner++)
2139        sym_on_corner[sym][corner] =
2140                         sym_on_corner[4][(int)sym_on_corner[sym - 4][corner]];
2141
2142for (corner = 0; corner < N_CORNER; corner++)
2143    sym_on_corner[8][corner] = (unsigned short)sym_rud_on_corner(corner);
2144
2145for (sym = 9; sym < 16; sym++)
2146    for (corner = 0; corner < N_CORNER; corner++)
2147        sym_on_corner[sym][corner] =
2148                         sym_on_corner[8][(int)sym_on_corner[sym - 8][corner]];
2149
2150return;
2151}
2152
2153
2154/* ========================================================================= */
2155   void  calc_edgeloc_conv(int  conv_tab[N_ELOC], int  unconv_tab[N_ELOC_CONV])
2156/* ------------------------------------------------------------------------- */
2157
2158{
2159int                     ii, loc0, loc1, loc2, loc3, count;
2160
2161
2162for (ii = 0; ii < N_ELOC; ii++)
2163    conv_tab[ii] = -1;
2164
2165for (ii = 0; ii < N_ELOC_CONV; ii++)
2166    unconv_tab[ii] = -1;
2167
2168count = 0;
2169for (loc0 = 0; loc0 < 9; loc0++)
2170    for (loc1 = loc0 + 1; loc1 < 10; loc1++)
2171        for (loc2 = loc1 + 1; loc2 < 11; loc2++)
2172            for (loc3 = loc2 + 1; loc3 < 12; loc3++)
2173                {
2174                if (count >= N_ELOC)
2175                   exit_w_error_message("calc_edgeloc_conv : too many eloc's");
2176                conv_tab[count] = (1 << loc0) | (1 << loc1) |
2177                                  (1 << loc2) | (1 << loc3);
2178                unconv_tab[conv_tab[count]] = count;
2179                count++;
2180                }
2181
2182if (count != N_ELOC)
2183   exit_w_error_message("calc_edgeloc_conv : wrong number of  eloc's");
2184
2185return;
2186}
2187
2188
2189/* ========================================================================= */
2190   int  edgeloc_conv_or_unconv(int  eloc_conv_or_unconv, int  convert_flag)
2191/* ------------------------------------------------------------------------- */
2192
2193{
2194static int              eloc_conv[N_ELOC];
2195static int              eloc_unconv[N_ELOC_CONV];
2196static int              initialized = 0;
2197int                     el_conv, el_unconv;
2198
2199
2200if (initialized == 0)
2201   {
2202   calc_edgeloc_conv(eloc_conv, eloc_unconv);
2203   initialized = 1;
2204   }
2205
2206if (convert_flag)
2207   {
2208   if ((eloc_conv_or_unconv < 0) || (eloc_conv_or_unconv >= N_ELOC))
2209      exit_w_error_message("edgeloc_conv_or_unconv : invalid input");
2210
2211   el_conv = eloc_conv[eloc_conv_or_unconv];
2212
2213   if (el_conv < 0)
2214      exit_w_error_message("edgeloc_conv_or_unconv : corrupted data");
2215
2216   return el_conv;
2217   }
2218else
2219   {
2220   if ((eloc_conv_or_unconv < 0) || (eloc_conv_or_unconv >= N_ELOC_CONV))
2221      exit_w_error_message("edgeloc_conv_or_unconv : invalid input");
2222
2223   el_unconv = eloc_unconv[eloc_conv_or_unconv];
2224
2225   if (el_unconv < 0)
2226      exit_w_error_message("edgeloc_conv_or_unconv : corrupted data");
2227
2228   return el_unconv;
2229   }
2230}
2231
2232
2233/* ========================================================================= */
2234   int  edgeloc_conv(int  eloc_unconv)
2235/* ------------------------------------------------------------------------- */
2236
2237{
2238return edgeloc_conv_or_unconv(eloc_unconv, 1);
2239}
2240
2241
2242/* ========================================================================= */
2243   int  edgeloc_unconv(int  eloc_conv)
2244/* ------------------------------------------------------------------------- */
2245
2246{
2247return edgeloc_conv_or_unconv(eloc_conv, 0);
2248}
2249
2250
2251/* ========================================================================= */
2252   void  eloc_unpack(int  eloc, int  array_out[12])
2253/* ------------------------------------------------------------------------- */
2254
2255/*  input:  eloc
2256   output:  array_out[]  */
2257
2258{
2259int                     conv, ii;
2260
2261
2262conv = edgeloc_conv(eloc);
2263
2264for (ii = 0; ii < 12; ii++)
2265    {
2266    array_out[ii] = conv % 2;
2267    conv = conv / 2;
2268    }
2269
2270return;
2271}
2272
2273
2274/* ========================================================================= */
2275   int  eloc_pack(int  array_in[12])
2276/* ------------------------------------------------------------------------- */
2277
2278{
2279int                     ii, conv;
2280
2281
2282conv = 0;
2283for (ii = 11; ii >= 0; ii--)
2284    conv = 2 * conv + array_in[ii];
2285
2286return edgeloc_unconv(conv);
2287}
2288
2289
2290/* ========================================================================= */
2291   int  twist_f_on_eloc(int  eloc)
2292/* ------------------------------------------------------------------------- */
2293
2294{
2295int                     temp_arr[12];
2296
2297
2298eloc_unpack(eloc, temp_arr);
2299four_cycle(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);
2300
2301return eloc_pack(temp_arr);
2302}
2303
2304
2305/* ========================================================================= */
2306   int  twist_r_on_eloc(int  eloc)
2307/* ------------------------------------------------------------------------- */
2308
2309{
2310int                     temp_arr[12];
2311
2312
2313eloc_unpack(eloc, temp_arr);
2314four_cycle(temp_arr, EDGE_FR, EDGE_DR, EDGE_BR, EDGE_UR);
2315
2316return eloc_pack(temp_arr);
2317}
2318
2319
2320/* ========================================================================= */
2321   int  twist_u_on_eloc(int  eloc)
2322/* ------------------------------------------------------------------------- */
2323
2324{
2325int                     temp_arr[12];
2326
2327
2328eloc_unpack(eloc, temp_arr);
2329four_cycle(temp_arr, EDGE_UF, EDGE_UR, EDGE_UB, EDGE_UL);
2330
2331return eloc_pack(temp_arr);
2332}
2333
2334
2335/* ========================================================================= */
2336   int  twist_b_on_eloc(int  eloc)
2337/* ------------------------------------------------------------------------- */
2338
2339{
2340int                     temp_arr[12];
2341
2342
2343eloc_unpack(eloc, temp_arr);
2344four_cycle(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);
2345
2346return eloc_pack(temp_arr);
2347}
2348
2349
2350/* ========================================================================= */
2351   int  twist_l_on_eloc(int  eloc)
2352/* ------------------------------------------------------------------------- */
2353
2354{
2355int                     temp_arr[12];
2356
2357
2358eloc_unpack(eloc, temp_arr);
2359four_cycle(temp_arr, EDGE_BL, EDGE_DL, EDGE_FL, EDGE_UL);
2360
2361return eloc_pack(temp_arr);
2362}
2363
2364
2365/* ========================================================================= */
2366   int  twist_d_on_eloc(int  eloc)
2367/* ------------------------------------------------------------------------- */
2368
2369{
2370int                     temp_arr[12];
2371
2372
2373eloc_unpack(eloc, temp_arr);
2374four_cycle(temp_arr, EDGE_DF, EDGE_DL, EDGE_DB, EDGE_DR);
2375
2376return eloc_pack(temp_arr);
2377}
2378
2379
2380/* ========================================================================= */
2381   void  calc_twist_on_eloc(int  table[N_TWIST][N_ELOC])
2382/* ------------------------------------------------------------------------- */
2383
2384{
2385int                     edgeloc;
2386
2387
2388for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
2389    {
2390    table[TWIST_F][edgeloc] = twist_f_on_eloc(edgeloc);
2391    table[TWIST_R][edgeloc] = twist_r_on_eloc(edgeloc);
2392    table[TWIST_U][edgeloc] = twist_u_on_eloc(edgeloc);
2393    table[TWIST_B][edgeloc] = twist_b_on_eloc(edgeloc);
2394    table[TWIST_L][edgeloc] = twist_l_on_eloc(edgeloc);
2395    table[TWIST_D][edgeloc] = twist_d_on_eloc(edgeloc);
2396    }
2397
2398perm_n_compose(N_ELOC, table[TWIST_F], table[TWIST_F], table[TWIST_F2]);
2399perm_n_compose(N_ELOC, table[TWIST_R], table[TWIST_R], table[TWIST_R2]);
2400perm_n_compose(N_ELOC, table[TWIST_U], table[TWIST_U], table[TWIST_U2]);
2401perm_n_compose(N_ELOC, table[TWIST_B], table[TWIST_B], table[TWIST_B2]);
2402perm_n_compose(N_ELOC, table[TWIST_L], table[TWIST_L], table[TWIST_L2]);
2403perm_n_compose(N_ELOC, table[TWIST_D], table[TWIST_D], table[TWIST_D2]);
2404
2405perm_n_compose(N_ELOC, table[TWIST_F2], table[TWIST_F], table[TWIST_F3]);
2406perm_n_compose(N_ELOC, table[TWIST_R2], table[TWIST_R], table[TWIST_R3]);
2407perm_n_compose(N_ELOC, table[TWIST_U2], table[TWIST_U], table[TWIST_U3]);
2408perm_n_compose(N_ELOC, table[TWIST_B2], table[TWIST_B], table[TWIST_B3]);
2409perm_n_compose(N_ELOC, table[TWIST_L2], table[TWIST_L], table[TWIST_L3]);
2410perm_n_compose(N_ELOC, table[TWIST_D2], table[TWIST_D], table[TWIST_D3]);
2411
2412return;
2413}
2414
2415
2416/* ========================================================================= */
2417   int  sym_cu_on_eloc(int  eloc)
2418/* ------------------------------------------------------------------------- */
2419
2420{
2421int                     temp_arr[12];
2422
2423
2424eloc_unpack(eloc, temp_arr);
2425four_cycle(temp_arr, EDGE_UF, EDGE_UR, EDGE_UB, EDGE_UL);
2426four_cycle(temp_arr, EDGE_DF, EDGE_DR, EDGE_DB, EDGE_DL);
2427four_cycle(temp_arr, EDGE_FR, EDGE_BR, EDGE_BL, EDGE_FL);
2428
2429return eloc_pack(temp_arr);
2430}
2431
2432
2433/* ========================================================================= */
2434   int  sym_cf2_on_eloc(int  eloc)
2435/* ------------------------------------------------------------------------- */
2436
2437{
2438int                     temp_arr[12];
2439
2440
2441eloc_unpack(eloc, temp_arr);
2442two_cycle(temp_arr, EDGE_UF, EDGE_DF);
2443two_cycle(temp_arr, EDGE_UR, EDGE_DL);
2444two_cycle(temp_arr, EDGE_UB, EDGE_DB);
2445two_cycle(temp_arr, EDGE_UL, EDGE_DR);
2446two_cycle(temp_arr, EDGE_FR, EDGE_FL);
2447two_cycle(temp_arr, EDGE_BR, EDGE_BL);
2448
2449return eloc_pack(temp_arr);
2450}
2451
2452
2453/* ========================================================================= */
2454   int  sym_rud_on_eloc(int  eloc)
2455/* ------------------------------------------------------------------------- */
2456
2457{
2458int                     temp_arr[12];
2459
2460
2461eloc_unpack(eloc, temp_arr);
2462two_cycle(temp_arr, EDGE_UF, EDGE_DF);
2463two_cycle(temp_arr, EDGE_UR, EDGE_DR);
2464two_cycle(temp_arr, EDGE_UB, EDGE_DB);
2465two_cycle(temp_arr, EDGE_UL, EDGE_DL);
2466
2467return eloc_pack(temp_arr);
2468}
2469
2470
2471/* ========================================================================= */
2472   void  calc_sym_on_eloc(int  table[N_SYM][N_ELOC])
2473/* ------------------------------------------------------------------------- */
2474
2475{
2476int                     edgeloc, sym;
2477
2478
2479perm_n_init(N_ELOC, table[0]);
2480
2481for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
2482    table[1][edgeloc] = sym_cu_on_eloc(edgeloc);
2483
2484for (sym = 2; sym < 4; sym++)
2485    perm_n_compose(N_ELOC, table[1], table[sym - 1], table[sym]);
2486
2487for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
2488    table[4][edgeloc] = sym_cf2_on_eloc(edgeloc);
2489
2490for (sym = 5; sym < 8; sym++)
2491    perm_n_compose(N_ELOC, table[4], table[sym - 4], table[sym]);
2492
2493for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
2494    table[8][edgeloc] = sym_rud_on_eloc(edgeloc);
2495
2496for (sym = 9; sym < 16; sym++)
2497    perm_n_compose(N_ELOC, table[8], table[sym - 8], table[sym]);
2498
2499return;
2500}
2501
2502
2503/* ========================================================================= */
2504   void  eflip_unpack(int  eflip, int  array_out[12])
2505/* ------------------------------------------------------------------------- */
2506
2507{
2508int                     ii;
2509
2510
2511for (ii = 0; ii < 11; ii++)
2512    {
2513    array_out[ii] = eflip % 2;
2514    eflip = eflip / 2;
2515    }
2516
2517array_out[11] = (array_out[0] + array_out[1] + array_out[2] + array_out[3] +
2518                 array_out[4] + array_out[5] + array_out[6] + array_out[7] +
2519                 array_out[8] + array_out[9] + array_out[10]) % 2;
2520
2521return;
2522}
2523
2524
2525/* ========================================================================= */
2526   int  eflip_pack(int  array_in[12])
2527/* ------------------------------------------------------------------------- */
2528
2529{
2530int                     eflip, ii;
2531
2532
2533eflip = 0;
2534for (ii = 10; ii >= 0; ii--)
2535    eflip = 2 * eflip + array_in[ii];
2536
2537return eflip;
2538}
2539
2540
2541/* ========================================================================= */
2542   void  eflip_adjust(int  array[12], int  ind0, int  ind1, int  ind2,
2543                                                            int  ind3)
2544/* ------------------------------------------------------------------------- */
2545
2546{
2547array[ind0] = 1 - array[ind0];
2548array[ind1] = 1 - array[ind1];
2549array[ind2] = 1 - array[ind2];
2550array[ind3] = 1 - array[ind3];
2551
2552return;
2553}
2554
2555
2556/* ========================================================================= */
2557   int  twist_f_on_eflip(int  eflip)
2558/* ------------------------------------------------------------------------- */
2559
2560{
2561int                     temp_arr[12];
2562
2563
2564eflip_unpack(eflip, temp_arr);
2565four_cycle(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);
2566eflip_adjust(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);
2567
2568return eflip_pack(temp_arr);
2569}
2570
2571
2572/* ========================================================================= */
2573   int  twist_r_on_eflip(int  eflip)
2574/* ------------------------------------------------------------------------- */
2575
2576{
2577int                     temp_arr[12];
2578
2579
2580eflip_unpack(eflip, temp_arr);
2581four_cycle(temp_arr, EDGE_FR, EDGE_DR, EDGE_BR, EDGE_UR);
2582
2583return eflip_pack(temp_arr);
2584}
2585
2586
2587/* ========================================================================= */
2588   int  twist_u_on_eflip(int  eflip)
2589/* ------------------------------------------------------------------------- */
2590
2591{
2592int                     temp_arr[12];
2593
2594
2595eflip_unpack(eflip, temp_arr);
2596four_cycle(temp_arr, EDGE_UR, EDGE_UB, EDGE_UL, EDGE_UF);
2597
2598return eflip_pack(temp_arr);
2599}
2600
2601
2602/* ========================================================================= */
2603   int  twist_b_on_eflip(int  eflip)
2604/* ------------------------------------------------------------------------- */
2605
2606{
2607int                     temp_arr[12];
2608
2609
2610eflip_unpack(eflip, temp_arr);
2611four_cycle(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);
2612eflip_adjust(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);
2613
2614return eflip_pack(temp_arr);
2615}
2616
2617
2618/* ========================================================================= */
2619   int  twist_l_on_eflip(int  eflip)
2620/* ------------------------------------------------------------------------- */
2621
2622{
2623int                     temp_arr[12];
2624
2625
2626eflip_unpack(eflip, temp_arr);
2627four_cycle(temp_arr, EDGE_BL, EDGE_DL, EDGE_FL, EDGE_UL);
2628
2629return eflip_pack(temp_arr);
2630}
2631
2632
2633/* ========================================================================= */
2634   int  twist_d_on_eflip(int  eflip)
2635/* ------------------------------------------------------------------------- */
2636
2637{
2638int                     temp_arr[12];
2639
2640
2641eflip_unpack(eflip, temp_arr);
2642four_cycle(temp_arr, EDGE_DL, EDGE_DB, EDGE_DR, EDGE_DF);
2643
2644return eflip_pack(temp_arr);
2645}
2646
2647
2648/* ========================================================================= */
2649   void  calc_twist_on_eflip(int  table[N_TWIST][N_EFLIP])
2650/* ------------------------------------------------------------------------- */
2651
2652{
2653int                     edgeflip;
2654
2655
2656for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
2657    {
2658    table[TWIST_F][edgeflip] = twist_f_on_eflip(edgeflip);
2659    table[TWIST_R][edgeflip] = twist_r_on_eflip(edgeflip);
2660    table[TWIST_U][edgeflip] = twist_u_on_eflip(edgeflip);
2661    table[TWIST_B][edgeflip] = twist_b_on_eflip(edgeflip);
2662    table[TWIST_L][edgeflip] = twist_l_on_eflip(edgeflip);
2663    table[TWIST_D][edgeflip] = twist_d_on_eflip(edgeflip);
2664    }
2665
2666perm_n_compose(N_EFLIP, table[TWIST_F], table[TWIST_F], table[TWIST_F2]);
2667perm_n_compose(N_EFLIP, table[TWIST_R], table[TWIST_R], table[TWIST_R2]);
2668perm_n_compose(N_EFLIP, table[TWIST_U], table[TWIST_U], table[TWIST_U2]);
2669perm_n_compose(N_EFLIP, table[TWIST_B], table[TWIST_B], table[TWIST_B2]);
2670perm_n_compose(N_EFLIP, table[TWIST_L], table[TWIST_L], table[TWIST_L2]);
2671perm_n_compose(N_EFLIP, table[TWIST_D], table[TWIST_D], table[TWIST_D2]);
2672
2673perm_n_compose(N_EFLIP, table[TWIST_F2], table[TWIST_F], table[TWIST_F3]);
2674perm_n_compose(N_EFLIP, table[TWIST_R2], table[TWIST_R], table[TWIST_R3]);
2675perm_n_compose(N_EFLIP, table[TWIST_U2], table[TWIST_U], table[TWIST_U3]);
2676perm_n_compose(N_EFLIP, table[TWIST_B2], table[TWIST_B], table[TWIST_B3]);
2677perm_n_compose(N_EFLIP, table[TWIST_L2], table[TWIST_L], table[TWIST_L3]);
2678perm_n_compose(N_EFLIP, table[TWIST_D2], table[TWIST_D], table[TWIST_D3]);
2679
2680return;
2681}
2682
2683
2684/* ========================================================================= */
2685   int  sym_cu2_on_eflip(int  eflip)
2686/* ------------------------------------------------------------------------- */
2687
2688{
2689int                     temp_arr[12];
2690
2691
2692eflip_unpack(eflip, temp_arr);
2693two_cycle(temp_arr, EDGE_UF, EDGE_UB);
2694two_cycle(temp_arr, EDGE_UR, EDGE_UL);
2695two_cycle(temp_arr, EDGE_DF, EDGE_DB);
2696two_cycle(temp_arr, EDGE_DR, EDGE_DL);
2697two_cycle(temp_arr, EDGE_FR, EDGE_BL);
2698two_cycle(temp_arr, EDGE_FL, EDGE_BR);
2699
2700return eflip_pack(temp_arr);
2701}
2702
2703
2704/* ========================================================================= */
2705   int  sym_cf2_on_eflip(int  eflip)
2706/* ------------------------------------------------------------------------- */
2707
2708{
2709int                     temp_arr[12];
2710
2711
2712eflip_unpack(eflip, temp_arr);
2713two_cycle(temp_arr, EDGE_UF, EDGE_DF);
2714two_cycle(temp_arr, EDGE_UR, EDGE_DL);
2715two_cycle(temp_arr, EDGE_UB, EDGE_DB);
2716two_cycle(temp_arr, EDGE_UL, EDGE_DR);
2717two_cycle(temp_arr, EDGE_FR, EDGE_FL);
2718two_cycle(temp_arr, EDGE_BR, EDGE_BL);
2719
2720return eflip_pack(temp_arr);
2721}
2722
2723
2724/* ========================================================================= */
2725   int  sym_rud_on_eflip(int  eflip)
2726/* ------------------------------------------------------------------------- */
2727
2728{
2729int                     temp_arr[12];
2730
2731
2732eflip_unpack(eflip, temp_arr);
2733two_cycle(temp_arr, EDGE_UF, EDGE_DF);
2734two_cycle(temp_arr, EDGE_UR, EDGE_DR);
2735two_cycle(temp_arr, EDGE_UB, EDGE_DB);
2736two_cycle(temp_arr, EDGE_UL, EDGE_DL);
2737
2738return eflip_pack(temp_arr);
2739}
2740
2741
2742/* ========================================================================= */
2743   void  calc_sym_on_eflip(int  table[N_SYM / 2][N_EFLIP])
2744/* ------------------------------------------------------------------------- */
2745
2746{
2747int                     edgeflip, sym;
2748
2749
2750perm_n_init(N_EFLIP, table[0]);
2751
2752for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
2753    table[1][edgeflip] = sym_cu2_on_eflip(edgeflip);
2754
2755for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
2756    table[2][edgeflip] = sym_cf2_on_eflip(edgeflip);
2757
2758perm_n_compose(N_EFLIP, table[2], table[1], table[3]);
2759
2760for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
2761    table[4][edgeflip] = sym_rud_on_eflip(edgeflip);
2762
2763for (sym = 5; sym < 8; sym++)
2764    perm_n_compose(N_EFLIP, table[4], table[sym - 4], table[sym]);
2765
2766return;
2767}
2768
2769
2770/* ========================================================================= */
2771   int  sym_cu_on_fulledge(int  fulledge)
2772/* ------------------------------------------------------------------------- */
2773
2774{
2775int                     edgeloc_arr[12], edgeflip_arr[12], temp_arr[12], ii;
2776
2777
2778eloc_unpack(fulledge / N_EFLIP, edgeloc_arr);
2779eflip_unpack(fulledge % N_EFLIP, edgeflip_arr);
2780
2781for (ii = 0; ii < 12; ii++)
2782    temp_arr[ii] = (edgeloc_arr[ii] != edgeflip_arr[ii]);
2783
2784four_cycle(temp_arr, EDGE_UR, EDGE_UB, EDGE_UL, EDGE_UF);
2785four_cycle(temp_arr, EDGE_DR, EDGE_DB, EDGE_DL, EDGE_DF);
2786four_cycle(temp_arr, EDGE_BR, EDGE_BL, EDGE_FL, EDGE_FR);
2787eflip_adjust(temp_arr, EDGE_FR, EDGE_FL, EDGE_BR, EDGE_BL);
2788
2789return sym_cu_on_eloc(fulledge / N_EFLIP) * N_EFLIP + eflip_pack(temp_arr);
2790}
2791
2792
2793/* ========================================================================= */
2794   void  init_fulledge_to_edgequot(int  sym_on_eloc[N_SYM][N_ELOC],
2795                                   int  sym_on_eflip[N_SYM / 2][N_EFLIP],
2796                                   int  edge_to_fulledge[N_EDGEQUOT],
2797                                   int  stabilizers[N_EDGEQUOT],
2798                                   int  multiplicities[N_EDGEQUOT])
2799/* ------------------------------------------------------------------------- */
2800
2801{
2802int                     count, sym_count, fulledge, cu_fulledge, sym, min_sym;
2803int                     min_full, new_full, stab;
2804
2805
2806fulledge_to_edge =
2807                 (unsigned short *)malloc(sizeof(unsigned short [N_FULLEDGE]));
2808fulledge_to_sym = (unsigned char *)malloc(sizeof(unsigned char [N_FULLEDGE]));
2809
2810if ((fulledge_to_edge == NULL) || (fulledge_to_sym == NULL))
2811   exit_w_error_message("init_fulledge_to_edgequot : couldn't get memory");
2812
2813count = 0;
2814
2815for (fulledge = 0; fulledge < N_FULLEDGE; fulledge++)
2816    {
2817    min_full = fulledge;
2818    min_sym = 0;
2819    stab = 0;
2820    sym_count = 0;
2821    cu_fulledge = sym_cu_on_fulledge(fulledge);
2822
2823    for (sym = 0; sym < (N_SYM / 2); sym++)
2824        {
2825        new_full = sym_on_eloc[2 * sym][fulledge / N_EFLIP] * N_EFLIP +
2826                                         sym_on_eflip[sym][fulledge % N_EFLIP];
2827        if (min_full > new_full)
2828           {
2829           min_full = new_full;
2830           min_sym = 2 * sym;
2831           }
2832        else if (min_full == new_full)
2833           {
2834           stab |= (1 << (2 * sym));
2835           sym_count++;
2836           }
2837
2838        new_full = sym_on_eloc[2 * sym][cu_fulledge / N_EFLIP] * N_EFLIP +
2839                                      sym_on_eflip[sym][cu_fulledge % N_EFLIP];
2840        if (min_full > new_full)
2841           {
2842           min_full = new_full;
2843           min_sym = 2 * sym + 1;
2844           }
2845        else if (min_full == new_full)
2846           {
2847           stab |= (1 << (2 * sym + 1));
2848           sym_count++;
2849           }
2850        }
2851
2852    if (min_sym == 0)
2853       {
2854       if (count >= N_EDGEQUOT)
2855          exit_w_error_message(
2856                           "init_fulledge_to_edgequot : too many  edgequot's");
2857       edge_to_fulledge[count] = fulledge;
2858       stabilizers[count] = stab;
2859       multiplicities[count] = N_SYM / sym_count;
2860       fulledge_to_edge[fulledge] = (unsigned short)count;
2861       fulledge_to_sym[fulledge] = sym_x_invsym_to_sym[0][0];
2862       count++;
2863       }
2864    else
2865       {
2866       fulledge_to_edge[fulledge] = fulledge_to_edge[min_full];
2867       fulledge_to_sym[fulledge] = sym_x_invsym_to_sym[0][min_sym];
2868       }
2869    }
2870
2871if (count != N_EDGEQUOT)
2872   exit_w_error_message(
2873                    "init_fulledge_to_edgequot : wrong number of  edgequot's");
2874
2875return;
2876}
2877
2878
2879/* ========================================================================= */
2880   void  init_twist_on_edge(int  twist_on_eloc[N_TWIST][N_ELOC],
2881                            int  twist_on_eflip[N_TWIST][N_EFLIP],
2882                            int  edge_to_fulledge[N_EDGEQUOT])
2883/* ------------------------------------------------------------------------- */
2884
2885{
2886int                     twist, edge, fulledge, new_edge;
2887
2888
2889/*  allocate and initialize global arrays         */
2890/*  twist_on_edge   and    twist_x_edge_to_sym    */
2891
2892twist_on_edge[0] =
2893        (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_EDGEQUOT]));
2894twist_x_edge_to_sym[0] =
2895          (unsigned char *)malloc(sizeof(unsigned char [N_TWIST][N_EDGEQUOT]));
2896
2897if ((twist_on_edge[0] == NULL) || (twist_x_edge_to_sym[0] == NULL))
2898   exit_w_error_message("init_twist_on_edge : couldn't get memory");
2899
2900for (twist = 1; twist < N_TWIST; twist++)
2901    {
2902    twist_on_edge[twist] = &twist_on_edge[0][twist * N_EDGEQUOT];
2903    twist_x_edge_to_sym[twist] = &twist_x_edge_to_sym[0][twist * N_EDGEQUOT];
2904    }
2905
2906for (twist = 0; twist < N_TWIST; twist++)
2907    for (edge = 0; edge < N_EDGEQUOT; edge++)
2908        {
2909        fulledge = edge_to_fulledge[edge];
2910        new_edge = twist_on_eloc[twist][fulledge / N_EFLIP] * N_EFLIP +
2911                                   twist_on_eflip[twist][fulledge % N_EFLIP];
2912        twist_on_edge[twist][edge] = fulledge_to_edge[new_edge];
2913        twist_x_edge_to_sym[twist][edge] =
2914                        sym_x_invsym_to_sym[0][(int)fulledge_to_sym[new_edge]];
2915        }
2916
2917return;
2918}
2919
2920
2921/* ========================================================================= */
2922   void  init_edge_quotient(int  stabilizers[N_EDGEQUOT],
2923                            int  multiplicities[N_EDGEQUOT])
2924/* ------------------------------------------------------------------------- */
2925
2926{
2927int                     twist_on_eloc[N_TWIST][N_ELOC];
2928int                     twist_on_eflip[N_TWIST][N_EFLIP];
2929int                     sym_on_eloc[N_SYM][N_ELOC];
2930int                     sym_on_eflip[N_SYM / 2][N_EFLIP];
2931int                     edge_to_fulledge[N_EDGEQUOT];
2932
2933
2934calc_twist_on_eloc(twist_on_eloc);
2935calc_sym_on_eloc(sym_on_eloc);
2936calc_twist_on_eflip(twist_on_eflip);
2937calc_sym_on_eflip(sym_on_eflip);
2938init_fulledge_to_edgequot(sym_on_eloc, sym_on_eflip, edge_to_fulledge,
2939                                                  stabilizers, multiplicities);
2940init_twist_on_edge(twist_on_eloc, twist_on_eflip, edge_to_fulledge);
2941
2942return;
2943}
2944
2945
2946/* ========================================================================= */
2947   void  cornerperm_unpack(int  cperm, int  array_out[8])
2948/* ------------------------------------------------------------------------- */
2949
2950{
2951perm_n_unpack(8, cperm, array_out);
2952
2953return;
2954}
2955
2956
2957/* ========================================================================= */
2958   int  cornerperm_pack(int  array_in[8])
2959/* ------------------------------------------------------------------------- */
2960
2961{
2962return perm_n_pack(8, array_in);
2963}
2964
2965
2966/* ========================================================================= */
2967   int  twist_f_on_cperm(int  cperm)
2968/* ------------------------------------------------------------------------- */
2969
2970{
2971int                     temp_arr[8];
2972
2973
2974cornerperm_unpack(cperm, temp_arr);
2975four_cycle(temp_arr, CORNER_DFL, CORNER_DRF, CORNER_UFR, CORNER_ULF);
2976
2977return cornerperm_pack(temp_arr);
2978}
2979
2980
2981/* ========================================================================= */
2982   int  twist_r_on_cperm(int  cperm)
2983/* ------------------------------------------------------------------------- */
2984
2985{
2986int                     temp_arr[8];
2987
2988
2989cornerperm_unpack(cperm, temp_arr);
2990four_cycle(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_URB, CORNER_UFR);
2991
2992return cornerperm_pack(temp_arr);
2993}
2994
2995
2996/* ========================================================================= */
2997   int  twist_u_on_cperm(int  cperm)
2998/* ------------------------------------------------------------------------- */
2999
3000{
3001int                     temp_arr[8];
3002
3003
3004cornerperm_unpack(cperm, temp_arr);
3005four_cycle(temp_arr, CORNER_URB, CORNER_UBL, CORNER_ULF, CORNER_UFR);
3006
3007return cornerperm_pack(temp_arr);
3008}
3009
3010
3011/* ========================================================================= */
3012   int  twist_b_on_cperm(int  cperm)
3013/* ------------------------------------------------------------------------- */
3014
3015{
3016int                     temp_arr[8];
3017
3018
3019cornerperm_unpack(cperm, temp_arr);
3020four_cycle(temp_arr, CORNER_DBR, CORNER_DLB, CORNER_UBL, CORNER_URB);
3021
3022return cornerperm_pack(temp_arr);
3023}
3024
3025
3026/* ========================================================================= */
3027   int  twist_l_on_cperm(int  cperm)
3028/* ------------------------------------------------------------------------- */
3029
3030{
3031int                     temp_arr[8];
3032
3033
3034cornerperm_unpack(cperm, temp_arr);
3035four_cycle(temp_arr, CORNER_DLB, CORNER_DFL, CORNER_ULF, CORNER_UBL);
3036
3037return cornerperm_pack(temp_arr);
3038}
3039
3040
3041/* ========================================================================= */
3042   int  twist_d_on_cperm(int  cperm)
3043/* ------------------------------------------------------------------------- */
3044
3045{
3046int                     temp_arr[8];
3047
3048
3049cornerperm_unpack(cperm, temp_arr);
3050four_cycle(temp_arr, CORNER_DFL, CORNER_DLB, CORNER_DBR, CORNER_DRF);
3051
3052return cornerperm_pack(temp_arr);
3053}
3054
3055
3056/* ========================================================================= */
3057   void  init_twist_on_cornerperm(void)
3058/* ------------------------------------------------------------------------- */
3059
3060{
3061int                     cp, twist;
3062
3063
3064/*  allocate and initialize global array    twist_on_cornerperm    */
3065
3066twist_on_cornerperm[0] =
3067      (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_CORNERPERM]));
3068if (twist_on_cornerperm[0] == NULL)
3069   exit_w_error_message("init_twist_on_cornerperm : couldn't get memory");
3070
3071for (twist = 1; twist < N_TWIST; twist++)
3072    twist_on_cornerperm[twist] = &twist_on_cornerperm[0][twist * N_CORNERPERM];
3073
3074for (cp = 0; cp < N_CORNERPERM; cp++)
3075    {
3076    twist_on_cornerperm[TWIST_F][cp] = (unsigned short)twist_f_on_cperm(cp);
3077    twist_on_cornerperm[TWIST_R][cp] = (unsigned short)twist_r_on_cperm(cp);
3078    twist_on_cornerperm[TWIST_U][cp] = (unsigned short)twist_u_on_cperm(cp);
3079    twist_on_cornerperm[TWIST_B][cp] = (unsigned short)twist_b_on_cperm(cp);
3080    twist_on_cornerperm[TWIST_L][cp] = (unsigned short)twist_l_on_cperm(cp);
3081    twist_on_cornerperm[TWIST_D][cp] = (unsigned short)twist_d_on_cperm(cp);
3082    }
3083for (cp = 0; cp < N_CORNERPERM; cp++)
3084    {
3085    twist_on_cornerperm[TWIST_F2][cp] =
3086          twist_on_cornerperm[TWIST_F][(int)twist_on_cornerperm[TWIST_F][cp]];
3087    twist_on_cornerperm[TWIST_R2][cp] =
3088          twist_on_cornerperm[TWIST_R][(int)twist_on_cornerperm[TWIST_R][cp]];
3089    twist_on_cornerperm[TWIST_U2][cp] =
3090          twist_on_cornerperm[TWIST_U][(int)twist_on_cornerperm[TWIST_U][cp]];
3091    twist_on_cornerperm[TWIST_B2][cp] =
3092          twist_on_cornerperm[TWIST_B][(int)twist_on_cornerperm[TWIST_B][cp]];
3093    twist_on_cornerperm[TWIST_L2][cp] =
3094          twist_on_cornerperm[TWIST_L][(int)twist_on_cornerperm[TWIST_L][cp]];
3095    twist_on_cornerperm[TWIST_D2][cp] =
3096          twist_on_cornerperm[TWIST_D][(int)twist_on_cornerperm[TWIST_D][cp]];
3097    }
3098for (cp = 0; cp < N_CORNERPERM; cp++)
3099    {
3100    twist_on_cornerperm[TWIST_F3][cp] =
3101          twist_on_cornerperm[TWIST_F2][(int)twist_on_cornerperm[TWIST_F][cp]];
3102    twist_on_cornerperm[TWIST_R3][cp] =
3103          twist_on_cornerperm[TWIST_R2][(int)twist_on_cornerperm[TWIST_R][cp]];
3104    twist_on_cornerperm[TWIST_U3][cp] =
3105          twist_on_cornerperm[TWIST_U2][(int)twist_on_cornerperm[TWIST_U][cp]];
3106    twist_on_cornerperm[TWIST_B3][cp] =
3107          twist_on_cornerperm[TWIST_B2][(int)twist_on_cornerperm[TWIST_B][cp]];
3108    twist_on_cornerperm[TWIST_L3][cp] =
3109          twist_on_cornerperm[TWIST_L2][(int)twist_on_cornerperm[TWIST_L][cp]];
3110    twist_on_cornerperm[TWIST_D3][cp] =
3111          twist_on_cornerperm[TWIST_D2][(int)twist_on_cornerperm[TWIST_D][cp]];
3112    }
3113
3114return;
3115}
3116
3117
3118/* ========================================================================= */
3119   void  sliceedge_unpack(int  sliceedge, int  array_out[12])
3120/* ------------------------------------------------------------------------- */
3121
3122{
3123int                     temp_arr[4], ii, count;
3124
3125
3126eloc_unpack(sliceedge % N_ELOC, array_out);
3127perm_n_unpack(4, sliceedge / N_ELOC, temp_arr);
3128
3129count = 0;
3130for (ii = 0; ii < 12; ii++)
3131    if (array_out[ii] != 0)
3132       {
3133       if (count >= 4)
3134          exit_w_error_message("sliceedge_unpack : corrupted data");
3135
3136       array_out[ii] = 1 + temp_arr[count++];
3137       }
3138
3139return;
3140}
3141
3142
3143/* ========================================================================= */
3144   int  sliceedge_pack(int  array_in[12])
3145/* ------------------------------------------------------------------------- */
3146
3147{
3148int                     eloc_arr[12], temp_arr[4], ii, count;
3149
3150
3151count = 0;
3152for (ii = 0; ii < 12; ii++)
3153    {
3154    if (array_in[ii] != 0)
3155       {
3156       if (count >= 4)
3157          exit_w_error_message("sliceedge_pack : invalid input");
3158
3159       temp_arr[count++] = array_in[ii] - 1;
3160       }
3161
3162    eloc_arr[ii] = (array_in[ii] != 0);
3163    }
3164
3165return perm_n_pack(4, temp_arr) * N_ELOC + eloc_pack(eloc_arr);
3166}
3167
3168
3169/* ========================================================================= */
3170   int  twist_f_on_sliceedge(int  sliceedge)
3171/* ------------------------------------------------------------------------- */
3172
3173{
3174int                     temp_arr[12];
3175
3176
3177sliceedge_unpack(sliceedge, temp_arr);
3178four_cycle(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);
3179
3180return sliceedge_pack(temp_arr);
3181}
3182
3183
3184/* ========================================================================= */
3185   int  twist_r_on_sliceedge(int  sliceedge)
3186/* ------------------------------------------------------------------------- */
3187
3188{
3189int                     temp_arr[12];
3190
3191
3192sliceedge_unpack(sliceedge, temp_arr);
3193four_cycle(temp_arr, EDGE_FR, EDGE_DR, EDGE_BR, EDGE_UR);
3194
3195return sliceedge_pack(temp_arr);
3196}
3197
3198
3199/* ========================================================================= */
3200   int  twist_u_on_sliceedge(int  sliceedge)
3201/* ------------------------------------------------------------------------- */
3202
3203{
3204int                     temp_arr[12];
3205
3206
3207sliceedge_unpack(sliceedge, temp_arr);
3208four_cycle(temp_arr, EDGE_UR, EDGE_UB, EDGE_UL, EDGE_UF);
3209
3210return sliceedge_pack(temp_arr);
3211}
3212
3213
3214/* ========================================================================= */
3215   int  twist_b_on_sliceedge(int  sliceedge)
3216/* ------------------------------------------------------------------------- */
3217
3218{
3219int                     temp_arr[12];
3220
3221
3222sliceedge_unpack(sliceedge, temp_arr);
3223four_cycle(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);
3224
3225return sliceedge_pack(temp_arr);
3226}
3227
3228
3229/* ========================================================================= */
3230   int  twist_l_on_sliceedge(int  sliceedge)
3231/* ------------------------------------------------------------------------- */
3232
3233{
3234int                     temp_arr[12];
3235
3236
3237sliceedge_unpack(sliceedge, temp_arr);
3238four_cycle(temp_arr, EDGE_BL, EDGE_DL, EDGE_FL, EDGE_UL);
3239
3240return sliceedge_pack(temp_arr);
3241}
3242
3243
3244/* ========================================================================= */
3245   int  twist_d_on_sliceedge(int  sliceedge)
3246/* ------------------------------------------------------------------------- */
3247
3248{
3249int                     temp_arr[12];
3250
3251
3252sliceedge_unpack(sliceedge, temp_arr);
3253four_cycle(temp_arr, EDGE_DL, EDGE_DB, EDGE_DR, EDGE_DF);
3254
3255return sliceedge_pack(temp_arr);
3256}
3257
3258
3259/* ========================================================================= */
3260   void  init_twist_on_sliceedge(void)
3261/* ------------------------------------------------------------------------- */
3262
3263{
3264int                     twist, sl;
3265
3266
3267/*  allocate and initialize global array    twist_on_sliceedge    */
3268
3269twist_on_sliceedge[0] =
3270     (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_SLICEEDGE]));
3271if (twist_on_sliceedge[0] == NULL)
3272   exit_w_error_message("init_twist_on_sliceedge : couldn't get memory");
3273
3274for (twist = 1; twist < N_TWIST; twist++)
3275    twist_on_sliceedge[twist] = &twist_on_sliceedge[0][twist * N_SLICEEDGE];
3276
3277for (sl = 0; sl < N_SLICEEDGE; sl++)
3278    {
3279    twist_on_sliceedge[TWIST_F][sl] = (unsigned short)twist_f_on_sliceedge(sl);
3280    twist_on_sliceedge[TWIST_R][sl] = (unsigned short)twist_r_on_sliceedge(sl);
3281    twist_on_sliceedge[TWIST_U][sl] = (unsigned short)twist_u_on_sliceedge(sl);
3282    twist_on_sliceedge[TWIST_B][sl] = (unsigned short)twist_b_on_sliceedge(sl);
3283    twist_on_sliceedge[TWIST_L][sl] = (unsigned short)twist_l_on_sliceedge(sl);
3284    twist_on_sliceedge[TWIST_D][sl] = (unsigned short)twist_d_on_sliceedge(sl);
3285    }
3286for (sl = 0; sl < N_SLICEEDGE; sl++)
3287    {
3288    twist_on_sliceedge[TWIST_F2][sl] =
3289            twist_on_sliceedge[TWIST_F][(int)twist_on_sliceedge[TWIST_F][sl]];
3290    twist_on_sliceedge[TWIST_R2][sl] =
3291            twist_on_sliceedge[TWIST_R][(int)twist_on_sliceedge[TWIST_R][sl]];
3292    twist_on_sliceedge[TWIST_U2][sl] =
3293            twist_on_sliceedge[TWIST_U][(int)twist_on_sliceedge[TWIST_U][sl]];
3294    twist_on_sliceedge[TWIST_B2][sl] =
3295            twist_on_sliceedge[TWIST_B][(int)twist_on_sliceedge[TWIST_B][sl]];
3296    twist_on_sliceedge[TWIST_L2][sl] =
3297            twist_on_sliceedge[TWIST_L][(int)twist_on_sliceedge[TWIST_L][sl]];
3298    twist_on_sliceedge[TWIST_D2][sl] =
3299            twist_on_sliceedge[TWIST_D][(int)twist_on_sliceedge[TWIST_D][sl]];
3300    }
3301for (sl = 0; sl < N_SLICEEDGE; sl++)
3302    {
3303    twist_on_sliceedge[TWIST_F3][sl] =
3304            twist_on_sliceedge[TWIST_F2][(int)twist_on_sliceedge[TWIST_F][sl]];
3305    twist_on_sliceedge[TWIST_R3][sl] =
3306            twist_on_sliceedge[TWIST_R2][(int)twist_on_sliceedge[TWIST_R][sl]];
3307    twist_on_sliceedge[TWIST_U3][sl] =
3308            twist_on_sliceedge[TWIST_U2][(int)twist_on_sliceedge[TWIST_U][sl]];
3309    twist_on_sliceedge[TWIST_B3][sl] =
3310            twist_on_sliceedge[TWIST_B2][(int)twist_on_sliceedge[TWIST_B][sl]];
3311    twist_on_sliceedge[TWIST_L3][sl] =
3312            twist_on_sliceedge[TWIST_L2][(int)twist_on_sliceedge[TWIST_L][sl]];
3313    twist_on_sliceedge[TWIST_D3][sl] =
3314            twist_on_sliceedge[TWIST_D2][(int)twist_on_sliceedge[TWIST_D][sl]];
3315    }
3316
3317return;
3318}
3319
3320
3321/* ========================================================================= */
3322   int  make_current(int  corner, int  edge, Search_data  *p_data)
3323/* ------------------------------------------------------------------------- */
3324
3325{
3326if (DIST(corner, edge) > p_data->depth)
3327   {
3328   if (edge & 0x1)
3329      {
3330      distance[corner][edge >> 1] &= 0x0F;
3331      distance[corner][edge >> 1] |= (unsigned char)((p_data->depth) << 4);
3332      }
3333   else
3334      {
3335      distance[corner][edge >> 1] &= 0xF0;
3336      distance[corner][edge >> 1] |= (unsigned char)(p_data->depth);
3337      }
3338
3339   p_data->found_quot++;
3340   p_data->found += (p_data->multiplicities)[edge];
3341
3342   return 1;
3343   }
3344
3345return 0;
3346}
3347
3348
3349/* ========================================================================= */
3350   void  make_current_all(int  corner, int  edge, Search_data  *p_data)
3351/* ------------------------------------------------------------------------- */
3352
3353{
3354int                     sym, stab;
3355
3356
3357if (make_current(corner, edge, p_data))
3358   {
3359   stab = (p_data->stabilizers)[edge];
3360   for (sym = 1; sym < N_SYM; sym++)
3361       {
3362       stab /= 2;
3363
3364       if (stab % 2)
3365          make_current((int)sym_on_corner[sym][corner], edge, p_data);
3366       }
3367   }
3368
3369return;
3370}
3371
3372
3373/* ========================================================================= */
3374   void  make_neighbors_current(int  corner, int  edge, Search_data  *p_data)
3375/* ------------------------------------------------------------------------- */
3376
3377{
3378int                     twist, new_edge, new_corner, sym;
3379
3380
3381for (twist = 0; twist < N_TWIST; twist++)
3382    {
3383    if (p_current_metric->twist_length[twist] != 1)
3384       continue;
3385
3386    new_edge = (int)twist_on_edge[twist][edge];
3387    sym = (int)twist_x_edge_to_sym[twist][edge];
3388    new_corner = (int)sym_on_corner[sym][(int)twist_on_corner[twist][corner]];
3389    make_current_all(new_corner, new_edge, p_data);
3390    }
3391
3392return;
3393}
3394
3395
3396/* ========================================================================= */
3397   int  neighbors_are_previous(int  corner, int  edge, Search_data  *p_data)
3398/* ------------------------------------------------------------------------- */
3399
3400{
3401int                     twist, new_edge, sym, new_corner;
3402
3403
3404for (twist = 0; twist < N_TWIST; twist++)
3405    {
3406    if (p_current_metric->twist_length[twist] != 1)
3407       continue;
3408
3409    new_edge = (int)twist_on_edge[twist][edge];
3410    sym = (int)twist_x_edge_to_sym[twist][edge];
3411    new_corner = (int)sym_on_corner[sym][(int)twist_on_corner[twist][corner]];
3412
3413    if (DIST(new_corner, new_edge) < p_data->depth)
3414       return 1;
3415    }
3416
3417return 0;
3418}
3419
3420
3421/* ========================================================================= */
3422   void  init_distance_table(int  edge_stabilizers[N_EDGEQUOT],
3423                             int  edge_multiplicities[N_EDGEQUOT])
3424/* ------------------------------------------------------------------------- */
3425
3426{
3427Search_data             sdata_struc;
3428int                     total_found_quot, corner, edge, ii, msg_given;
3429
3430
3431/*  allocate and initialize global array   distance   */
3432
3433distance[0] = (unsigned char *)malloc(sizeof(unsigned char [N_DIST_CHARS]));
3434if (distance[0] == NULL)
3435   exit_w_error_message("init_distance_table : couldn't get memory");
3436
3437for (corner = 1; corner < N_CORNER; corner++)
3438    distance[corner] = &distance[0][corner * (N_EDGEQUOT / 2)];
3439
3440for (ii = 0; ii < N_DIST_CHARS; ii++)
3441    distance[0][ii] = (unsigned char)255;
3442
3443msg_given = 0;
3444
3445sdata_struc.depth = 0;
3446sdata_struc.found_quot = 0;
3447sdata_struc.found = 0;
3448sdata_struc.stabilizers = edge_stabilizers;
3449sdata_struc.multiplicities = edge_multiplicities;
3450total_found_quot = 0;
3451
3452printf("distance     positions     (quotient)\n");
3453
3454make_current_all(CORNER_START, EDGE_START, &sdata_struc);
3455
3456while (sdata_struc.found)
3457      {
3458      printf("%7d%c %13d     (%8d)\n", sdata_struc.depth,
3459                      p_current_metric->metric_char, sdata_struc.found,
3460                                                       sdata_struc.found_quot);
3461      total_found_quot += sdata_struc.found_quot;
3462      sdata_struc.found_quot = 0;
3463      sdata_struc.found = 0;
3464
3465      if (++(sdata_struc.depth) == 15)
3466         break;                            /*  shouldn't happen  */
3467
3468      if (total_found_quot == 2 * N_DIST_CHARS)
3469         break;
3470
3471      if (total_found_quot < BACKWARDS_SWITCH_POINT)  /*  search forward  */
3472         {
3473         for (corner = 0; corner < N_CORNER; corner++)
3474             for (edge = 0; edge < N_EDGEQUOT; edge++)
3475                 if (DIST(corner, edge) == sdata_struc.depth - 1)
3476                    make_neighbors_current(corner, edge, &sdata_struc);
3477         }
3478      else  /*  search backward  */
3479         {
3480         if (msg_given == 0)
3481            {
3482            printf("     switching to backwards searching\n");
3483            msg_given = 1;
3484            }
3485
3486         for (corner = 0; corner < N_CORNER; corner++)
3487             for (edge = 0; edge < N_EDGEQUOT; edge++)
3488                 if ((DIST(corner, edge) == 15) &&
3489                     neighbors_are_previous(corner, edge, &sdata_struc))
3490                    make_current_all(corner, edge, &sdata_struc);
3491         }
3492      }
3493
3494return;
3495}
3496
3497
3498/* ========================================================================= */
3499   void  init_globals(void)
3500/* ------------------------------------------------------------------------- */
3501
3502{
3503int                    *edge_stabilizers;
3504int                    *edge_multiplicities;
3505
3506
3507printf("initializing transformation tables\n");
3508init_sym_x_invsym_to_sym();
3509init_invsym_on_twist();
3510init_twist_on_follow();
3511init_twist_on_corner();
3512init_sym_on_corner();
3513
3514edge_stabilizers = (int *)malloc(sizeof(int [2 * N_EDGEQUOT]));
3515if (edge_stabilizers == NULL)
3516   exit_w_error_message("init_globals : couldn't get memory");
3517
3518edge_multiplicities = &edge_stabilizers[N_EDGEQUOT];
3519
3520init_edge_quotient(edge_stabilizers, edge_multiplicities);
3521init_twist_on_cornerperm();
3522init_twist_on_sliceedge();
3523printf("initializing distance table ... this will take several minutes\n");
3524init_distance_table(edge_stabilizers, edge_multiplicities);
3525
3526free((void *)edge_stabilizers);
3527
3528return;
3529}
3530
3531
3532/* ========================================================================= */
3533   int  string_to_cube(char  string[], Cube  *p_cube, int  give_err_msg)
3534/* ------------------------------------------------------------------------- */
3535
3536/*  input:  string[]  */
3537
3538{
3539char                    edge_str[12][3], corner_str[8][4];
3540int                     edge_arr[12], corner_arr[8];
3541int                     ii, jj, twist, flip, edge_par, corner_par, stat;
3542
3543
3544stat = 0;
3545
3546if (sscanf(string, "%2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %3s %3s %3s %3s %3s %3s %3s %3s",
3547           edge_str[0], edge_str[1], edge_str[2], edge_str[3],
3548           edge_str[4], edge_str[5], edge_str[6], edge_str[7],
3549           edge_str[8], edge_str[9], edge_str[10], edge_str[11],
3550           corner_str[0], corner_str[1], corner_str[2], corner_str[3],
3551           corner_str[4], corner_str[5], corner_str[6], corner_str[7]) < 20)
3552   {
3553   if (give_err_msg)
3554      printf("invalid input!\n");
3555   return 1;
3556   }
3557
3558for (ii = 0; ii < 12; ii++)
3559    {
3560    for (jj = 0; jj < 24; jj++)
3561        if (strcmp(edge_str[ii], edge_cubie_str[jj]) == 0)
3562           {
3563           p_cube->edges[ii] = jj;
3564           break;
3565           }
3566    if (jj == 24)
3567       {
3568       if (give_err_msg)
3569          printf("invalid edge cubie: %s\n", edge_str[ii]);
3570       stat = 1;
3571       }
3572    }
3573
3574for (ii = 0; ii < 8; ii++)
3575    {
3576    for (jj = 0; jj < 24; jj++)
3577        if (strcmp(corner_str[ii], corner_cubie_str[jj]) == 0)
3578           {
3579           p_cube->corners[ii] = jj;
3580           break;
3581           }
3582    if (jj == 24)
3583       {
3584       if (give_err_msg)
3585          printf("invalid corner cubie: %s\n", corner_str[ii]);
3586       stat = 1;
3587       }
3588    }
3589
3590if (stat)
3591   return stat;
3592
3593/*  fill out the remaining oriented edges and corners  */
3594
3595for (ii = 12; ii < 24; ii++)
3596    p_cube->edges[ii] = (12 + p_cube->edges[ii - 12]) % 24;
3597
3598for (ii = 8; ii < 24; ii++)
3599    p_cube->corners[ii] = (8 + p_cube->corners[ii - 8]) % 24;
3600
3601/*  now check to see that it's a legal cube  */
3602
3603if (perm_n_check(24, p_cube->edges))
3604   {
3605   if (give_err_msg)
3606      printf("bad edge cubies\n");
3607   stat = 1;
3608   }
3609
3610if (perm_n_check(24, p_cube->corners))
3611   {
3612   if (give_err_msg)
3613      printf("bad corner cubies\n");
3614   stat = 1;
3615   }
3616
3617if (stat)
3618   return stat;
3619
3620flip = 0;
3621for (ii = 0; ii < 12; ii++)
3622    flip += (p_cube->edges[ii] / 12);
3623
3624if ((flip % 2) != 0)
3625   {
3626   if (give_err_msg)
3627      printf("flip any edge cubie!\n");
3628   stat = 1;
3629   }
3630
3631twist = 0;
3632for (ii = 0; ii < 8; ii++)
3633    twist += (p_cube->corners[ii] / 8);
3634
3635twist %= 3;
3636
3637if (twist != 0)
3638   {
3639   if (give_err_msg)
3640      printf("twist any corner cubie %sclockwise!\n",
3641              (twist == 1) ? "counter" : "");
3642   stat = 1;
3643   }
3644
3645for (ii = 0; ii < 12; ii++)
3646    edge_arr[ii] = p_cube->edges[ii] % 12;
3647
3648edge_par = perm_n_parity(12, edge_arr);
3649
3650for (ii = 0; ii < 8; ii++)
3651    corner_arr[ii] = p_cube->corners[ii] % 8;
3652
3653corner_par = perm_n_parity(8, corner_arr);
3654
3655if (edge_par != corner_par)
3656   {
3657   if (give_err_msg)
3658      printf("swap any two edge cubies or any two corner cubies!\n");
3659   stat = 1;
3660   }
3661
3662return stat;
3663}
3664
3665
3666/* ========================================================================= */
3667   int  user_enters_cube(Cube  *p_cube)
3668/* ------------------------------------------------------------------------- */
3669
3670{
3671char                     line_str[256];
3672
3673
3674printf("\nenter cube (Ctrl-D to exit):\n");
3675
3676line_str[0] = '\n';
3677
3678while (line_str[0] == '\n')           /*  ignore blank lines  */
3679      {
3680      if (fgets(line_str, 256, stdin) == NULL)
3681         return -1;
3682
3683      if (line_str[0] == '%')         /*  echo comments  */
3684         {
3685         printf("%s", line_str);
3686         line_str[0] = '\n';
3687         }
3688      }
3689
3690return string_to_cube(line_str, p_cube, 1);
3691}
3692
3693
3694/* ========================================================================= */
3695   void  calc_cube_urf(Cube  *p_cube)
3696/* ------------------------------------------------------------------------- */
3697
3698{
3699cube_init(p_cube);
3700three_cycle(p_cube->edges, EDGE_UF, EDGE_FR, EDGE_RU);
3701three_cycle(p_cube->edges, EDGE_UB, EDGE_FL, EDGE_RD);
3702three_cycle(p_cube->edges, EDGE_DB, EDGE_BL, EDGE_LD);
3703three_cycle(p_cube->edges, EDGE_DF, EDGE_BR, EDGE_LU);
3704three_cycle(p_cube->edges, EDGE_FU, EDGE_RF, EDGE_UR);
3705three_cycle(p_cube->edges, EDGE_BU, EDGE_LF, EDGE_DR);
3706three_cycle(p_cube->edges, EDGE_BD, EDGE_LB, EDGE_DL);
3707three_cycle(p_cube->edges, EDGE_FD, EDGE_RB, EDGE_UL);
3708three_cycle(p_cube->corners, CORNER_UFR, CORNER_FRU, CORNER_RUF);
3709three_cycle(p_cube->corners, CORNER_DLB, CORNER_BDL, CORNER_LBD);
3710three_cycle(p_cube->corners, CORNER_URB, CORNER_FUL, CORNER_RFD);
3711three_cycle(p_cube->corners, CORNER_UBL, CORNER_FLD, CORNER_RDB);
3712three_cycle(p_cube->corners, CORNER_RBU, CORNER_ULF, CORNER_FDR);
3713three_cycle(p_cube->corners, CORNER_BLU, CORNER_LDF, CORNER_DBR);
3714three_cycle(p_cube->corners, CORNER_BUR, CORNER_LFU, CORNER_DRF);
3715three_cycle(p_cube->corners, CORNER_LUB, CORNER_DFL, CORNER_BRD);
3716
3717return;
3718}
3719
3720
3721/* ========================================================================= */
3722   void  cube_to_coset_coord(Cube  *p_cube, Coset_coord  *p_coset_coord)
3723/* ------------------------------------------------------------------------- */
3724
3725/*  output:  *p_coset_coord  */
3726
3727{
3728int                     corner_arr[8], edge_arr[12];
3729int                     ii, eflip, eloc, sym, corner;
3730
3731
3732for (ii = 0; ii < 12; ii++)
3733    edge_arr[ii] = p_cube->edges[ii] / 12;
3734eflip = eflip_pack(edge_arr);
3735
3736for (ii = 0; ii < 12; ii++)
3737    edge_arr[ii] = (p_cube->edges[ii] % 12) / 8;
3738eloc = eloc_pack(edge_arr);
3739
3740p_coset_coord->edge_state = (int)fulledge_to_edge[eloc * N_EFLIP + eflip];
3741p_coset_coord->sym_state = sym = (int)fulledge_to_sym[eloc * N_EFLIP + eflip];
3742
3743for (ii = 0; ii < 8; ii++)
3744    corner_arr[ii] = p_cube->corners[ii] / 8;
3745
3746corner = corner_pack(corner_arr);
3747p_coset_coord->corner_state =
3748                  (int)sym_on_corner[(int)sym_x_invsym_to_sym[0][sym]][corner];
3749
3750return;
3751}
3752
3753
3754/* ========================================================================= */
3755   void  process_full_cube(Full_cube  *p_cube)
3756/* ------------------------------------------------------------------------- */
3757
3758{
3759Cube                    cube1, cube2, cube_urf;
3760int                     edges_to_ud[12], edges_to_rl[12], edges_to_fb[12];
3761int                     cornerperm_arr[8], sliceedge_arr[12], ii;
3762
3763
3764/*  p_cube->cubies  already filled in  */
3765/*  fill in other fields of  p_cube    */
3766
3767for (ii = 0; ii < 8; ii++)
3768    cornerperm_arr[ii] = p_cube->cubies.corners[ii] % 8;
3769
3770p_cube->cornerperm = cornerperm_pack(cornerperm_arr);
3771p_cube->parity = perm_n_parity(8, cornerperm_arr);
3772
3773
3774for (ii = 0; ii < 12; ii++)
3775    edges_to_ud[ii] = edges_to_fb[ii] = edges_to_rl[ii] = 0;
3776
3777edges_to_ud[EDGE_FR] = 1;
3778edges_to_ud[EDGE_FL] = 2;
3779edges_to_ud[EDGE_BR] = 3;
3780edges_to_ud[EDGE_BL] = 4;
3781
3782edges_to_rl[EDGE_UF] = 1;
3783edges_to_rl[EDGE_UB] = 2;
3784edges_to_rl[EDGE_DF] = 3;
3785edges_to_rl[EDGE_DB] = 4;
3786
3787edges_to_fb[EDGE_UR] = 1;
3788edges_to_fb[EDGE_UL] = 2;
3789edges_to_fb[EDGE_DR] = 3;
3790edges_to_fb[EDGE_DL] = 4;
3791
3792
3793for (ii = 0; ii < 12; ii++)
3794    sliceedge_arr[ii] = edges_to_ud[(p_cube->cubies.edges[ii]) % 12];
3795p_cube->ud_sliceedge = sliceedge_pack(sliceedge_arr);
3796
3797for (ii = 0; ii < 12; ii++)
3798    sliceedge_arr[ii] = edges_to_fb[(p_cube->cubies.edges[ii]) % 12];
3799p_cube->fb_sliceedge = sliceedge_pack(sliceedge_arr);
3800
3801for (ii = 0; ii < 12; ii++)
3802    sliceedge_arr[ii] = edges_to_rl[(p_cube->cubies.edges[ii]) % 12];
3803p_cube->rl_sliceedge = sliceedge_pack(sliceedge_arr);
3804
3805
3806cube_to_coset_coord(&p_cube->cubies, &p_cube->ud);
3807
3808calc_cube_urf(&cube_urf);
3809
3810cube_conjugate(&p_cube->cubies, &cube_urf, &cube1);
3811cube_to_coset_coord(&cube1, &p_cube->rl);
3812
3813cube_conjugate(&cube1, &cube_urf, &cube2);
3814cube_to_coset_coord(&cube2, &p_cube->fb);
3815
3816return;
3817}
3818
3819
3820/* ========================================================================= */
3821   void  set_cube_symmetry(Full_cube  *p_cube, Cube  sym_cubes[N_CUBESYM],
3822                           int  subgroup_list[N_SYMSUBGRP][N_CUBESYM])
3823/* ------------------------------------------------------------------------- */
3824
3825{
3826Cube                    temp_cube;
3827int                     subgroup[N_CUBESYM], sym, count;
3828
3829
3830if (p_current_options->use_symmetry)
3831   {
3832   count = 0;
3833
3834   for (sym = 0; sym < N_CUBESYM; sym++)
3835       {
3836       cube_conjugate(&p_cube->cubies, &sym_cubes[sym], &temp_cube);
3837       subgroup[sym] = (cube_compare(&p_cube->cubies, &temp_cube) == 0);
3838       if (subgroup[sym])
3839          count++;
3840       }
3841
3842   p_cube->sym_subgrp = which_subgroup(subgroup, subgroup_list);
3843
3844   if (p_cube->sym_subgrp < 0)
3845      exit_w_error_message("set_cube_symmetry : unknown symmetry group");
3846
3847   if (count > 1)
3848      printf("position has %d-fold symmetry (subgroup #%d)\n", count,
3849                                                           p_cube->sym_subgrp);
3850   else
3851      printf("asymmetric position\n");
3852   }
3853else
3854   p_cube->sym_subgrp = SUBGRP_TRIVIAL;
3855
3856return;
3857}
3858
3859
3860/* ========================================================================= */
3861   void  output_solution(Search_node  *node_arr)
3862/* ------------------------------------------------------------------------- */
3863
3864{
3865static char            *twist_string[] = {"F ", "F2", "F'", "R ", "R2", "R'",
3866                                          "U ", "U2", "U'", "B ", "B2", "B'",
3867                                          "L ", "L2", "L'", "D ", "D2", "D'"};
3868Search_node            *p_node;
3869int                     turn_list[MAX_TWISTS];
3870int                     ii, count, q_length, f_length;
3871
3872
3873count = 0;
3874
3875for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
3876    turn_list[count++] = p_node[1].twist;
3877
3878q_length = f_length = 0;
3879
3880for (ii = 0; ii < count; ii++)
3881    {
3882    q_length += metric_q_length(turn_list[ii]);
3883    f_length += metric_f_length(turn_list[ii]);
3884    }
3885
3886for (ii = 0; ii < count; ii++)
3887    printf(" %s", twist_string[turn_list[ii]]);
3888
3889if (p_current_metric->metric == QUARTER_TURN_METRIC)
3890   printf("  (%dq*, %df)\n", q_length, f_length);
3891else
3892   printf("  (%df*, %dq)\n", f_length, q_length);
3893fflush(stdout);
3894
3895sol_found = 1;
3896
3897return;
3898}
3899
3900
3901/* ========================================================================= */
3902   int  test_for_solution(Full_cube  *p_cube, Search_node  *node_arr)
3903/* ------------------------------------------------------------------------- */
3904
3905{
3906register Search_node   *p_node;
3907register int            cornerperm, sliceedge;
3908
3909
3910n_tests++;
3911
3912cornerperm = p_cube->cornerperm;
3913for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
3914    cornerperm = (int)twist_on_cornerperm[p_node[1].twist][cornerperm];
3915
3916if (cornerperm != CORNERPERM_START)
3917   return 0;                                  /*  not a solution  */
3918
3919sliceedge = p_cube->ud_sliceedge;
3920for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
3921    sliceedge = (int)twist_on_sliceedge[p_node[1].twist][sliceedge];
3922
3923if (sliceedge != UD_SLICEEDGE_START)
3924   return 0;                                  /*  not a solution  */
3925
3926sliceedge = p_cube->rl_sliceedge;
3927for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
3928    sliceedge = (int)twist_on_sliceedge[p_node[1].twist][sliceedge];
3929
3930if (sliceedge != RL_SLICEEDGE_START)
3931   return 0;                                  /*  not a solution  */
3932
3933sliceedge = p_cube->fb_sliceedge;
3934for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
3935    sliceedge = (int)twist_on_sliceedge[p_node[1].twist][sliceedge];
3936
3937if (sliceedge != FB_SLICEEDGE_START)
3938   return 0;                                  /*  not a solution  */
3939
3940output_solution(node_arr);                    /*  solution !  */
3941
3942return 1;
3943}
3944
3945
3946/* ========================================================================= */
3947   void  search_tree(Full_cube  *p_cube, Search_node  *node_arr)
3948/* ------------------------------------------------------------------------- */
3949
3950{
3951register Search_node   *p_node;
3952register int            twist, virtual_twist, new_sym_factor;
3953
3954
3955p_node = node_arr;
3956
3957while (p_node >= node_arr)
3958      {
3959      if (p_node->remain_depth == 0)
3960         {
3961         if (test_for_solution(p_cube, node_arr) &&
3962             p_current_options->one_solution_only)
3963            return;
3964         p_node--;
3965         }
3966      else
3967         {
3968         for (twist = p_node[1].twist + 1; twist < N_TWIST; twist++)
3969             {
3970             p_node[1].follow_type =
3971                              (int)twist_on_follow[twist][p_node->follow_type];
3972
3973             if (p_node[1].follow_type == FOLLOW_INVALID)
3974                continue;
3975
3976             p_node[1].remain_depth = p_node->remain_depth -
3977                                         p_current_metric->twist_length[twist];
3978             if (p_node[1].remain_depth < 0)
3979                continue;
3980
3981             n_nodes++;
3982
3983             virtual_twist =
3984                          (int)invsym_on_twist_ud[p_node->ud.sym_state][twist];
3985             new_sym_factor =
3986                (int)twist_x_edge_to_sym[virtual_twist][p_node->ud.edge_state];
3987             p_node[1].ud.edge_state =
3988                      (int)twist_on_edge[virtual_twist][p_node->ud.edge_state];
3989             p_node[1].ud.sym_state =
3990                (int)sym_x_invsym_to_sym[p_node->ud.sym_state][new_sym_factor];
3991             p_node[1].ud.corner_state = (int)sym_on_corner[new_sym_factor]
3992                [(int)twist_on_corner[virtual_twist][p_node->ud.corner_state]];
3993
3994             if (p_node[1].remain_depth <
3995                      DIST(p_node[1].ud.corner_state, p_node[1].ud.edge_state))
3996                continue;
3997
3998
3999             virtual_twist =
4000                          (int)invsym_on_twist_rl[p_node->rl.sym_state][twist];
4001             new_sym_factor =
4002                (int)twist_x_edge_to_sym[virtual_twist][p_node->rl.edge_state];
4003             p_node[1].rl.edge_state =
4004                      (int)twist_on_edge[virtual_twist][p_node->rl.edge_state];
4005             p_node[1].rl.sym_state =
4006                (int)sym_x_invsym_to_sym[p_node->rl.sym_state][new_sym_factor];
4007             p_node[1].rl.corner_state = (int)sym_on_corner[new_sym_factor]
4008                [(int)twist_on_corner[virtual_twist][p_node->rl.corner_state]];
4009
4010             if (p_node[1].remain_depth <
4011                      DIST(p_node[1].rl.corner_state, p_node[1].rl.edge_state))
4012                continue;
4013
4014
4015             virtual_twist =
4016                          (int)invsym_on_twist_fb[p_node->fb.sym_state][twist];
4017             new_sym_factor =
4018                (int)twist_x_edge_to_sym[virtual_twist][p_node->fb.edge_state];
4019             p_node[1].fb.edge_state =
4020                      (int)twist_on_edge[virtual_twist][p_node->fb.edge_state];
4021             p_node[1].fb.sym_state =
4022                (int)sym_x_invsym_to_sym[p_node->fb.sym_state][new_sym_factor];
4023             p_node[1].fb.corner_state = (int)sym_on_corner[new_sym_factor]
4024                [(int)twist_on_corner[virtual_twist][p_node->fb.corner_state]];
4025
4026             if (p_node[1].remain_depth <
4027                      DIST(p_node[1].fb.corner_state, p_node[1].fb.edge_state))
4028                continue;
4029
4030
4031             p_node[1].twist = twist;
4032             break;
4033             }
4034
4035         if (twist == N_TWIST)
4036            p_node--;
4037         else
4038            {
4039            p_node++;
4040            p_node[1].twist = -1;
4041            }
4042         }
4043      }
4044
4045return;
4046}
4047
4048
4049/* ========================================================================= */
4050   void  calc_sym_cubes(Cube  sym_conj[N_CUBESYM])
4051/* ------------------------------------------------------------------------- */
4052
4053{
4054int                     ii;
4055
4056
4057cube_init(&sym_conj[0]);
4058cube_init(&sym_conj[1]);
4059
4060four_cycle(sym_conj[1].edges, EDGE_UF, EDGE_UL, EDGE_UB, EDGE_UR);
4061four_cycle(sym_conj[1].edges, EDGE_DF, EDGE_DL, EDGE_DB, EDGE_DR);
4062four_cycle(sym_conj[1].edges, EDGE_FR, EDGE_LF, EDGE_BL, EDGE_RB);
4063four_cycle(sym_conj[1].edges, EDGE_FU, EDGE_LU, EDGE_BU, EDGE_RU);
4064four_cycle(sym_conj[1].edges, EDGE_FD, EDGE_LD, EDGE_BD, EDGE_RD);
4065four_cycle(sym_conj[1].edges, EDGE_RF, EDGE_FL, EDGE_LB, EDGE_BR);
4066four_cycle(sym_conj[1].corners, CORNER_UFR, CORNER_ULF, CORNER_UBL, CORNER_URB);
4067four_cycle(sym_conj[1].corners, CORNER_DRF, CORNER_DFL, CORNER_DLB, CORNER_DBR);
4068four_cycle(sym_conj[1].corners, CORNER_FRU, CORNER_LFU, CORNER_BLU, CORNER_RBU);
4069four_cycle(sym_conj[1].corners, CORNER_RFD, CORNER_FLD, CORNER_LBD, CORNER_BRD);
4070four_cycle(sym_conj[1].corners, CORNER_RUF, CORNER_FUL, CORNER_LUB, CORNER_BUR);
4071four_cycle(sym_conj[1].corners, CORNER_FDR, CORNER_LDF, CORNER_BDL, CORNER_RDB);
4072
4073for (ii = 2; ii < 4; ii++)
4074    cube_compose(&sym_conj[1], &sym_conj[ii - 1], &sym_conj[ii]);
4075
4076cube_init(&sym_conj[4]);
4077
4078two_cycle(sym_conj[4].edges, EDGE_UF, EDGE_DF);
4079two_cycle(sym_conj[4].edges, EDGE_UR, EDGE_DL);
4080two_cycle(sym_conj[4].edges, EDGE_UB, EDGE_DB);
4081two_cycle(sym_conj[4].edges, EDGE_UL, EDGE_DR);
4082two_cycle(sym_conj[4].edges, EDGE_FR, EDGE_FL);
4083two_cycle(sym_conj[4].edges, EDGE_BR, EDGE_BL);
4084two_cycle(sym_conj[4].edges, EDGE_FU, EDGE_FD);
4085two_cycle(sym_conj[4].edges, EDGE_RU, EDGE_LD);
4086two_cycle(sym_conj[4].edges, EDGE_BU, EDGE_BD);
4087two_cycle(sym_conj[4].edges, EDGE_LU, EDGE_RD);
4088two_cycle(sym_conj[4].edges, EDGE_RF, EDGE_LF);
4089two_cycle(sym_conj[4].edges, EDGE_RB, EDGE_LB);
4090two_cycle(sym_conj[4].corners, CORNER_UFR, CORNER_DFL);
4091two_cycle(sym_conj[4].corners, CORNER_ULF, CORNER_DRF);
4092two_cycle(sym_conj[4].corners, CORNER_UBL, CORNER_DBR);
4093two_cycle(sym_conj[4].corners, CORNER_URB, CORNER_DLB);
4094two_cycle(sym_conj[4].corners, CORNER_FRU, CORNER_FLD);
4095two_cycle(sym_conj[4].corners, CORNER_LFU, CORNER_RFD);
4096two_cycle(sym_conj[4].corners, CORNER_BLU, CORNER_BRD);
4097two_cycle(sym_conj[4].corners, CORNER_RBU, CORNER_LBD);
4098two_cycle(sym_conj[4].corners, CORNER_RUF, CORNER_LDF);
4099two_cycle(sym_conj[4].corners, CORNER_FUL, CORNER_FDR);
4100two_cycle(sym_conj[4].corners, CORNER_LUB, CORNER_RDB);
4101two_cycle(sym_conj[4].corners, CORNER_BUR, CORNER_BDL);
4102
4103for (ii = 5; ii < 8; ii++)
4104    cube_compose(&sym_conj[4], &sym_conj[ii - 4], &sym_conj[ii]);
4105
4106cube_init(&sym_conj[8]);
4107
4108two_cycle(sym_conj[8].edges, EDGE_UF, EDGE_DF);
4109two_cycle(sym_conj[8].edges, EDGE_UR, EDGE_DR);
4110two_cycle(sym_conj[8].edges, EDGE_UB, EDGE_DB);
4111two_cycle(sym_conj[8].edges, EDGE_UL, EDGE_DL);
4112two_cycle(sym_conj[8].edges, EDGE_FU, EDGE_FD);
4113two_cycle(sym_conj[8].edges, EDGE_RU, EDGE_RD);
4114two_cycle(sym_conj[8].edges, EDGE_BU, EDGE_BD);
4115two_cycle(sym_conj[8].edges, EDGE_LU, EDGE_LD);
4116two_cycle(sym_conj[8].corners, CORNER_UFR, CORNER_DRF);
4117two_cycle(sym_conj[8].corners, CORNER_ULF, CORNER_DFL);
4118two_cycle(sym_conj[8].corners, CORNER_UBL, CORNER_DLB);
4119two_cycle(sym_conj[8].corners, CORNER_URB, CORNER_DBR);
4120two_cycle(sym_conj[8].corners, CORNER_FRU, CORNER_FDR);
4121two_cycle(sym_conj[8].corners, CORNER_LFU, CORNER_LDF);
4122two_cycle(sym_conj[8].corners, CORNER_BLU, CORNER_BDL);
4123two_cycle(sym_conj[8].corners, CORNER_RBU, CORNER_RDB);
4124two_cycle(sym_conj[8].corners, CORNER_RUF, CORNER_RFD);
4125two_cycle(sym_conj[8].corners, CORNER_FUL, CORNER_FLD);
4126two_cycle(sym_conj[8].corners, CORNER_LUB, CORNER_LBD);
4127two_cycle(sym_conj[8].corners, CORNER_BUR, CORNER_BRD);
4128
4129for (ii = 9; ii < 16; ii++)
4130    cube_compose(&sym_conj[8], &sym_conj[ii - 8], &sym_conj[ii]);
4131
4132calc_cube_urf(&sym_conj[16]);
4133
4134for (ii = 17; ii < 48; ii++)
4135    cube_compose(&sym_conj[16], &sym_conj[ii - 16], &sym_conj[ii]);
4136
4137return;
4138}
4139
4140
4141/* ========================================================================= */
4142   void  pretty_print_unsigned_int(unsigned int  nn)
4143/* ------------------------------------------------------------------------- */
4144
4145{
4146int                     digits[4], ii, started;
4147
4148
4149for (ii = 0; ii < 4; ii++)
4150    {
4151    digits[ii] = nn % 1000;
4152    nn /= 1000;
4153    }
4154
4155started = 0;
4156
4157for (ii = 3; ii >= 0; ii--)
4158    {
4159    if (started)
4160       {
4161       if (digits[ii] >= 100)
4162          printf("%3d", digits[ii]);
4163       else if (digits[ii] >= 10)
4164               printf("0%2d", digits[ii]);
4165       else
4166          printf("00%1d", digits[ii]);
4167       }
4168    else
4169       {
4170       if (digits[ii] >= 100)
4171          {
4172          printf("%3d", digits[ii]);
4173          started = 1;
4174          }
4175       else if (digits[ii] >= 10)
4176               {
4177               printf(" %2d", digits[ii]);
4178               started = 1;
4179               }
4180       else if ((digits[ii] >= 1) || (ii == 0))
4181               {
4182               printf("  %1d", digits[ii]);
4183               started = 1;
4184               }
4185       else
4186          printf("   ");
4187       }
4188
4189    if (ii > 0)
4190       printf("%c", started ? ',' : ' ');
4191    }
4192
4193return;
4194}
4195
4196
4197/* ========================================================================= */
4198   void  solve_cube(Cube  *p_cube)
4199/* ------------------------------------------------------------------------- */
4200
4201{
4202static Cube             sym_cubes[N_CUBESYM];
4203static int              subgroup_list[N_SYMSUBGRP][N_CUBESYM];
4204static int              initialized = 0;
4205Full_cube               full_cube_struct;
4206Search_node             node_arr[MAX_TWISTS];
4207int                     ii, start_depth, search_limit;
4208
4209
4210if (initialized == 0)
4211   {
4212   calc_sym_cubes(sym_cubes);
4213   calc_subgroup_list(subgroup_list);
4214   initialized = 1;
4215   }
4216
4217print_cube(p_cube);
4218if (cube_is_solved(p_cube))
4219   {
4220   printf("cube is already solved!\n");
4221   return;
4222   }
4223
4224cube_conjugate(p_cube, &sym_cubes[0], &full_cube_struct.cubies);
4225process_full_cube(&full_cube_struct);
4226
4227set_cube_symmetry(&full_cube_struct, sym_cubes, subgroup_list);
4228
4229node_arr[0].follow_type = 1 + full_cube_struct.sym_subgrp;
4230node_arr[0].ud.corner_state = full_cube_struct.ud.corner_state;
4231node_arr[0].ud.edge_state = full_cube_struct.ud.edge_state;
4232node_arr[0].ud.sym_state = full_cube_struct.ud.sym_state;
4233
4234node_arr[0].rl.corner_state = full_cube_struct.rl.corner_state;
4235node_arr[0].rl.edge_state = full_cube_struct.rl.edge_state;
4236node_arr[0].rl.sym_state = full_cube_struct.rl.sym_state;
4237
4238node_arr[0].fb.corner_state = full_cube_struct.fb.corner_state;
4239node_arr[0].fb.edge_state = full_cube_struct.fb.edge_state;
4240node_arr[0].fb.sym_state = full_cube_struct.fb.sym_state;
4241
4242sol_found = 0;
4243if ((p_current_metric->metric == QUARTER_TURN_METRIC) &&
4244    (full_cube_struct.parity == 0))
4245   start_depth = 2;
4246else
4247   start_depth = 1;
4248
4249search_limit = p_current_options->search_limit;
4250if ((search_limit <= 0) || (search_limit >= MAX_TWISTS))
4251   search_limit = MAX_TWISTS - 1;
4252
4253for (ii = start_depth; ii <= search_limit; ii += p_current_metric->increment)
4254    {
4255    n_nodes = (long long int)0;
4256    n_tests = (unsigned int)0;
4257    node_arr[0].remain_depth = ii;
4258    node_arr[1].twist = -1;
4259    search_tree(&full_cube_struct, node_arr);
4260
4261    if ((p_current_options->one_solution_only == 0) || (sol_found == 0))
4262       {
4263       printf("depth %2d%c completed  (", ii, p_current_metric->metric_char);
4264       pretty_print_unsigned_int(n_nodes);
4265       printf(" nodes, ");
4266       pretty_print_unsigned_int(n_tests);
4267       printf(" tests)\n");
4268       fflush(stdout);
4269       }
4270
4271    if (sol_found)
4272       break;
4273    }
4274
4275return;
4276}
4277
4278
4279/* ========================================================================= */
4280   int  main(void)
4281/* ------------------------------------------------------------------------- */
4282
4283{
4284Metric_data             metric_data;
4285Options                 user_options;
4286Cube                    cube_struct;
4287int                     stat;
4288
4289
4290init_options(&metric_data, &user_options);
4291init_globals();
4292
4293signal(SIGINT, SIG_IGN);
4294
4295while (1)
4296      {
4297      stat = user_enters_cube(&cube_struct);
4298      if (stat < 0)
4299         break;
4300
4301      if (stat == 0)
4302         {
4303         if (sigsetjmp(jump_env, 1) == 0)
4304            {
4305            signal(SIGINT, user_interrupt);
4306            solve_cube(&cube_struct);
4307            }
4308
4309         signal(SIGINT, SIG_IGN);
4310         }
4311      }
4312
4313exit(EXIT_SUCCESS);
4314
4315return 0;  /*  haha  */
4316}
Note: See TracBrowser for help on using the repository browser.