research/2008-rubik/solver/optimal/optimal.c

/*  optimal cube solver  by  michael reid  reid@math.ucf.edu  */
/*  version 2.1  june 3, 2004  */
/*  symmetry mechanism added  */
/*  malloc.h removed, long string fixed  */


#define  USE_METRIC        QUARTER_TURN_METRIC
#define  SEARCH_LIMIT                        0
#define  USE_SYMMETRY                        1
#define  ONE_SOLUTION_ONLY                   0


#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>
#include  <setjmp.h>
#include  <signal.h>


#define  QUARTER_TURN_METRIC                 0
#define  FACE_TURN_METRIC                    1

#define  N_SYM                              16
#define  N_TWIST                            18
#define  N_CORNER                         2187
#define  N_ELOC                            495
#define  N_ELOC_CONV                      4096
#define  N_EFLIP                          2048
#define  N_FULLEDGE         (N_ELOC * N_EFLIP)
#define  N_EDGEQUOT                      64430
#define  N_CORNERPERM                    40320
#define  N_SLICEEDGE                     11880

#define  N_CUBESYM                          48
#define  N_SYMSUBGRP                        98
#define  SUBGRP_TRIVIAL                     97

#define  N_DIST_CHARS                  ((N_EDGEQUOT * N_CORNER) / 2)
#define  BACKWARDS_SWITCH_POINT    ((2 * N_EDGEQUOT * N_CORNER) / 5)

#define  CORNER_START                        0
#define  EDGE_START                      64244
#define  CORNERPERM_START                    0
#define  UD_SLICEEDGE_START                494
#define  RL_SLICEEDGE_START                 54
#define  FB_SLICEEDGE_START                209

#define  MAX_PERM_N                         12
#define  MAX_CHECK_PERM_N                   24

#define  MAX_TWISTS                         43

#define  TWIST_F                             0
#define  TWIST_F2                            1
#define  TWIST_F3                            2
#define  TWIST_R                             3
#define  TWIST_R2                            4
#define  TWIST_R3                            5
#define  TWIST_U                             6
#define  TWIST_U2                            7
#define  TWIST_U3                            8
#define  TWIST_B                             9
#define  TWIST_B2                           10
#define  TWIST_B3                           11
#define  TWIST_L                            12
#define  TWIST_L2                           13
#define  TWIST_L3                           14
#define  TWIST_D                            15
#define  TWIST_D2                           16
#define  TWIST_D3                           17

#define  CORNER_UFR                          0
#define  CORNER_URB                          1
#define  CORNER_UBL                          2
#define  CORNER_ULF                          3
#define  CORNER_DRF                          4
#define  CORNER_DFL                          5
#define  CORNER_DLB                          6
#define  CORNER_DBR                          7

#define  CORNER_FRU                          8
#define  CORNER_RBU                          9
#define  CORNER_BLU                         10
#define  CORNER_LFU                         11
#define  CORNER_RFD                         12
#define  CORNER_FLD                         13
#define  CORNER_LBD                         14
#define  CORNER_BRD                         15

#define  CORNER_RUF                         16
#define  CORNER_BUR                         17
#define  CORNER_LUB                         18
#define  CORNER_FUL                         19
#define  CORNER_FDR                         20
#define  CORNER_LDF                         21
#define  CORNER_BDL                         22
#define  CORNER_RDB                         23


#define  EDGE_UF                             0
#define  EDGE_UR                             1
#define  EDGE_UB                             2
#define  EDGE_UL                             3
#define  EDGE_DF                             4
#define  EDGE_DR                             5
#define  EDGE_DB                             6
#define  EDGE_DL                             7
#define  EDGE_FR                             8
#define  EDGE_FL                             9
#define  EDGE_BR                            10
#define  EDGE_BL                            11

#define  EDGE_FU                            12
#define  EDGE_RU                            13
#define  EDGE_BU                            14
#define  EDGE_LU                            15
#define  EDGE_FD                            16
#define  EDGE_RD                            17
#define  EDGE_BD                            18
#define  EDGE_LD                            19
#define  EDGE_RF                            20
#define  EDGE_LF                            21
#define  EDGE_RB                            22
#define  EDGE_LB                            23


#define  FACE_F                              0
#define  FACE_R                              1
#define  FACE_U                              2
#define  FACE_B                              3
#define  FACE_L                              4
#define  FACE_D                              5


#define  N_FOLLOW                          873

#define  FOLLOW_INVALID                      0

#define  N_SYLLABLE                         32

#define  SYLLABLE_INVALID                    0
#define  SYLLABLE_NONE                       1
#define  SYLLABLE_F                          2
#define  SYLLABLE_F2                         3
#define  SYLLABLE_F3                         4
#define  SYLLABLE_R                          5
#define  SYLLABLE_R2                         6
#define  SYLLABLE_R3                         7
#define  SYLLABLE_U                          8
#define  SYLLABLE_U2                         9
#define  SYLLABLE_U3                        10
#define  SYLLABLE_B                         11
#define  SYLLABLE_B2                        12
#define  SYLLABLE_B3                        13
#define  SYLLABLE_L                         14
#define  SYLLABLE_L2                        15
#define  SYLLABLE_L3                        16
#define  SYLLABLE_D                         17
#define  SYLLABLE_D2                        18
#define  SYLLABLE_D3                        19
#define  SYLLABLE_FB                        20
#define  SYLLABLE_FB2                       21
#define  SYLLABLE_FB3                       22
#define  SYLLABLE_F2B2                      23
#define  SYLLABLE_RL                        24
#define  SYLLABLE_RL2                       25
#define  SYLLABLE_RL3                       26
#define  SYLLABLE_R2L2                      27
#define  SYLLABLE_UD                        28
#define  SYLLABLE_UD2                       29
#define  SYLLABLE_UD3                       30
#define  SYLLABLE_U2D2                      31



#define  DIST(c, e)     (((e) & 0x1) ? (((int)distance[c][(e) >> 1]) >> 4)   \
                                     : (((int)distance[c][(e) >> 1]) & 0xF))


typedef struct cube
        {
        int             edges[24];
        int             corners[24];
        }
        Cube;


typedef struct coset_coord
        {
        int             corner_state;
        int             edge_state;
        int             sym_state;
        }
        Coset_coord;


typedef struct full_cube
        {
        Cube            cubies;
        int             cornerperm;
        int             ud_sliceedge;
        int             rl_sliceedge;
        int             fb_sliceedge;
        Coset_coord     ud;
        Coset_coord     rl;
        Coset_coord     fb;
        int             parity;
        int             sym_subgrp;
        }
        Full_cube;


typedef struct search_data
        {
        int             depth;
        int             found;
        int             found_quot;
        int            *multiplicities;
        int            *stabilizers;
        }
        Search_data;


typedef struct search_node
        {
        int             remain_depth;
        int             twist;
        int             follow_type;
        Coset_coord     ud;
        Coset_coord     rl;
        Coset_coord     fb;
        }
        Search_node;


typedef struct metric_data
        {
        int             metric;
        char            metric_char;
        int             twist_length[N_TWIST];
        int             increment;
        }
        Metric_data;


typedef struct options
        {
        int             use_symmetry;
        int             search_limit;
        int             one_solution_only;
        }
        Options;


typedef struct subgroup_list
        {
        int             n_subgroups;
        int           (*subgroups)[N_CUBESYM];
        }
        Subgroup_list;



static unsigned char   *sym_x_invsym_to_sym[N_SYM];

static unsigned char   *invsym_on_twist_ud[N_SYM];
static unsigned char   *invsym_on_twist_rl[N_SYM];
static unsigned char   *invsym_on_twist_fb[N_SYM];

static unsigned short  *twist_on_corner[N_TWIST];
static unsigned short  *sym_on_corner[N_SYM];

static unsigned short  *fulledge_to_edge;
static unsigned char   *fulledge_to_sym;

static unsigned short  *twist_on_edge[N_TWIST];
static unsigned char   *twist_x_edge_to_sym[N_TWIST];

static unsigned short  *twist_on_cornerperm[N_TWIST];
static unsigned short  *twist_on_sliceedge[N_TWIST];

static unsigned short  *twist_on_follow[N_TWIST];

static unsigned char   *distance[N_CORNER];

static char            *edge_cubie_str[] = {"UF", "UR", "UB", "UL",
                                            "DF", "DR", "DB", "DL",
                                            "FR", "FL", "BR", "BL",
                                            "FU", "RU", "BU", "LU",
                                            "FD", "RD", "BD", "LD",
                                            "RF", "LF", "RB", "LB"};

static char            *corner_cubie_str[] = {"UFR", "URB", "UBL", "ULF",
                                              "DRF", "DFL", "DLB", "DBR",
                                              "FRU", "RBU", "BLU", "LFU",
                                              "RFD", "FLD", "LBD", "BRD",
                                              "RUF", "BUR", "LUB", "FUL",
                                              "FDR", "LDF", "BDL", "RDB"};

static Metric_data     *p_current_metric;
static Options         *p_current_options;

static unsigned int     n_nodes;
static unsigned int     n_tests;
static int              sol_found;

static sigjmp_buf       jump_env;


/* ========================================================================= */
   void  exit_w_error_message(char  *msg)
/* ------------------------------------------------------------------------- */

{
printf("\n%s\n", msg);
exit(EXIT_FAILURE);

return;
}


/* ========================================================================= */
   void  user_interrupt(int  unused_arg)
/* ------------------------------------------------------------------------- */

{
printf("\n-- user interrupt --\n");
fflush(stdout);
siglongjmp(jump_env, 1);

return;
}


/* ========================================================================= */
   void  perm_n_unpack(int  nn, int  indx, int  array_out[])
/* ------------------------------------------------------------------------- */

{
int                     ii, jj;


for (ii = nn - 1; ii >= 0; ii--)
    {
    array_out[ii] = indx % (nn - ii);
    indx /= (nn - ii);

    for (jj = ii + 1; jj < nn; jj++)
        if (array_out[jj] >= array_out[ii])
           array_out[jj]++;
    }

return;
}


/* ========================================================================= */
   int  perm_n_pack(int  nn, int  array_in[])
/* ------------------------------------------------------------------------- */

{
int                     indx, ii, jj;


indx = 0;

for (ii = 0; ii < nn; ii++)
    {
    indx *= (nn - ii);

    for (jj = ii + 1; jj < nn; jj++)
        if (array_in[jj] < array_in[ii])
           indx++;
    }

return indx;
}


/* ========================================================================= */
   int  perm_n_check(int  nn, int  array_in[])
/* ------------------------------------------------------------------------- */

{
int                     count[MAX_CHECK_PERM_N], ii;


for (ii = 0; ii < nn; ii++)
    count[ii] = 0;

for (ii = 0; ii < nn; ii++)
    {
    if ((array_in[ii] < 0) || (array_in[ii] >= nn))
       return 1;

    count[array_in[ii]]++;
    }

for (ii = 0; ii < nn; ii++)
    if (count[ii] != 1)
       return 1;

return 0;
}


/* ========================================================================= */
   int  perm_n_parity(int  nn, int  array_in[])
/* ------------------------------------------------------------------------- */

{
int                     temp_array[MAX_CHECK_PERM_N];
int                     ii, jj, n_cycles;


for (ii = 0; ii < nn; ii++)
    temp_array[ii] = 0;

n_cycles = 0;

for (ii = 0; ii < nn; ii++)
    if (temp_array[ii] == 0)
       {
       n_cycles++;
       jj = ii;
       while (temp_array[jj] == 0)
             {
             temp_array[jj] = 1;
             jj = array_in[jj];
             }
       }

return (n_cycles + nn) % 2;
}


/* ========================================================================= */
   void  perm_n_init(int  nn, int  array_out[])
/* ------------------------------------------------------------------------- */

{
int                     ii;


for (ii = 0; ii < nn; ii++)
    array_out[ii] = ii;

return;
}


/* ========================================================================= */
   void  perm_n_compose(int  nn, int  perm0_in[], int  perm1_in[],
                                                  int  perm_out[])
/* ------------------------------------------------------------------------- */

{
int                     ii;


for (ii = 0; ii < nn; ii++)
    perm_out[ii] = perm0_in[perm1_in[ii]];

return;
}


/* ========================================================================= */
   void  perm_n_conjugate(int  nn, int  arr_in[], int  conjugator[],
                                                  int  array_out[])
/* ------------------------------------------------------------------------- */

{
int                     ii;


for (ii = 0; ii < nn; ii++)
    array_out[conjugator[ii]] = conjugator[arr_in[ii]];

return;
}


/* ========================================================================= */
   void  two_cycle(int  array[], int  ind0, int  ind1)
/* ------------------------------------------------------------------------- */

{
int                     temp;


temp = array[ind0];
array[ind0] = array[ind1];
array[ind1] = temp;

return;
}


/* ========================================================================= */
   void  three_cycle(int  array[], int  ind0, int  ind1, int  ind2)
/* ------------------------------------------------------------------------- */

{
int                     temp;


temp = array[ind0];
array[ind0] = array[ind1];
array[ind1] = array[ind2];
array[ind2] = temp;

return;
}


/* ========================================================================= */
   void  four_cycle(int  array[], int  ind0, int  ind1, int  ind2, int  ind3)
/* ------------------------------------------------------------------------- */

{
int                     temp;


temp = array[ind0];
array[ind0] = array[ind1];
array[ind1] = array[ind2];
array[ind2] = array[ind3];
array[ind3] = temp;

return;
}


/* ========================================================================= */
   void  print_cube(Cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
printf("%s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s %s\n",
       edge_cubie_str[p_cube->edges[0]], edge_cubie_str[p_cube->edges[1]],
       edge_cubie_str[p_cube->edges[2]], edge_cubie_str[p_cube->edges[3]],
       edge_cubie_str[p_cube->edges[4]], edge_cubie_str[p_cube->edges[5]],
       edge_cubie_str[p_cube->edges[6]], edge_cubie_str[p_cube->edges[7]],
       edge_cubie_str[p_cube->edges[8]], edge_cubie_str[p_cube->edges[9]],
       edge_cubie_str[p_cube->edges[10]], edge_cubie_str[p_cube->edges[11]],
   corner_cubie_str[p_cube->corners[0]], corner_cubie_str[p_cube->corners[1]],
   corner_cubie_str[p_cube->corners[2]], corner_cubie_str[p_cube->corners[3]],
   corner_cubie_str[p_cube->corners[4]], corner_cubie_str[p_cube->corners[5]],
   corner_cubie_str[p_cube->corners[6]], corner_cubie_str[p_cube->corners[7]]);

return;
}


/* ========================================================================= */
   void  cube_init(Cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
perm_n_init(24, p_cube->edges);
perm_n_init(24, p_cube->corners);

return;
}


/* ========================================================================= */
   int  cube_compare(Cube  *cube0, Cube  *cube1)
/* ------------------------------------------------------------------------- */

{
int           ii;

for (ii = 0; ii < 24; ii++)
    {
    if (cube0->edges[ii] < cube1->edges[ii])
       return -1;
    else if (cube0->edges[ii] > cube1->edges[ii])
       return 1;
    }

for (ii = 0; ii < 24; ii++)
    {
    if (cube0->corners[ii] < cube1->corners[ii])
       return -1;
    else if (cube0->corners[ii] > cube1->corners[ii])
       return 1;
    }

return 0;
}


/* ========================================================================= */
   void  cube_compose(Cube  *in_cube0, Cube  *in_cube1, Cube  *out_cube)
/* ------------------------------------------------------------------------- */

{
perm_n_compose(24, in_cube0->edges, in_cube1->edges, out_cube->edges);
perm_n_compose(24, in_cube0->corners, in_cube1->corners, out_cube->corners);

return;
}


/* ========================================================================= */
   void  cube_conjugate(Cube  *p_cube_in, Cube  *p_conjugator,
                                          Cube  *p_cube_out)
/* ------------------------------------------------------------------------- */

{
perm_n_conjugate(24, p_cube_in->edges, p_conjugator->edges, p_cube_out->edges);
perm_n_conjugate(24, p_cube_in->corners, p_conjugator->corners,
                                                          p_cube_out->corners);

return;
}


/* ========================================================================= */
   int  cube_is_solved(Cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
Cube                    temp_cube;


cube_init(&temp_cube);

return (cube_compare(p_cube, &temp_cube) == 0);
}


/* ========================================================================= */
   int  metric_q_length(int  twist)
/* ------------------------------------------------------------------------- */

{
if ((twist == TWIST_F) || (twist == TWIST_F3) ||
    (twist == TWIST_R) || (twist == TWIST_R3) ||
    (twist == TWIST_U) || (twist == TWIST_U3) ||
    (twist == TWIST_B) || (twist == TWIST_B3) ||
    (twist == TWIST_L) || (twist == TWIST_L3) ||
    (twist == TWIST_D) || (twist == TWIST_D3))
   return 1;
else if ((twist == TWIST_F2) || (twist == TWIST_R2) || (twist == TWIST_U2) ||
         (twist == TWIST_B2) || (twist == TWIST_L2) || (twist == TWIST_D2))
        return 2;
else
   exit_w_error_message("metric_q_length : invalid twist");

return 0;
}


/* ========================================================================= */
   int  metric_f_length(int  twist)
/* ------------------------------------------------------------------------- */

{
if ((twist == TWIST_F) || (twist == TWIST_F2) || (twist == TWIST_F3) ||
    (twist == TWIST_R) || (twist == TWIST_R2) || (twist == TWIST_R3) ||
    (twist == TWIST_U) || (twist == TWIST_U2) || (twist == TWIST_U3) ||
    (twist == TWIST_B) || (twist == TWIST_B2) || (twist == TWIST_B3) ||
    (twist == TWIST_L) || (twist == TWIST_L2) || (twist == TWIST_L3) ||
    (twist == TWIST_D) || (twist == TWIST_D2) || (twist == TWIST_D3))
   return 1;
else
   exit_w_error_message("metric_f_length : invalid twist");

return 0;
}


/* ========================================================================= */
   void  calc_metric_q_length(int  lengths[N_TWIST])
/* ------------------------------------------------------------------------- */

{
int                     twist;


for (twist = 0; twist < N_TWIST; twist++)
    lengths[twist] = metric_q_length(twist);

return;
}


/* ========================================================================= */
   void  calc_metric_f_length(int  lengths[N_TWIST])
/* ------------------------------------------------------------------------- */

{
int                     twist;


for (twist = 0; twist < N_TWIST; twist++)
    lengths[twist] = metric_f_length(twist);

return;
}


/* ========================================================================= */
   void  init_metric(Metric_data  *p_metric_data, int  use_metric)
/* ------------------------------------------------------------------------- */

{
if ((use_metric != QUARTER_TURN_METRIC) && (use_metric != FACE_TURN_METRIC))
   exit_w_error_message("init_metric : unknown metric");

p_metric_data->metric = use_metric;

if (p_metric_data->metric == QUARTER_TURN_METRIC)
   {
   printf("using quarter turn metric\n");
   p_metric_data->metric_char = 'q';
   calc_metric_q_length(p_metric_data->twist_length);
   p_metric_data->increment = 2;
   }
else
   {
   printf("using face turn metric\n");
   p_metric_data->metric_char = 'f';
   calc_metric_f_length(p_metric_data->twist_length);
   p_metric_data->increment = 1;
   }

p_current_metric = p_metric_data;

return;
}


/* ========================================================================= */
   void  init_options(Metric_data  *p_metric_data, Options  *p_user_options)
/* ------------------------------------------------------------------------- */

{
init_metric(p_metric_data, USE_METRIC);

p_user_options->search_limit = SEARCH_LIMIT;
if (p_user_options->search_limit <= 0)
   printf("no search limit\n");
else
   printf("search limit: %d%c\n", p_user_options->search_limit,
                                                p_current_metric->metric_char);

p_user_options->use_symmetry = USE_SYMMETRY;
if (p_user_options->use_symmetry)
   printf("using symmetry reductions\n");
else
   printf("not using symmetry reductions\n");

p_user_options->one_solution_only = ONE_SOLUTION_ONLY;
if (p_user_options->one_solution_only)
   printf("only finding one solution\n");
else
   printf("finding all solutions\n");

printf("\n");
p_current_options = p_user_options;

return;
}


/* ========================================================================= */
   void  calc_group_table(int  group_table[N_CUBESYM][N_CUBESYM])
/* ------------------------------------------------------------------------- */

{
int                     sym_array[N_CUBESYM][6];
int                     sym_pack[N_CUBESYM];
int                     temp_array[6];
int                     ii, jj, kk, pack;


perm_n_init(6, sym_array[0]);
perm_n_init(6, sym_array[1]);

four_cycle(sym_array[1], FACE_F, FACE_L, FACE_B, FACE_R);

for (ii = 2; ii < 4; ii++)
    perm_n_compose(6, sym_array[1], sym_array[ii - 1], sym_array[ii]);

perm_n_init(6, sym_array[4]);

two_cycle(sym_array[4], FACE_U, FACE_D);
two_cycle(sym_array[4], FACE_R, FACE_L);

for (ii = 5; ii < 8; ii++)
    perm_n_compose(6, sym_array[4], sym_array[ii - 4], sym_array[ii]);

perm_n_init(6, sym_array[8]);

two_cycle(sym_array[8], FACE_U, FACE_D);

for (ii = 9; ii < 16; ii++)
    perm_n_compose(6, sym_array[8], sym_array[ii - 8], sym_array[ii]);

perm_n_init(6, sym_array[16]);

three_cycle(sym_array[16], FACE_U, FACE_F, FACE_R);
three_cycle(sym_array[16], FACE_D, FACE_B, FACE_L);

for (ii = 17; ii < 48; ii++)
    perm_n_compose(6, sym_array[16], sym_array[ii - 16], sym_array[ii]);

for (ii = 0; ii < N_CUBESYM; ii++)
    sym_pack[ii] = perm_n_pack(6, sym_array[ii]);

for (ii = 0; ii < N_CUBESYM; ii++)
    for (jj = 0; jj < N_CUBESYM; jj++)
        {
        perm_n_compose(6, sym_array[ii], sym_array[jj], temp_array);
        pack = perm_n_pack(6, temp_array);

        for (kk = 0; kk < N_CUBESYM; kk++)
            if (sym_pack[kk] == pack)
               {
               group_table[ii][jj] = kk;
               break;
               }

        if (kk == N_CUBESYM)
           exit_w_error_message("calc_group_table : product not found");
        }

return;
}


/* ========================================================================= */
   void  init_sym_x_invsym_to_sym(void)
/* ------------------------------------------------------------------------- */

{
unsigned char         (*mem_ptr)[N_SYM];
int                     group_table[N_CUBESYM][N_CUBESYM];
int                     group_inverse[N_CUBESYM];
int                     ii, jj;


/*  initialize global array   sym_x_invsym_to_sym   */

mem_ptr =
        (unsigned char (*)[N_SYM])malloc(sizeof(unsigned char [N_SYM][N_SYM]));
if (mem_ptr == NULL)
   exit_w_error_message("init_sym_x_invsym_to_sym : couldn't get memory");

for (ii = 0; ii < N_SYM; ii++)
    sym_x_invsym_to_sym[ii] = mem_ptr[ii];

calc_group_table(group_table);

for (ii = 0; ii < N_SYM; ii++)
    {
    for (jj = 0; jj < N_SYM; jj++)
        if (group_table[ii][jj] == 0)
           {
           group_inverse[ii] = jj;
           break;
           }

    if (jj == N_SYM)
       exit_w_error_message("init_sym_x_invsym_to_sym : inverse not found");
    }

for (ii = 0; ii < N_SYM; ii++)
    for (jj = 0; jj < N_SYM; jj++)
        sym_x_invsym_to_sym[ii][jj] =
                             (unsigned char)group_table[ii][group_inverse[jj]];

return;
}


/* ========================================================================= */
   void  calc_sym_on_twist(int  sym_on_twist[N_CUBESYM][N_TWIST])
/* ------------------------------------------------------------------------- */

{
int                     sym;


perm_n_init(N_TWIST, sym_on_twist[0]);
perm_n_init(N_TWIST, sym_on_twist[1]);

four_cycle(sym_on_twist[1], TWIST_F , TWIST_L , TWIST_B , TWIST_R );
four_cycle(sym_on_twist[1], TWIST_F2, TWIST_L2, TWIST_B2, TWIST_R2);
four_cycle(sym_on_twist[1], TWIST_F3, TWIST_L3, TWIST_B3, TWIST_R3);

for (sym = 2; sym < 4; sym++)
    perm_n_compose(N_TWIST, sym_on_twist[1], sym_on_twist[sym - 1],
                                                            sym_on_twist[sym]);

perm_n_init(N_TWIST, sym_on_twist[4]);

two_cycle(sym_on_twist[4], TWIST_R , TWIST_L );
two_cycle(sym_on_twist[4], TWIST_R2, TWIST_L2);
two_cycle(sym_on_twist[4], TWIST_R3, TWIST_L3);
two_cycle(sym_on_twist[4], TWIST_U , TWIST_D );
two_cycle(sym_on_twist[4], TWIST_U2, TWIST_D2);
two_cycle(sym_on_twist[4], TWIST_U3, TWIST_D3);

for (sym = 5; sym < 8; sym++)
    perm_n_compose(N_TWIST, sym_on_twist[4], sym_on_twist[sym - 4],
                                                            sym_on_twist[sym]);

perm_n_init(N_TWIST, sym_on_twist[8]);

two_cycle(sym_on_twist[8], TWIST_F, TWIST_F3);
two_cycle(sym_on_twist[8], TWIST_R, TWIST_R3);
two_cycle(sym_on_twist[8], TWIST_B, TWIST_B3);
two_cycle(sym_on_twist[8], TWIST_L, TWIST_L3);
two_cycle(sym_on_twist[8], TWIST_U , TWIST_D3);
two_cycle(sym_on_twist[8], TWIST_U2, TWIST_D2);
two_cycle(sym_on_twist[8], TWIST_U3, TWIST_D );

for (sym = 9; sym < 16; sym++)
    perm_n_compose(N_TWIST, sym_on_twist[8], sym_on_twist[sym - 8],
                                                            sym_on_twist[sym]);

perm_n_init(N_TWIST, sym_on_twist[16]);

three_cycle(sym_on_twist[16], TWIST_F , TWIST_R , TWIST_U );
three_cycle(sym_on_twist[16], TWIST_F2, TWIST_R2, TWIST_U2);
three_cycle(sym_on_twist[16], TWIST_F3, TWIST_R3, TWIST_U3);
three_cycle(sym_on_twist[16], TWIST_B , TWIST_L , TWIST_D );
three_cycle(sym_on_twist[16], TWIST_B2, TWIST_L2, TWIST_D2);
three_cycle(sym_on_twist[16], TWIST_B3, TWIST_L3, TWIST_D3);

for (sym = 17; sym < 48; sym++)
    perm_n_compose(N_TWIST, sym_on_twist[16], sym_on_twist[sym - 16],
                                                            sym_on_twist[sym]);

return;
}


/* ========================================================================= */
   void  init_invsym_on_twist(void)
/* ------------------------------------------------------------------------- */

{
unsigned char         (*mem_ptr)[N_SYM][N_TWIST];
int                     sym_on_twist[N_CUBESYM][N_TWIST];
int                     ud_to_rl[N_TWIST], sym, twist;


/*   allocate and initialize global arrays                                 */
/*   invsym_on_twist_ud ,  invsym_on_twist_fb   and   invsym_on_twist_rl   */

mem_ptr = (unsigned char (*)[N_SYM][N_TWIST])
                             malloc(sizeof(unsigned char [3][N_SYM][N_TWIST]));
if (mem_ptr == NULL)
   exit_w_error_message("init_invsym_on_twist : couldn't get memory");

for (sym = 0; sym < N_SYM; sym++)
    {
    invsym_on_twist_ud[sym] = mem_ptr[0][sym];
    invsym_on_twist_rl[sym] = mem_ptr[1][sym];
    invsym_on_twist_fb[sym] = mem_ptr[2][sym];
    }

calc_sym_on_twist(sym_on_twist);

for (sym = 0; sym < N_SYM; sym++)
    for (twist = 0; twist < N_TWIST; twist++)
        invsym_on_twist_ud[sym][twist] =
          (unsigned char)sym_on_twist[(int)sym_x_invsym_to_sym[0][sym]][twist];

perm_n_init(N_TWIST, ud_to_rl);

three_cycle(ud_to_rl, TWIST_F , TWIST_R , TWIST_U );
three_cycle(ud_to_rl, TWIST_F2, TWIST_R2, TWIST_U2);
three_cycle(ud_to_rl, TWIST_F3, TWIST_R3, TWIST_U3);
three_cycle(ud_to_rl, TWIST_B , TWIST_L , TWIST_D );
three_cycle(ud_to_rl, TWIST_B2, TWIST_L2, TWIST_D2);
three_cycle(ud_to_rl, TWIST_B3, TWIST_L3, TWIST_D3);

for (sym = 0; sym < N_SYM; sym++)
    for (twist = 0; twist < N_TWIST; twist++)
        invsym_on_twist_rl[sym][twist] =
                                      invsym_on_twist_ud[sym][ud_to_rl[twist]];

for (sym = 0; sym < N_SYM; sym++)
    for (twist = 0; twist < N_TWIST; twist++)
        invsym_on_twist_fb[sym][twist] =
                                      invsym_on_twist_rl[sym][ud_to_rl[twist]];

return;
}


/* ========================================================================= */
   void  generate_subgroup(int  group_table[N_CUBESYM][N_CUBESYM],
                           int   gen_set[N_CUBESYM])
/* ------------------------------------------------------------------------- */

/*  gen_set[]  is both input and output  */

{
int                 found, ii, jj;


gen_set[0] = 1;
found = 1;

while (found)
      {
      found = 0;

      for (ii = 0; ii < N_CUBESYM; ii++)
          if (gen_set[ii] != 0)
             for (jj = 0; jj < N_CUBESYM; jj++)
                 if ((gen_set[jj] != 0) && (gen_set[group_table[ii][jj]] == 0))
                    {
                    gen_set[group_table[ii][jj]] = 1;
                    found = 1;
                    }
      }

return;
}


/* ========================================================================= */
   void  calc_subgroups_recursive(int  group_table[N_CUBESYM][N_CUBESYM],
                                  int  contain_list[N_CUBESYM],
                                  int  avoid_list[N_CUBESYM],
                                  Subgroup_list  *p_output)
/* ------------------------------------------------------------------------- */

{
int                 local_contain_list[N_CUBESYM], ii, jj;


for (ii = 0; ii < N_CUBESYM; ii++)
    if (contain_list[ii] && avoid_list[ii])
       return;

for (ii = 0; ii < N_CUBESYM; ii++)
    if ((contain_list[ii] == 0) && (avoid_list[ii] == 0))
       break;

if (ii < N_CUBESYM)
   {
   for (jj = 0; jj < N_CUBESYM; jj++)
       local_contain_list[jj] = contain_list[jj];
   local_contain_list[ii] = 1;
   generate_subgroup(group_table, local_contain_list);
   calc_subgroups_recursive(group_table, local_contain_list, avoid_list,
                                                                     p_output);
   avoid_list[ii] = 1;
   calc_subgroups_recursive(group_table, contain_list, avoid_list, p_output);
   avoid_list[ii] = 0;
   }
else
   {
   if (p_output->n_subgroups >= N_SYMSUBGRP)
      exit_w_error_message("calc_subgroups_recursive : too many subgroups");

   for (ii = 0; ii < N_CUBESYM; ii++)
       p_output->subgroups[p_output->n_subgroups][ii] = contain_list[ii];

   p_output->n_subgroups++;
   }

return;
}


/* ========================================================================= */
   void  calc_subgroup_list(int  subgroup_list[N_SYMSUBGRP][N_CUBESYM])
/* ------------------------------------------------------------------------- */

{
Subgroup_list   output_list;
int             group_table[N_CUBESYM][N_CUBESYM];
int             contain_list[N_CUBESYM];
int             avoid_list[N_CUBESYM];
int             ii;


calc_group_table(group_table);

output_list.n_subgroups = 0;
output_list.subgroups = subgroup_list;

contain_list[0] = 1;

for (ii = 1; ii < N_CUBESYM; ii++)
    contain_list[ii] = 0;

for (ii = 0; ii < N_CUBESYM; ii++)
    avoid_list[ii] = 0;

calc_subgroups_recursive(group_table, contain_list, avoid_list, &output_list);

if (output_list.n_subgroups != N_SYMSUBGRP)
   exit_w_error_message("calc_subgroup_list : wrong number of subgroups");

return;
}


/* ========================================================================= */
   int  is_single_twist(int  syllable)
/* ------------------------------------------------------------------------- */

{
if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
                                (syllable == SYLLABLE_F3) ||
    (syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
                                (syllable == SYLLABLE_R3) ||
    (syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
                                (syllable == SYLLABLE_U3) ||
    (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                (syllable == SYLLABLE_B3) ||
    (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                (syllable == SYLLABLE_L3) ||
    (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                (syllable == SYLLABLE_D3))
   return 1;

return 0;
}


/* ========================================================================= */
   int  syllable_to_twist(int  syllable)
/* ------------------------------------------------------------------------- */

{
if (syllable == SYLLABLE_F)
   return TWIST_F;
else if (syllable == SYLLABLE_F2)
        return TWIST_F2;
else if (syllable == SYLLABLE_F3)
        return TWIST_F3;
else if (syllable == SYLLABLE_R)
        return TWIST_R;
else if (syllable == SYLLABLE_R2)
        return TWIST_R2;
else if (syllable == SYLLABLE_R3)
        return TWIST_R3;
else if (syllable == SYLLABLE_U)
        return TWIST_U;
else if (syllable == SYLLABLE_U2)
        return TWIST_U2;
else if (syllable == SYLLABLE_U3)
        return TWIST_U3;
else if (syllable == SYLLABLE_B)
        return TWIST_B;
else if (syllable == SYLLABLE_B2)
        return TWIST_B2;
else if (syllable == SYLLABLE_B3)
        return TWIST_B3;
else if (syllable == SYLLABLE_L)
        return TWIST_L;
else if (syllable == SYLLABLE_L2)
        return TWIST_L2;
else if (syllable == SYLLABLE_L3)
        return TWIST_L3;
else if (syllable == SYLLABLE_D)
        return TWIST_D;
else if (syllable == SYLLABLE_D2)
        return TWIST_D2;
else if (syllable == SYLLABLE_D3)
        return TWIST_D3;
else
   exit_w_error_message("syllable_to_twist : invalid input");

return -1;
}


/* ========================================================================= */
   void  syllable_to_two_twists(int  syllable, int  twists_out[2])
/* ------------------------------------------------------------------------- */

{
if (syllable == SYLLABLE_FB)
   {
   twists_out[0] = TWIST_F;
   twists_out[1] = TWIST_B;
   }
else if (syllable == SYLLABLE_FB2)
        {
        twists_out[0] = TWIST_F;
        twists_out[1] = TWIST_B2;
        }
else if (syllable == SYLLABLE_FB3)
        {
        twists_out[0] = TWIST_F;
        twists_out[1] = TWIST_B3;
        }
else if (syllable == SYLLABLE_F2B2)
        {
        twists_out[0] = TWIST_F2;
        twists_out[1] = TWIST_B2;
        }
else if (syllable == SYLLABLE_RL)
        {
        twists_out[0] = TWIST_R;
        twists_out[1] = TWIST_L;
        }
else if (syllable == SYLLABLE_RL2)
        {
        twists_out[0] = TWIST_R;
        twists_out[1] = TWIST_L2;
        }
else if (syllable == SYLLABLE_RL3)
        {
        twists_out[0] = TWIST_R;
        twists_out[1] = TWIST_L3;
        }
else if (syllable == SYLLABLE_R2L2)
        {
        twists_out[0] = TWIST_R2;
        twists_out[1] = TWIST_L2;
        }
else if (syllable == SYLLABLE_UD)
        {
        twists_out[0] = TWIST_U;
        twists_out[1] = TWIST_D;
        }
else if (syllable == SYLLABLE_UD2)
        {
        twists_out[0] = TWIST_U;
        twists_out[1] = TWIST_D2;
        }
else if (syllable == SYLLABLE_UD3)
        {
        twists_out[0] = TWIST_U;
        twists_out[1] = TWIST_D3;
        }
else if (syllable == SYLLABLE_U2D2)
        {
        twists_out[0] = TWIST_U2;
        twists_out[1] = TWIST_D2;
        }
else
   exit_w_error_message("syllable_to_two_twists : invalid input");

return;
}


/* ========================================================================= */
   int  twists_in_wrong_order(int  twists[2])
/* ------------------------------------------------------------------------- */

{
if (((twists[0] == TWIST_B) || (twists[0] == TWIST_B2) ||
                                   (twists[0] == TWIST_B3)) &&
    ((twists[1] == TWIST_F) || (twists[1] == TWIST_F2) ||
                                   (twists[1] == TWIST_F3)))
   return 1;

if (((twists[0] == TWIST_L) || (twists[0] == TWIST_L2) ||
                                   (twists[0] == TWIST_L3)) &&
    ((twists[1] == TWIST_R) || (twists[1] == TWIST_R2) ||
                                   (twists[1] == TWIST_R3)))
   return 1;

if (((twists[0] == TWIST_D) || (twists[0] == TWIST_D2) ||
                                   (twists[0] == TWIST_D3)) &&
    ((twists[1] == TWIST_U) || (twists[1] == TWIST_U2) ||
                                   (twists[1] == TWIST_U3)))
   return 1;

return 0;
}


/* ========================================================================= */
   void  clean_up_sequence(int  twist_sequence[], int  n_twists)
/* ------------------------------------------------------------------------- */

{
int             ii;


for (ii = 1; ii < n_twists; ii++)
    if (twists_in_wrong_order(&twist_sequence[ii - 1]) != 0)
       two_cycle(twist_sequence, ii - 1, ii);

return;
}


/* ========================================================================= */
   int  which_subgroup(int  subgroup[N_CUBESYM],
                       int  subgroup_list[N_SYMSUBGRP][N_CUBESYM])
/* ------------------------------------------------------------------------- */

{
int             subgrp, sym;


for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
    {
    for (sym = 0; sym < N_CUBESYM; sym++)
        if ((subgroup[sym] == 0) != (subgroup_list[subgrp][sym] == 0))
           break;

    if (sym == N_CUBESYM)
       return subgrp;
    }

return -1;
}


/* ========================================================================= */
   void  calc_syllable_on_sym(int  subgroup_list[N_SYMSUBGRP][N_CUBESYM],
                              int  sym_on_twist[N_CUBESYM][N_TWIST],
                              int  syllable_on_sym[N_SYLLABLE][N_SYMSUBGRP])
/* ------------------------------------------------------------------------- */

{
int             subgroup[N_CUBESYM], temp_subgroup[N_CUBESYM];
int             twist_arr[2], temp_arr[2];
int             syllable, sym, subgrp, twist;


for (syllable = 0; syllable < N_SYLLABLE; syllable++)
    {
    if ((syllable == SYLLABLE_INVALID) || (syllable == SYLLABLE_NONE))
       {
       subgroup[0] = 1;
       for (sym = 1; sym < N_CUBESYM; sym++)
           subgroup[sym] = 0;
       }
    else if (is_single_twist(syllable))
            {
            twist = syllable_to_twist(syllable);
            for (sym = 0; sym < N_CUBESYM; sym++)
                subgroup[sym] = (sym_on_twist[sym][twist] == twist);
            }
    else
       {
       syllable_to_two_twists(syllable, twist_arr);

       for (sym = 0; sym < N_CUBESYM; sym++)
           {
           temp_arr[0] = sym_on_twist[sym][twist_arr[0]];
           temp_arr[1] = sym_on_twist[sym][twist_arr[1]];
           clean_up_sequence(temp_arr, 2);
           if ((temp_arr[0] == twist_arr[0]) &&
               (temp_arr[1] == twist_arr[1]))
              subgroup[sym] = 1;
           else
              subgroup[sym] = 0;
           }
       }

    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
        {
        for (sym = 0; sym < N_CUBESYM; sym++)
            temp_subgroup[sym] = (subgroup[sym] && subgroup_list[subgrp][sym]);

        syllable_on_sym[syllable][subgrp] = which_subgroup(temp_subgroup,
                                                                subgroup_list);
        if (syllable_on_sym[syllable][subgrp] < 0)
           exit_w_error_message("calc_syllable_on_sym : subgroup not found");
        }
    }

return;
}


/* ========================================================================= */
   int  twist_on_syllable(int  twist, int  syllable)
/* ------------------------------------------------------------------------- */

{
if (syllable == SYLLABLE_INVALID)
   return SYLLABLE_INVALID;

if (twist == TWIST_F)
   {
   if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
                                   (syllable == SYLLABLE_F3) ||
       (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                   (syllable == SYLLABLE_B3) ||
       (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
       (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
      return SYLLABLE_INVALID;
   else
      return SYLLABLE_F;
   }
else if (twist == TWIST_F2)
        {
        if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
                                        (syllable == SYLLABLE_F3) ||
            (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                        (syllable == SYLLABLE_B3) ||
            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_F2;
        }
else if (twist == TWIST_F3)
        {
        if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F2) ||
                                        (syllable == SYLLABLE_F3) ||
            (syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                        (syllable == SYLLABLE_B3) ||
            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_F3;
        }
else if (twist == TWIST_R)
        {
        if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
                                        (syllable == SYLLABLE_R3) ||
            (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                        (syllable == SYLLABLE_L3) ||
            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_R;
        }
else if (twist == TWIST_R2)
        {
        if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
                                        (syllable == SYLLABLE_R3) ||
            (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                        (syllable == SYLLABLE_L3) ||
            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_R2;
        }
else if (twist == TWIST_R3)
        {
        if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R2) ||
                                        (syllable == SYLLABLE_R3) ||
            (syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                        (syllable == SYLLABLE_L3) ||
            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_R3;
        }
else if (twist == TWIST_U)
        {
        if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
                                        (syllable == SYLLABLE_U3) ||
            (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                        (syllable == SYLLABLE_D3) ||
            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_U;
        }
else if (twist == TWIST_U2)
        {
        if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
                                        (syllable == SYLLABLE_U3) ||
            (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                        (syllable == SYLLABLE_D3) ||
            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_U2;
        }
else if (twist == TWIST_U3)
        {
        if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U2) ||
                                        (syllable == SYLLABLE_U3) ||
            (syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                        (syllable == SYLLABLE_D3) ||
            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
           return SYLLABLE_INVALID;
        else
           return SYLLABLE_U3;
        }
else if (twist == TWIST_B)
        {
        if ((syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                        (syllable == SYLLABLE_B3) ||
            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
           return SYLLABLE_INVALID;
        else if (syllable == SYLLABLE_F)
                return SYLLABLE_FB;
        else if (syllable == SYLLABLE_F2)
                return SYLLABLE_FB2;
        else if (syllable == SYLLABLE_F3)
                return SYLLABLE_FB3;
        else
           return SYLLABLE_B;
        }
else if (twist == TWIST_B2)
        {
        if ((syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                        (syllable == SYLLABLE_B3) ||
            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
           return SYLLABLE_INVALID;
        else if ((syllable == SYLLABLE_F) || (syllable == SYLLABLE_F3))
                return SYLLABLE_FB2;
        else if (syllable == SYLLABLE_F2)
                return SYLLABLE_F2B2;
        else
           return SYLLABLE_B2;
        }
else if (twist == TWIST_B3)
        {
        if ((syllable == SYLLABLE_B) || (syllable == SYLLABLE_B2) ||
                                        (syllable == SYLLABLE_B3) ||
            (syllable == SYLLABLE_FB) || (syllable == SYLLABLE_FB2) ||
            (syllable == SYLLABLE_FB3) || (syllable == SYLLABLE_F2B2))
           return SYLLABLE_INVALID;
        else if (syllable == SYLLABLE_F)
                return SYLLABLE_FB3;
        else if (syllable == SYLLABLE_F2)
                return SYLLABLE_FB2;
        else if (syllable == SYLLABLE_F3)
                return SYLLABLE_FB;
        else
           return SYLLABLE_B3;
        }
else if (twist == TWIST_L)
        {
        if ((syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                        (syllable == SYLLABLE_L3) ||
            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
           return SYLLABLE_INVALID;
        else if (syllable == SYLLABLE_R)
                return SYLLABLE_RL;
        else if (syllable == SYLLABLE_R2)
                return SYLLABLE_RL2;
        else if (syllable == SYLLABLE_R3)
                return SYLLABLE_RL3;
        else
           return SYLLABLE_L;
        }
else if (twist == TWIST_L2)
        {
        if ((syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                        (syllable == SYLLABLE_L3) ||
            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
           return SYLLABLE_INVALID;
        else if ((syllable == SYLLABLE_R) || (syllable == SYLLABLE_R3))
                return SYLLABLE_RL2;
        else if (syllable == SYLLABLE_R2)
                return SYLLABLE_R2L2;
        else
           return SYLLABLE_L2;
        }
else if (twist == TWIST_L3)
        {
        if ((syllable == SYLLABLE_L) || (syllable == SYLLABLE_L2) ||
                                        (syllable == SYLLABLE_L3) ||
            (syllable == SYLLABLE_RL) || (syllable == SYLLABLE_RL2) ||
            (syllable == SYLLABLE_RL3) || (syllable == SYLLABLE_R2L2))
           return SYLLABLE_INVALID;
        else if (syllable == SYLLABLE_R)
                return SYLLABLE_RL3;
        else if (syllable == SYLLABLE_R2)
                return SYLLABLE_RL2;
        else if (syllable == SYLLABLE_R3)
                return SYLLABLE_RL;
        else
           return SYLLABLE_L3;
        }
else if (twist == TWIST_D)
        {
        if ((syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                        (syllable == SYLLABLE_D3) ||
            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
           return SYLLABLE_INVALID;
        else if (syllable == SYLLABLE_U)
                return SYLLABLE_UD;
        else if (syllable == SYLLABLE_U2)
                return SYLLABLE_UD2;
        else if (syllable == SYLLABLE_U3)
                return SYLLABLE_UD3;
        else
           return SYLLABLE_D;
        }
else if (twist == TWIST_D2)
        {
        if ((syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                        (syllable == SYLLABLE_D3) ||
            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
           return SYLLABLE_INVALID;
        else if ((syllable == SYLLABLE_U) || (syllable == SYLLABLE_U3))
                return SYLLABLE_UD2;
        else if (syllable == SYLLABLE_U2)
                return SYLLABLE_U2D2;
        else
           return SYLLABLE_D2;
        }
else if (twist == TWIST_D3)
        {
        if ((syllable == SYLLABLE_D) || (syllable == SYLLABLE_D2) ||
                                        (syllable == SYLLABLE_D3) ||
            (syllable == SYLLABLE_UD) || (syllable == SYLLABLE_UD2) ||
            (syllable == SYLLABLE_UD3) || (syllable == SYLLABLE_U2D2))
           return SYLLABLE_INVALID;
        else if (syllable == SYLLABLE_U)
                return SYLLABLE_UD3;
        else if (syllable == SYLLABLE_U2)
                return SYLLABLE_UD2;
        else if (syllable == SYLLABLE_U3)
                return SYLLABLE_UD;
        else
           return SYLLABLE_D3;
        }
else
   exit_w_error_message("twist_on_syllable : invalid twist");

return SYLLABLE_INVALID;
}


/* ========================================================================= */
   int  not_minimal_one_twist(int  subgroup[N_CUBESYM],
                              int  sym_on_twist[N_CUBESYM][N_TWIST],
                              int  twist)
/* ------------------------------------------------------------------------- */

{
int                     sym;


for (sym = 0; sym < N_CUBESYM; sym++)
    if (subgroup[sym] && (sym_on_twist[sym][twist] < twist))
       return 1;

return 0;
}


/* ========================================================================= */
   int  not_minimal_two_twists(int  subgroup[N_CUBESYM],
                               int  sym_on_twist[N_CUBESYM][N_TWIST],
                               int  twist0, int  twist1)
/* ------------------------------------------------------------------------- */

{
int                     twist_arr[2], sym;


for (sym = 0; sym < N_CUBESYM; sym++)
    if (subgroup[sym])
       {
       twist_arr[0] = sym_on_twist[sym][twist0];
       twist_arr[1] = sym_on_twist[sym][twist1];
       clean_up_sequence(twist_arr, 2);
       if ((twist_arr[0] < twist0) ||
           ((twist_arr[0] == twist0) && (twist_arr[1] < twist1)))
          return 1;
       }

return 0;
}


/* ========================================================================= */
   void  calc_twist_on_sylsubgrp(int
                           tw_on_sylsubgrp[N_TWIST][N_SYLLABLE * N_SYMSUBGRP])
/* ------------------------------------------------------------------------- */

{
int             subgroup_list[N_SYMSUBGRP][N_CUBESYM];
int             sym_on_twist[N_CUBESYM][N_TWIST];
int             syllable_on_subgrp[N_SYLLABLE][N_SYMSUBGRP];
int             syllable, subgrp, subgrp_before, subgrp_after, twist;
int             new_syllable, new_subgrp;


calc_subgroup_list(subgroup_list);
calc_sym_on_twist(sym_on_twist);
calc_syllable_on_sym(subgroup_list, sym_on_twist, syllable_on_subgrp);

for (syllable = 0; syllable < N_SYLLABLE; syllable++)
    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
        {
        if (is_single_twist(syllable))
           {
           subgrp_before = subgrp;
           subgrp_after = syllable_on_subgrp[syllable][subgrp];
           }
        else
           {
           subgrp_before = SUBGRP_TRIVIAL;

           if (syllable == SYLLABLE_INVALID)
              subgrp_after = SUBGRP_TRIVIAL;
           else
              subgrp_after = subgrp;
           }

        for (twist = 0; twist < N_TWIST; twist++)
            {
            new_syllable = twist_on_syllable(twist, syllable);

            if (is_single_twist(new_syllable))
               {
               if (not_minimal_one_twist(subgroup_list[subgrp_after],
                                sym_on_twist, syllable_to_twist(new_syllable)))
                  new_syllable = SYLLABLE_INVALID;
               }
            else if (new_syllable != SYLLABLE_INVALID)
                    {
                    if (not_minimal_two_twists(subgroup_list[subgrp_before],
                             sym_on_twist, syllable_to_twist(syllable), twist))
                       new_syllable = SYLLABLE_INVALID;
                    }

            if (new_syllable == SYLLABLE_INVALID)
               new_subgrp = SUBGRP_TRIVIAL;
            else if (is_single_twist(new_syllable))
                    new_subgrp = subgrp_after;
            else
               new_subgrp = syllable_on_subgrp[new_syllable][subgrp_before];

            tw_on_sylsubgrp[twist][syllable * N_SYMSUBGRP + subgrp] =
                                     new_syllable * N_SYMSUBGRP + new_subgrp;
            }
        }

return;
}


/* ========================================================================= */
   void  init_twist_on_follow(void)
/* ------------------------------------------------------------------------- */

{
unsigned short        (*mem_ptr)[N_FOLLOW];
int                     tw_on_sylsubgrp[N_TWIST][N_SYLLABLE * N_SYMSUBGRP];
int                     occurs[N_SYLLABLE * N_SYMSUBGRP];
int                     sylsubgrp_to_follow[N_SYLLABLE * N_SYMSUBGRP];
int                     follow_to_sylsubgrp[N_FOLLOW];
int                     syllable, subgrp, found, twist, count, follow;


calc_twist_on_sylsubgrp(tw_on_sylsubgrp);

for (syllable = 0; syllable < N_SYLLABLE; syllable++)
    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
        occurs[syllable * N_SYMSUBGRP + subgrp] = 0;

for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
    occurs[SYLLABLE_NONE * N_SYMSUBGRP + subgrp] = 1;

found = 1;

while (found)
      {
      found = 0;
      for (syllable = 0; syllable < N_SYLLABLE; syllable++)
          for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
              for (twist = 0; twist < N_TWIST; twist++)
                  if (occurs[tw_on_sylsubgrp[twist]
                                     [syllable * N_SYMSUBGRP + subgrp]] == 0)
                     {
                     occurs[tw_on_sylsubgrp[twist]
                                      [syllable * N_SYMSUBGRP + subgrp]] = 1;
                     found = 1;
                     }
      }

count = 0;

for (syllable = 0; syllable < N_SYLLABLE; syllable++)
    for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
        {
        if (occurs[syllable * N_SYMSUBGRP + subgrp] == 0)
           sylsubgrp_to_follow[syllable * N_SYMSUBGRP + subgrp] = -1;
        else
           {
           sylsubgrp_to_follow[syllable * N_SYMSUBGRP + subgrp] = count;
           follow_to_sylsubgrp[count] = syllable * N_SYMSUBGRP + subgrp;
           count++;
           }
        }

if (count != N_FOLLOW)
   exit_w_error_message("init_twist_on_follow : wrong number of  follow's");

for (subgrp = 0; subgrp < N_SYMSUBGRP; subgrp++)
    if (sylsubgrp_to_follow[SYLLABLE_NONE * N_SYMSUBGRP + subgrp]
                                                                 != 1 + subgrp)
       exit_w_error_message("init_twist_on_follow : indexing error");

mem_ptr = (unsigned short (*)[N_FOLLOW])
                            malloc(sizeof(unsigned short [N_TWIST][N_FOLLOW]));
if (mem_ptr == NULL)
   exit_w_error_message("init_twist_on_follow : couldn't get memory");

for (twist = 0; twist < N_TWIST; twist++)
    twist_on_follow[twist] = mem_ptr[twist];

for (twist = 0; twist < N_TWIST; twist++)
    for (follow = 0; follow < N_FOLLOW; follow++)
        twist_on_follow[twist][follow] =
            (unsigned short)sylsubgrp_to_follow[tw_on_sylsubgrp[twist]
                                                [follow_to_sylsubgrp[follow]]];

return;
}


/* ========================================================================= */
   void  corner_unpack(int  corner, int  array_out[8])
/* ------------------------------------------------------------------------- */

/*  input:  corner
   output:  array_out[]  */

{
int                     ii;


for (ii = 0; ii < 7; ii++)
    {
    array_out[ii] = corner % 3;
    corner = corner / 3;
    }

array_out[7] = (2 * (array_out[0] + array_out[1] + array_out[2] + array_out[3]
                            + array_out[4] + array_out[5] + array_out[6])) % 3;

return;
}


/* ========================================================================= */
   int  corner_pack(int  array_in[8])
/* ------------------------------------------------------------------------- */

/*  input:  array_in[]  */

{
int                     corner, ii;


corner = 0;
for (ii = 6; ii >= 0; ii--)
    corner = 3 * corner + array_in[ii];

return corner;
}


/* ========================================================================= */
   void  corner_adjust(int  array[8], int  ind0, int  ind1, int  ind2,
                                                            int  ind3)
/* ------------------------------------------------------------------------- */

{
array[ind0] = (array[ind0] + 1) % 3;
array[ind1] = (array[ind1] + 2) % 3;
array[ind2] = (array[ind2] + 1) % 3;
array[ind3] = (array[ind3] + 2) % 3;

return;
}


/* ========================================================================= */
   int  twist_f_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_DFL, CORNER_DRF, CORNER_UFR, CORNER_ULF);
corner_adjust(temp_arr, CORNER_DFL, CORNER_DRF, CORNER_UFR, CORNER_ULF);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_r_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_URB, CORNER_UFR);
corner_adjust(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_URB, CORNER_UFR);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_u_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_UFR, CORNER_URB, CORNER_UBL, CORNER_ULF);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_b_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_DBR, CORNER_DLB, CORNER_UBL, CORNER_URB);
corner_adjust(temp_arr, CORNER_DBR, CORNER_DLB, CORNER_UBL, CORNER_URB);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_l_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_DLB, CORNER_DFL, CORNER_ULF, CORNER_UBL);
corner_adjust(temp_arr, CORNER_DLB, CORNER_DFL, CORNER_ULF, CORNER_UBL);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_d_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_DFL, CORNER_DLB, CORNER_DBR, CORNER_DRF);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   void  init_twist_on_corner(void)
/* ------------------------------------------------------------------------- */

{
int                     twist, corner;


/*  allocate and initialize global array   twist_on_corner    */

twist_on_corner[0] =
          (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_CORNER]));
if (twist_on_corner[0] == NULL)
   exit_w_error_message("init_twist_on_corner : couldn't get memory");

for (twist = 1; twist < N_TWIST; twist++)
    twist_on_corner[twist] = &twist_on_corner[0][twist * N_CORNER];

for (corner = 0; corner < N_CORNER; corner++)
    {
    twist_on_corner[TWIST_F][corner] =
                                     (unsigned short)twist_f_on_corner(corner);
    twist_on_corner[TWIST_R][corner] =
                                     (unsigned short)twist_r_on_corner(corner);
    twist_on_corner[TWIST_U][corner] =
                                     (unsigned short)twist_u_on_corner(corner);
    twist_on_corner[TWIST_B][corner] =
                                     (unsigned short)twist_b_on_corner(corner);
    twist_on_corner[TWIST_L][corner] =
                                     (unsigned short)twist_l_on_corner(corner);
    twist_on_corner[TWIST_D][corner] =
                                     (unsigned short)twist_d_on_corner(corner);
    }
for (corner = 0; corner < N_CORNER; corner++)
    {
    twist_on_corner[TWIST_F2][corner] =
              twist_on_corner[TWIST_F][(int)twist_on_corner[TWIST_F][corner]];
    twist_on_corner[TWIST_R2][corner] =
              twist_on_corner[TWIST_R][(int)twist_on_corner[TWIST_R][corner]];
    twist_on_corner[TWIST_U2][corner] =
              twist_on_corner[TWIST_U][(int)twist_on_corner[TWIST_U][corner]];
    twist_on_corner[TWIST_B2][corner] =
              twist_on_corner[TWIST_B][(int)twist_on_corner[TWIST_B][corner]];
    twist_on_corner[TWIST_L2][corner] =
              twist_on_corner[TWIST_L][(int)twist_on_corner[TWIST_L][corner]];
    twist_on_corner[TWIST_D2][corner] =
              twist_on_corner[TWIST_D][(int)twist_on_corner[TWIST_D][corner]];
    }
for (corner = 0; corner < N_CORNER; corner++)
    {
    twist_on_corner[TWIST_F3][corner] =
              twist_on_corner[TWIST_F2][(int)twist_on_corner[TWIST_F][corner]];
    twist_on_corner[TWIST_R3][corner] =
              twist_on_corner[TWIST_R2][(int)twist_on_corner[TWIST_R][corner]];
    twist_on_corner[TWIST_U3][corner] =
              twist_on_corner[TWIST_U2][(int)twist_on_corner[TWIST_U][corner]];
    twist_on_corner[TWIST_B3][corner] =
              twist_on_corner[TWIST_B2][(int)twist_on_corner[TWIST_B][corner]];
    twist_on_corner[TWIST_L3][corner] =
              twist_on_corner[TWIST_L2][(int)twist_on_corner[TWIST_L][corner]];
    twist_on_corner[TWIST_D3][corner] =
              twist_on_corner[TWIST_D2][(int)twist_on_corner[TWIST_D][corner]];
    }

return;
}


/* ========================================================================= */
   int  sym_cu_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
four_cycle(temp_arr, CORNER_UFR, CORNER_URB, CORNER_UBL, CORNER_ULF);
four_cycle(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_DLB, CORNER_DFL);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  sym_cf2_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


corner_unpack(corner, temp_arr);
two_cycle(temp_arr, CORNER_UFR, CORNER_DFL);
two_cycle(temp_arr, CORNER_ULF, CORNER_DRF);
two_cycle(temp_arr, CORNER_UBL, CORNER_DBR);
two_cycle(temp_arr, CORNER_URB, CORNER_DLB);

return corner_pack(temp_arr);
}


/* ========================================================================= */
   int  sym_rud_on_corner(int  corner)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8], ii;


corner_unpack(corner, temp_arr);
two_cycle(temp_arr, CORNER_UFR, CORNER_DRF);
two_cycle(temp_arr, CORNER_ULF, CORNER_DFL);
two_cycle(temp_arr, CORNER_UBL, CORNER_DLB);
two_cycle(temp_arr, CORNER_URB, CORNER_DBR);

for (ii = 0; ii < 8; ii++)
    temp_arr[ii] = (2 * temp_arr[ii]) % 3;

return corner_pack(temp_arr);
}


/* ========================================================================= */
   void  init_sym_on_corner(void)
/* ------------------------------------------------------------------------- */

{
int                     corner, sym;


/*  allocate and initialize global array   sym_on_corner    */

sym_on_corner[0] =
            (unsigned short *)malloc(sizeof(unsigned short [N_SYM][N_CORNER]));
if (sym_on_corner[0] == NULL)
   exit_w_error_message("init_sym_on_corner : couldn't get memory");

for (sym = 1; sym < N_SYM; sym++)
    sym_on_corner[sym] = &sym_on_corner[0][sym * N_CORNER];

for (corner = 0; corner < N_CORNER; corner++)
    sym_on_corner[0][corner] = (unsigned short)corner;

for (corner = 0; corner < N_CORNER; corner++)
    sym_on_corner[1][corner] = (unsigned short)sym_cu_on_corner(corner);

for (sym = 2; sym < 4; sym++)
    for (corner = 0; corner < N_CORNER; corner++)
        sym_on_corner[sym][corner] =
                         sym_on_corner[1][(int)sym_on_corner[sym - 1][corner]];

for (corner = 0; corner < N_CORNER; corner++)
    sym_on_corner[4][corner] = (unsigned short)sym_cf2_on_corner(corner);

for (sym = 5; sym < 8; sym++)
    for (corner = 0; corner < N_CORNER; corner++)
        sym_on_corner[sym][corner] =
                         sym_on_corner[4][(int)sym_on_corner[sym - 4][corner]];

for (corner = 0; corner < N_CORNER; corner++)
    sym_on_corner[8][corner] = (unsigned short)sym_rud_on_corner(corner);

for (sym = 9; sym < 16; sym++)
    for (corner = 0; corner < N_CORNER; corner++)
        sym_on_corner[sym][corner] =
                         sym_on_corner[8][(int)sym_on_corner[sym - 8][corner]];

return;
}


/* ========================================================================= */
   void  calc_edgeloc_conv(int  conv_tab[N_ELOC], int  unconv_tab[N_ELOC_CONV])
/* ------------------------------------------------------------------------- */

{
int                     ii, loc0, loc1, loc2, loc3, count;


for (ii = 0; ii < N_ELOC; ii++)
    conv_tab[ii] = -1;

for (ii = 0; ii < N_ELOC_CONV; ii++)
    unconv_tab[ii] = -1;

count = 0;
for (loc0 = 0; loc0 < 9; loc0++)
    for (loc1 = loc0 + 1; loc1 < 10; loc1++)
        for (loc2 = loc1 + 1; loc2 < 11; loc2++)
            for (loc3 = loc2 + 1; loc3 < 12; loc3++)
                {
                if (count >= N_ELOC)
                   exit_w_error_message("calc_edgeloc_conv : too many eloc's");
                conv_tab[count] = (1 << loc0) | (1 << loc1) |
                                  (1 << loc2) | (1 << loc3);
                unconv_tab[conv_tab[count]] = count;
                count++;
                }

if (count != N_ELOC)
   exit_w_error_message("calc_edgeloc_conv : wrong number of  eloc's");

return;
}


/* ========================================================================= */
   int  edgeloc_conv_or_unconv(int  eloc_conv_or_unconv, int  convert_flag)
/* ------------------------------------------------------------------------- */

{
static int              eloc_conv[N_ELOC];
static int              eloc_unconv[N_ELOC_CONV];
static int              initialized = 0;
int                     el_conv, el_unconv;


if (initialized == 0)
   {
   calc_edgeloc_conv(eloc_conv, eloc_unconv);
   initialized = 1;
   }

if (convert_flag)
   {
   if ((eloc_conv_or_unconv < 0) || (eloc_conv_or_unconv >= N_ELOC))
      exit_w_error_message("edgeloc_conv_or_unconv : invalid input");

   el_conv = eloc_conv[eloc_conv_or_unconv];

   if (el_conv < 0)
      exit_w_error_message("edgeloc_conv_or_unconv : corrupted data");

   return el_conv;
   }
else
   {
   if ((eloc_conv_or_unconv < 0) || (eloc_conv_or_unconv >= N_ELOC_CONV))
      exit_w_error_message("edgeloc_conv_or_unconv : invalid input");

   el_unconv = eloc_unconv[eloc_conv_or_unconv];

   if (el_unconv < 0)
      exit_w_error_message("edgeloc_conv_or_unconv : corrupted data");

   return el_unconv;
   }
}


/* ========================================================================= */
   int  edgeloc_conv(int  eloc_unconv)
/* ------------------------------------------------------------------------- */

{
return edgeloc_conv_or_unconv(eloc_unconv, 1);
}


/* ========================================================================= */
   int  edgeloc_unconv(int  eloc_conv)
/* ------------------------------------------------------------------------- */

{
return edgeloc_conv_or_unconv(eloc_conv, 0);
}


/* ========================================================================= */
   void  eloc_unpack(int  eloc, int  array_out[12])
/* ------------------------------------------------------------------------- */

/*  input:  eloc
   output:  array_out[]  */

{
int                     conv, ii;


conv = edgeloc_conv(eloc);

for (ii = 0; ii < 12; ii++)
    {
    array_out[ii] = conv % 2;
    conv = conv / 2;
    }

return;
}


/* ========================================================================= */
   int  eloc_pack(int  array_in[12])
/* ------------------------------------------------------------------------- */

{
int                     ii, conv;


conv = 0;
for (ii = 11; ii >= 0; ii--)
    conv = 2 * conv + array_in[ii];

return edgeloc_unconv(conv);
}


/* ========================================================================= */
   int  twist_f_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_r_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_FR, EDGE_DR, EDGE_BR, EDGE_UR);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_u_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_UF, EDGE_UR, EDGE_UB, EDGE_UL);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_b_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_l_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_BL, EDGE_DL, EDGE_FL, EDGE_UL);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_d_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_DF, EDGE_DL, EDGE_DB, EDGE_DR);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   void  calc_twist_on_eloc(int  table[N_TWIST][N_ELOC])
/* ------------------------------------------------------------------------- */

{
int                     edgeloc;


for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
    {
    table[TWIST_F][edgeloc] = twist_f_on_eloc(edgeloc);
    table[TWIST_R][edgeloc] = twist_r_on_eloc(edgeloc);
    table[TWIST_U][edgeloc] = twist_u_on_eloc(edgeloc);
    table[TWIST_B][edgeloc] = twist_b_on_eloc(edgeloc);
    table[TWIST_L][edgeloc] = twist_l_on_eloc(edgeloc);
    table[TWIST_D][edgeloc] = twist_d_on_eloc(edgeloc);
    }

perm_n_compose(N_ELOC, table[TWIST_F], table[TWIST_F], table[TWIST_F2]);
perm_n_compose(N_ELOC, table[TWIST_R], table[TWIST_R], table[TWIST_R2]);
perm_n_compose(N_ELOC, table[TWIST_U], table[TWIST_U], table[TWIST_U2]);
perm_n_compose(N_ELOC, table[TWIST_B], table[TWIST_B], table[TWIST_B2]);
perm_n_compose(N_ELOC, table[TWIST_L], table[TWIST_L], table[TWIST_L2]);
perm_n_compose(N_ELOC, table[TWIST_D], table[TWIST_D], table[TWIST_D2]);

perm_n_compose(N_ELOC, table[TWIST_F2], table[TWIST_F], table[TWIST_F3]);
perm_n_compose(N_ELOC, table[TWIST_R2], table[TWIST_R], table[TWIST_R3]);
perm_n_compose(N_ELOC, table[TWIST_U2], table[TWIST_U], table[TWIST_U3]);
perm_n_compose(N_ELOC, table[TWIST_B2], table[TWIST_B], table[TWIST_B3]);
perm_n_compose(N_ELOC, table[TWIST_L2], table[TWIST_L], table[TWIST_L3]);
perm_n_compose(N_ELOC, table[TWIST_D2], table[TWIST_D], table[TWIST_D3]);

return;
}


/* ========================================================================= */
   int  sym_cu_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
four_cycle(temp_arr, EDGE_UF, EDGE_UR, EDGE_UB, EDGE_UL);
four_cycle(temp_arr, EDGE_DF, EDGE_DR, EDGE_DB, EDGE_DL);
four_cycle(temp_arr, EDGE_FR, EDGE_BR, EDGE_BL, EDGE_FL);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  sym_cf2_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
two_cycle(temp_arr, EDGE_UF, EDGE_DF);
two_cycle(temp_arr, EDGE_UR, EDGE_DL);
two_cycle(temp_arr, EDGE_UB, EDGE_DB);
two_cycle(temp_arr, EDGE_UL, EDGE_DR);
two_cycle(temp_arr, EDGE_FR, EDGE_FL);
two_cycle(temp_arr, EDGE_BR, EDGE_BL);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   int  sym_rud_on_eloc(int  eloc)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eloc_unpack(eloc, temp_arr);
two_cycle(temp_arr, EDGE_UF, EDGE_DF);
two_cycle(temp_arr, EDGE_UR, EDGE_DR);
two_cycle(temp_arr, EDGE_UB, EDGE_DB);
two_cycle(temp_arr, EDGE_UL, EDGE_DL);

return eloc_pack(temp_arr);
}


/* ========================================================================= */
   void  calc_sym_on_eloc(int  table[N_SYM][N_ELOC])
/* ------------------------------------------------------------------------- */

{
int                     edgeloc, sym;


perm_n_init(N_ELOC, table[0]);

for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
    table[1][edgeloc] = sym_cu_on_eloc(edgeloc);

for (sym = 2; sym < 4; sym++)
    perm_n_compose(N_ELOC, table[1], table[sym - 1], table[sym]);

for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
    table[4][edgeloc] = sym_cf2_on_eloc(edgeloc);

for (sym = 5; sym < 8; sym++)
    perm_n_compose(N_ELOC, table[4], table[sym - 4], table[sym]);

for (edgeloc = 0; edgeloc < N_ELOC; edgeloc++)
    table[8][edgeloc] = sym_rud_on_eloc(edgeloc);

for (sym = 9; sym < 16; sym++)
    perm_n_compose(N_ELOC, table[8], table[sym - 8], table[sym]);

return;
}


/* ========================================================================= */
   void  eflip_unpack(int  eflip, int  array_out[12])
/* ------------------------------------------------------------------------- */

{
int                     ii;


for (ii = 0; ii < 11; ii++)
    {
    array_out[ii] = eflip % 2;
    eflip = eflip / 2;
    }

array_out[11] = (array_out[0] + array_out[1] + array_out[2] + array_out[3] +
                 array_out[4] + array_out[5] + array_out[6] + array_out[7] +
                 array_out[8] + array_out[9] + array_out[10]) % 2;

return;
}


/* ========================================================================= */
   int  eflip_pack(int  array_in[12])
/* ------------------------------------------------------------------------- */

{
int                     eflip, ii;


eflip = 0;
for (ii = 10; ii >= 0; ii--)
    eflip = 2 * eflip + array_in[ii];

return eflip;
}


/* ========================================================================= */
   void  eflip_adjust(int  array[12], int  ind0, int  ind1, int  ind2,
                                                            int  ind3)
/* ------------------------------------------------------------------------- */

{
array[ind0] = 1 - array[ind0];
array[ind1] = 1 - array[ind1];
array[ind2] = 1 - array[ind2];
array[ind3] = 1 - array[ind3];

return;
}


/* ========================================================================= */
   int  twist_f_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
four_cycle(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);
eflip_adjust(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_r_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
four_cycle(temp_arr, EDGE_FR, EDGE_DR, EDGE_BR, EDGE_UR);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_u_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
four_cycle(temp_arr, EDGE_UR, EDGE_UB, EDGE_UL, EDGE_UF);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_b_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
four_cycle(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);
eflip_adjust(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_l_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
four_cycle(temp_arr, EDGE_BL, EDGE_DL, EDGE_FL, EDGE_UL);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_d_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
four_cycle(temp_arr, EDGE_DL, EDGE_DB, EDGE_DR, EDGE_DF);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   void  calc_twist_on_eflip(int  table[N_TWIST][N_EFLIP])
/* ------------------------------------------------------------------------- */

{
int                     edgeflip;


for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
    {
    table[TWIST_F][edgeflip] = twist_f_on_eflip(edgeflip);
    table[TWIST_R][edgeflip] = twist_r_on_eflip(edgeflip);
    table[TWIST_U][edgeflip] = twist_u_on_eflip(edgeflip);
    table[TWIST_B][edgeflip] = twist_b_on_eflip(edgeflip);
    table[TWIST_L][edgeflip] = twist_l_on_eflip(edgeflip);
    table[TWIST_D][edgeflip] = twist_d_on_eflip(edgeflip);
    }

perm_n_compose(N_EFLIP, table[TWIST_F], table[TWIST_F], table[TWIST_F2]);
perm_n_compose(N_EFLIP, table[TWIST_R], table[TWIST_R], table[TWIST_R2]);
perm_n_compose(N_EFLIP, table[TWIST_U], table[TWIST_U], table[TWIST_U2]);
perm_n_compose(N_EFLIP, table[TWIST_B], table[TWIST_B], table[TWIST_B2]);
perm_n_compose(N_EFLIP, table[TWIST_L], table[TWIST_L], table[TWIST_L2]);
perm_n_compose(N_EFLIP, table[TWIST_D], table[TWIST_D], table[TWIST_D2]);

perm_n_compose(N_EFLIP, table[TWIST_F2], table[TWIST_F], table[TWIST_F3]);
perm_n_compose(N_EFLIP, table[TWIST_R2], table[TWIST_R], table[TWIST_R3]);
perm_n_compose(N_EFLIP, table[TWIST_U2], table[TWIST_U], table[TWIST_U3]);
perm_n_compose(N_EFLIP, table[TWIST_B2], table[TWIST_B], table[TWIST_B3]);
perm_n_compose(N_EFLIP, table[TWIST_L2], table[TWIST_L], table[TWIST_L3]);
perm_n_compose(N_EFLIP, table[TWIST_D2], table[TWIST_D], table[TWIST_D3]);

return;
}


/* ========================================================================= */
   int  sym_cu2_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
two_cycle(temp_arr, EDGE_UF, EDGE_UB);
two_cycle(temp_arr, EDGE_UR, EDGE_UL);
two_cycle(temp_arr, EDGE_DF, EDGE_DB);
two_cycle(temp_arr, EDGE_DR, EDGE_DL);
two_cycle(temp_arr, EDGE_FR, EDGE_BL);
two_cycle(temp_arr, EDGE_FL, EDGE_BR);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  sym_cf2_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
two_cycle(temp_arr, EDGE_UF, EDGE_DF);
two_cycle(temp_arr, EDGE_UR, EDGE_DL);
two_cycle(temp_arr, EDGE_UB, EDGE_DB);
two_cycle(temp_arr, EDGE_UL, EDGE_DR);
two_cycle(temp_arr, EDGE_FR, EDGE_FL);
two_cycle(temp_arr, EDGE_BR, EDGE_BL);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   int  sym_rud_on_eflip(int  eflip)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


eflip_unpack(eflip, temp_arr);
two_cycle(temp_arr, EDGE_UF, EDGE_DF);
two_cycle(temp_arr, EDGE_UR, EDGE_DR);
two_cycle(temp_arr, EDGE_UB, EDGE_DB);
two_cycle(temp_arr, EDGE_UL, EDGE_DL);

return eflip_pack(temp_arr);
}


/* ========================================================================= */
   void  calc_sym_on_eflip(int  table[N_SYM / 2][N_EFLIP])
/* ------------------------------------------------------------------------- */

{
int                     edgeflip, sym;


perm_n_init(N_EFLIP, table[0]);

for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
    table[1][edgeflip] = sym_cu2_on_eflip(edgeflip);

for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
    table[2][edgeflip] = sym_cf2_on_eflip(edgeflip);

perm_n_compose(N_EFLIP, table[2], table[1], table[3]);

for (edgeflip = 0; edgeflip < N_EFLIP; edgeflip++)
    table[4][edgeflip] = sym_rud_on_eflip(edgeflip);

for (sym = 5; sym < 8; sym++)
    perm_n_compose(N_EFLIP, table[4], table[sym - 4], table[sym]);

return;
}


/* ========================================================================= */
   int  sym_cu_on_fulledge(int  fulledge)
/* ------------------------------------------------------------------------- */

{
int                     edgeloc_arr[12], edgeflip_arr[12], temp_arr[12], ii;


eloc_unpack(fulledge / N_EFLIP, edgeloc_arr);
eflip_unpack(fulledge % N_EFLIP, edgeflip_arr);

for (ii = 0; ii < 12; ii++)
    temp_arr[ii] = (edgeloc_arr[ii] != edgeflip_arr[ii]);

four_cycle(temp_arr, EDGE_UR, EDGE_UB, EDGE_UL, EDGE_UF);
four_cycle(temp_arr, EDGE_DR, EDGE_DB, EDGE_DL, EDGE_DF);
four_cycle(temp_arr, EDGE_BR, EDGE_BL, EDGE_FL, EDGE_FR);
eflip_adjust(temp_arr, EDGE_FR, EDGE_FL, EDGE_BR, EDGE_BL);

return sym_cu_on_eloc(fulledge / N_EFLIP) * N_EFLIP + eflip_pack(temp_arr);
}


/* ========================================================================= */
   void  init_fulledge_to_edgequot(int  sym_on_eloc[N_SYM][N_ELOC],
                                   int  sym_on_eflip[N_SYM / 2][N_EFLIP],
                                   int  edge_to_fulledge[N_EDGEQUOT],
                                   int  stabilizers[N_EDGEQUOT],
                                   int  multiplicities[N_EDGEQUOT])
/* ------------------------------------------------------------------------- */

{
int                     count, sym_count, fulledge, cu_fulledge, sym, min_sym;
int                     min_full, new_full, stab;


fulledge_to_edge =
                 (unsigned short *)malloc(sizeof(unsigned short [N_FULLEDGE]));
fulledge_to_sym = (unsigned char *)malloc(sizeof(unsigned char [N_FULLEDGE]));

if ((fulledge_to_edge == NULL) || (fulledge_to_sym == NULL))
   exit_w_error_message("init_fulledge_to_edgequot : couldn't get memory");

count = 0;

for (fulledge = 0; fulledge < N_FULLEDGE; fulledge++)
    {
    min_full = fulledge;
    min_sym = 0;
    stab = 0;
    sym_count = 0;
    cu_fulledge = sym_cu_on_fulledge(fulledge);

    for (sym = 0; sym < (N_SYM / 2); sym++)
        {
        new_full = sym_on_eloc[2 * sym][fulledge / N_EFLIP] * N_EFLIP +
                                         sym_on_eflip[sym][fulledge % N_EFLIP];
        if (min_full > new_full)
           {
           min_full = new_full;
           min_sym = 2 * sym;
           }
        else if (min_full == new_full)
           {
           stab |= (1 << (2 * sym));
           sym_count++;
           }

        new_full = sym_on_eloc[2 * sym][cu_fulledge / N_EFLIP] * N_EFLIP +
                                      sym_on_eflip[sym][cu_fulledge % N_EFLIP];
        if (min_full > new_full)
           {
           min_full = new_full;
           min_sym = 2 * sym + 1;
           }
        else if (min_full == new_full)
           {
           stab |= (1 << (2 * sym + 1));
           sym_count++;
           }
        }

    if (min_sym == 0)
       {
       if (count >= N_EDGEQUOT)
          exit_w_error_message(
                           "init_fulledge_to_edgequot : too many  edgequot's");
       edge_to_fulledge[count] = fulledge;
       stabilizers[count] = stab;
       multiplicities[count] = N_SYM / sym_count;
       fulledge_to_edge[fulledge] = (unsigned short)count;
       fulledge_to_sym[fulledge] = sym_x_invsym_to_sym[0][0];
       count++;
       }
    else
       {
       fulledge_to_edge[fulledge] = fulledge_to_edge[min_full];
       fulledge_to_sym[fulledge] = sym_x_invsym_to_sym[0][min_sym];
       }
    }

if (count != N_EDGEQUOT)
   exit_w_error_message(
                    "init_fulledge_to_edgequot : wrong number of  edgequot's");

return;
}


/* ========================================================================= */
   void  init_twist_on_edge(int  twist_on_eloc[N_TWIST][N_ELOC],
                            int  twist_on_eflip[N_TWIST][N_EFLIP],
                            int  edge_to_fulledge[N_EDGEQUOT])
/* ------------------------------------------------------------------------- */

{
int                     twist, edge, fulledge, new_edge;


/*  allocate and initialize global arrays         */
/*  twist_on_edge   and    twist_x_edge_to_sym    */

twist_on_edge[0] =
        (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_EDGEQUOT]));
twist_x_edge_to_sym[0] =
          (unsigned char *)malloc(sizeof(unsigned char [N_TWIST][N_EDGEQUOT]));

if ((twist_on_edge[0] == NULL) || (twist_x_edge_to_sym[0] == NULL))
   exit_w_error_message("init_twist_on_edge : couldn't get memory");

for (twist = 1; twist < N_TWIST; twist++)
    {
    twist_on_edge[twist] = &twist_on_edge[0][twist * N_EDGEQUOT];
    twist_x_edge_to_sym[twist] = &twist_x_edge_to_sym[0][twist * N_EDGEQUOT];
    }

for (twist = 0; twist < N_TWIST; twist++)
    for (edge = 0; edge < N_EDGEQUOT; edge++)
        {
        fulledge = edge_to_fulledge[edge];
        new_edge = twist_on_eloc[twist][fulledge / N_EFLIP] * N_EFLIP +
                                   twist_on_eflip[twist][fulledge % N_EFLIP];
        twist_on_edge[twist][edge] = fulledge_to_edge[new_edge];
        twist_x_edge_to_sym[twist][edge] =
                        sym_x_invsym_to_sym[0][(int)fulledge_to_sym[new_edge]];
        }

return;
}


/* ========================================================================= */
   void  init_edge_quotient(int  stabilizers[N_EDGEQUOT],
                            int  multiplicities[N_EDGEQUOT])
/* ------------------------------------------------------------------------- */

{
int                     twist_on_eloc[N_TWIST][N_ELOC];
int                     twist_on_eflip[N_TWIST][N_EFLIP];
int                     sym_on_eloc[N_SYM][N_ELOC];
int                     sym_on_eflip[N_SYM / 2][N_EFLIP];
int                     edge_to_fulledge[N_EDGEQUOT];


calc_twist_on_eloc(twist_on_eloc);
calc_sym_on_eloc(sym_on_eloc);
calc_twist_on_eflip(twist_on_eflip);
calc_sym_on_eflip(sym_on_eflip);
init_fulledge_to_edgequot(sym_on_eloc, sym_on_eflip, edge_to_fulledge,
                                                  stabilizers, multiplicities);
init_twist_on_edge(twist_on_eloc, twist_on_eflip, edge_to_fulledge);

return;
}


/* ========================================================================= */
   void  cornerperm_unpack(int  cperm, int  array_out[8])
/* ------------------------------------------------------------------------- */

{
perm_n_unpack(8, cperm, array_out);

return;
}


/* ========================================================================= */
   int  cornerperm_pack(int  array_in[8])
/* ------------------------------------------------------------------------- */

{
return perm_n_pack(8, array_in);
}


/* ========================================================================= */
   int  twist_f_on_cperm(int  cperm)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


cornerperm_unpack(cperm, temp_arr);
four_cycle(temp_arr, CORNER_DFL, CORNER_DRF, CORNER_UFR, CORNER_ULF);

return cornerperm_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_r_on_cperm(int  cperm)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


cornerperm_unpack(cperm, temp_arr);
four_cycle(temp_arr, CORNER_DRF, CORNER_DBR, CORNER_URB, CORNER_UFR);

return cornerperm_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_u_on_cperm(int  cperm)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


cornerperm_unpack(cperm, temp_arr);
four_cycle(temp_arr, CORNER_URB, CORNER_UBL, CORNER_ULF, CORNER_UFR);

return cornerperm_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_b_on_cperm(int  cperm)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


cornerperm_unpack(cperm, temp_arr);
four_cycle(temp_arr, CORNER_DBR, CORNER_DLB, CORNER_UBL, CORNER_URB);

return cornerperm_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_l_on_cperm(int  cperm)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


cornerperm_unpack(cperm, temp_arr);
four_cycle(temp_arr, CORNER_DLB, CORNER_DFL, CORNER_ULF, CORNER_UBL);

return cornerperm_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_d_on_cperm(int  cperm)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[8];


cornerperm_unpack(cperm, temp_arr);
four_cycle(temp_arr, CORNER_DFL, CORNER_DLB, CORNER_DBR, CORNER_DRF);

return cornerperm_pack(temp_arr);
}


/* ========================================================================= */
   void  init_twist_on_cornerperm(void)
/* ------------------------------------------------------------------------- */

{
int                     cp, twist;


/*  allocate and initialize global array    twist_on_cornerperm    */

twist_on_cornerperm[0] =
      (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_CORNERPERM]));
if (twist_on_cornerperm[0] == NULL)
   exit_w_error_message("init_twist_on_cornerperm : couldn't get memory");

for (twist = 1; twist < N_TWIST; twist++)
    twist_on_cornerperm[twist] = &twist_on_cornerperm[0][twist * N_CORNERPERM];

for (cp = 0; cp < N_CORNERPERM; cp++)
    {
    twist_on_cornerperm[TWIST_F][cp] = (unsigned short)twist_f_on_cperm(cp);
    twist_on_cornerperm[TWIST_R][cp] = (unsigned short)twist_r_on_cperm(cp);
    twist_on_cornerperm[TWIST_U][cp] = (unsigned short)twist_u_on_cperm(cp);
    twist_on_cornerperm[TWIST_B][cp] = (unsigned short)twist_b_on_cperm(cp);
    twist_on_cornerperm[TWIST_L][cp] = (unsigned short)twist_l_on_cperm(cp);
    twist_on_cornerperm[TWIST_D][cp] = (unsigned short)twist_d_on_cperm(cp);
    }
for (cp = 0; cp < N_CORNERPERM; cp++)
    {
    twist_on_cornerperm[TWIST_F2][cp] =
          twist_on_cornerperm[TWIST_F][(int)twist_on_cornerperm[TWIST_F][cp]];
    twist_on_cornerperm[TWIST_R2][cp] =
          twist_on_cornerperm[TWIST_R][(int)twist_on_cornerperm[TWIST_R][cp]];
    twist_on_cornerperm[TWIST_U2][cp] =
          twist_on_cornerperm[TWIST_U][(int)twist_on_cornerperm[TWIST_U][cp]];
    twist_on_cornerperm[TWIST_B2][cp] =
          twist_on_cornerperm[TWIST_B][(int)twist_on_cornerperm[TWIST_B][cp]];
    twist_on_cornerperm[TWIST_L2][cp] =
          twist_on_cornerperm[TWIST_L][(int)twist_on_cornerperm[TWIST_L][cp]];
    twist_on_cornerperm[TWIST_D2][cp] =
          twist_on_cornerperm[TWIST_D][(int)twist_on_cornerperm[TWIST_D][cp]];
    }
for (cp = 0; cp < N_CORNERPERM; cp++)
    {
    twist_on_cornerperm[TWIST_F3][cp] =
          twist_on_cornerperm[TWIST_F2][(int)twist_on_cornerperm[TWIST_F][cp]];
    twist_on_cornerperm[TWIST_R3][cp] =
          twist_on_cornerperm[TWIST_R2][(int)twist_on_cornerperm[TWIST_R][cp]];
    twist_on_cornerperm[TWIST_U3][cp] =
          twist_on_cornerperm[TWIST_U2][(int)twist_on_cornerperm[TWIST_U][cp]];
    twist_on_cornerperm[TWIST_B3][cp] =
          twist_on_cornerperm[TWIST_B2][(int)twist_on_cornerperm[TWIST_B][cp]];
    twist_on_cornerperm[TWIST_L3][cp] =
          twist_on_cornerperm[TWIST_L2][(int)twist_on_cornerperm[TWIST_L][cp]];
    twist_on_cornerperm[TWIST_D3][cp] =
          twist_on_cornerperm[TWIST_D2][(int)twist_on_cornerperm[TWIST_D][cp]];
    }

return;
}


/* ========================================================================= */
   void  sliceedge_unpack(int  sliceedge, int  array_out[12])
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[4], ii, count;


eloc_unpack(sliceedge % N_ELOC, array_out);
perm_n_unpack(4, sliceedge / N_ELOC, temp_arr);

count = 0;
for (ii = 0; ii < 12; ii++)
    if (array_out[ii] != 0)
       {
       if (count >= 4)
          exit_w_error_message("sliceedge_unpack : corrupted data");

       array_out[ii] = 1 + temp_arr[count++];
       }

return;
}


/* ========================================================================= */
   int  sliceedge_pack(int  array_in[12])
/* ------------------------------------------------------------------------- */

{
int                     eloc_arr[12], temp_arr[4], ii, count;


count = 0;
for (ii = 0; ii < 12; ii++)
    {
    if (array_in[ii] != 0)
       {
       if (count >= 4)
          exit_w_error_message("sliceedge_pack : invalid input");

       temp_arr[count++] = array_in[ii] - 1;
       }

    eloc_arr[ii] = (array_in[ii] != 0);
    }

return perm_n_pack(4, temp_arr) * N_ELOC + eloc_pack(eloc_arr);
}


/* ========================================================================= */
   int  twist_f_on_sliceedge(int  sliceedge)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


sliceedge_unpack(sliceedge, temp_arr);
four_cycle(temp_arr, EDGE_FL, EDGE_DF, EDGE_FR, EDGE_UF);

return sliceedge_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_r_on_sliceedge(int  sliceedge)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


sliceedge_unpack(sliceedge, temp_arr);
four_cycle(temp_arr, EDGE_FR, EDGE_DR, EDGE_BR, EDGE_UR);

return sliceedge_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_u_on_sliceedge(int  sliceedge)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


sliceedge_unpack(sliceedge, temp_arr);
four_cycle(temp_arr, EDGE_UR, EDGE_UB, EDGE_UL, EDGE_UF);

return sliceedge_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_b_on_sliceedge(int  sliceedge)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


sliceedge_unpack(sliceedge, temp_arr);
four_cycle(temp_arr, EDGE_BR, EDGE_DB, EDGE_BL, EDGE_UB);

return sliceedge_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_l_on_sliceedge(int  sliceedge)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


sliceedge_unpack(sliceedge, temp_arr);
four_cycle(temp_arr, EDGE_BL, EDGE_DL, EDGE_FL, EDGE_UL);

return sliceedge_pack(temp_arr);
}


/* ========================================================================= */
   int  twist_d_on_sliceedge(int  sliceedge)
/* ------------------------------------------------------------------------- */

{
int                     temp_arr[12];


sliceedge_unpack(sliceedge, temp_arr);
four_cycle(temp_arr, EDGE_DL, EDGE_DB, EDGE_DR, EDGE_DF);

return sliceedge_pack(temp_arr);
}


/* ========================================================================= */
   void  init_twist_on_sliceedge(void)
/* ------------------------------------------------------------------------- */

{
int                     twist, sl;


/*  allocate and initialize global array    twist_on_sliceedge    */

twist_on_sliceedge[0] =
     (unsigned short *)malloc(sizeof(unsigned short [N_TWIST][N_SLICEEDGE]));
if (twist_on_sliceedge[0] == NULL)
   exit_w_error_message("init_twist_on_sliceedge : couldn't get memory");

for (twist = 1; twist < N_TWIST; twist++)
    twist_on_sliceedge[twist] = &twist_on_sliceedge[0][twist * N_SLICEEDGE];

for (sl = 0; sl < N_SLICEEDGE; sl++)
    {
    twist_on_sliceedge[TWIST_F][sl] = (unsigned short)twist_f_on_sliceedge(sl);
    twist_on_sliceedge[TWIST_R][sl] = (unsigned short)twist_r_on_sliceedge(sl);
    twist_on_sliceedge[TWIST_U][sl] = (unsigned short)twist_u_on_sliceedge(sl);
    twist_on_sliceedge[TWIST_B][sl] = (unsigned short)twist_b_on_sliceedge(sl);
    twist_on_sliceedge[TWIST_L][sl] = (unsigned short)twist_l_on_sliceedge(sl);
    twist_on_sliceedge[TWIST_D][sl] = (unsigned short)twist_d_on_sliceedge(sl);
    }
for (sl = 0; sl < N_SLICEEDGE; sl++)
    {
    twist_on_sliceedge[TWIST_F2][sl] =
            twist_on_sliceedge[TWIST_F][(int)twist_on_sliceedge[TWIST_F][sl]];
    twist_on_sliceedge[TWIST_R2][sl] =
            twist_on_sliceedge[TWIST_R][(int)twist_on_sliceedge[TWIST_R][sl]];
    twist_on_sliceedge[TWIST_U2][sl] =
            twist_on_sliceedge[TWIST_U][(int)twist_on_sliceedge[TWIST_U][sl]];
    twist_on_sliceedge[TWIST_B2][sl] =
            twist_on_sliceedge[TWIST_B][(int)twist_on_sliceedge[TWIST_B][sl]];
    twist_on_sliceedge[TWIST_L2][sl] =
            twist_on_sliceedge[TWIST_L][(int)twist_on_sliceedge[TWIST_L][sl]];
    twist_on_sliceedge[TWIST_D2][sl] =
            twist_on_sliceedge[TWIST_D][(int)twist_on_sliceedge[TWIST_D][sl]];
    }
for (sl = 0; sl < N_SLICEEDGE; sl++)
    {
    twist_on_sliceedge[TWIST_F3][sl] =
            twist_on_sliceedge[TWIST_F2][(int)twist_on_sliceedge[TWIST_F][sl]];
    twist_on_sliceedge[TWIST_R3][sl] =
            twist_on_sliceedge[TWIST_R2][(int)twist_on_sliceedge[TWIST_R][sl]];
    twist_on_sliceedge[TWIST_U3][sl] =
            twist_on_sliceedge[TWIST_U2][(int)twist_on_sliceedge[TWIST_U][sl]];
    twist_on_sliceedge[TWIST_B3][sl] =
            twist_on_sliceedge[TWIST_B2][(int)twist_on_sliceedge[TWIST_B][sl]];
    twist_on_sliceedge[TWIST_L3][sl] =
            twist_on_sliceedge[TWIST_L2][(int)twist_on_sliceedge[TWIST_L][sl]];
    twist_on_sliceedge[TWIST_D3][sl] =
            twist_on_sliceedge[TWIST_D2][(int)twist_on_sliceedge[TWIST_D][sl]];
    }

return;
}


/* ========================================================================= */
   int  make_current(int  corner, int  edge, Search_data  *p_data)
/* ------------------------------------------------------------------------- */

{
if (DIST(corner, edge) > p_data->depth)
   {
   if (edge & 0x1)
      {
      distance[corner][edge >> 1] &= 0x0F;
      distance[corner][edge >> 1] |= (unsigned char)((p_data->depth) << 4);
      }
   else
      {
      distance[corner][edge >> 1] &= 0xF0;
      distance[corner][edge >> 1] |= (unsigned char)(p_data->depth);
      }

   p_data->found_quot++;
   p_data->found += (p_data->multiplicities)[edge];

   return 1;
   }

return 0;
}


/* ========================================================================= */
   void  make_current_all(int  corner, int  edge, Search_data  *p_data)
/* ------------------------------------------------------------------------- */

{
int                     sym, stab;


if (make_current(corner, edge, p_data))
   {
   stab = (p_data->stabilizers)[edge];
   for (sym = 1; sym < N_SYM; sym++)
       {
       stab /= 2;

       if (stab % 2)
          make_current((int)sym_on_corner[sym][corner], edge, p_data);
       }
   }

return;
}


/* ========================================================================= */
   void  make_neighbors_current(int  corner, int  edge, Search_data  *p_data)
/* ------------------------------------------------------------------------- */

{
int                     twist, new_edge, new_corner, sym;


for (twist = 0; twist < N_TWIST; twist++)
    {
    if (p_current_metric->twist_length[twist] != 1)
       continue;

    new_edge = (int)twist_on_edge[twist][edge];
    sym = (int)twist_x_edge_to_sym[twist][edge];
    new_corner = (int)sym_on_corner[sym][(int)twist_on_corner[twist][corner]];
    make_current_all(new_corner, new_edge, p_data);
    }

return;
}


/* ========================================================================= */
   int  neighbors_are_previous(int  corner, int  edge, Search_data  *p_data)
/* ------------------------------------------------------------------------- */

{
int                     twist, new_edge, sym, new_corner;


for (twist = 0; twist < N_TWIST; twist++)
    {
    if (p_current_metric->twist_length[twist] != 1)
       continue;

    new_edge = (int)twist_on_edge[twist][edge];
    sym = (int)twist_x_edge_to_sym[twist][edge];
    new_corner = (int)sym_on_corner[sym][(int)twist_on_corner[twist][corner]];

    if (DIST(new_corner, new_edge) < p_data->depth)
       return 1;
    }

return 0;
}


/* ========================================================================= */
   void  init_distance_table(int  edge_stabilizers[N_EDGEQUOT],
                             int  edge_multiplicities[N_EDGEQUOT])
/* ------------------------------------------------------------------------- */

{
Search_data             sdata_struc;
int                     total_found_quot, corner, edge, ii, msg_given;


/*  allocate and initialize global array   distance   */

distance[0] = (unsigned char *)malloc(sizeof(unsigned char [N_DIST_CHARS]));
if (distance[0] == NULL)
   exit_w_error_message("init_distance_table : couldn't get memory");

for (corner = 1; corner < N_CORNER; corner++)
    distance[corner] = &distance[0][corner * (N_EDGEQUOT / 2)];

for (ii = 0; ii < N_DIST_CHARS; ii++)
    distance[0][ii] = (unsigned char)255;

msg_given = 0;

sdata_struc.depth = 0;
sdata_struc.found_quot = 0;
sdata_struc.found = 0;
sdata_struc.stabilizers = edge_stabilizers;
sdata_struc.multiplicities = edge_multiplicities;
total_found_quot = 0;

printf("distance     positions     (quotient)\n");

make_current_all(CORNER_START, EDGE_START, &sdata_struc);

while (sdata_struc.found)
      {
      printf("%7d%c %13d     (%8d)\n", sdata_struc.depth,
                      p_current_metric->metric_char, sdata_struc.found,
                                                       sdata_struc.found_quot);
      total_found_quot += sdata_struc.found_quot;
      sdata_struc.found_quot = 0;
      sdata_struc.found = 0;

      if (++(sdata_struc.depth) == 15)
         break;                            /*  shouldn't happen  */

      if (total_found_quot == 2 * N_DIST_CHARS)
         break;

      if (total_found_quot < BACKWARDS_SWITCH_POINT)  /*  search forward  */
         {
         for (corner = 0; corner < N_CORNER; corner++)
             for (edge = 0; edge < N_EDGEQUOT; edge++)
                 if (DIST(corner, edge) == sdata_struc.depth - 1)
                    make_neighbors_current(corner, edge, &sdata_struc);
         }
      else  /*  search backward  */
         {
         if (msg_given == 0)
            {
            printf("     switching to backwards searching\n");
            msg_given = 1;
            }

         for (corner = 0; corner < N_CORNER; corner++)
             for (edge = 0; edge < N_EDGEQUOT; edge++)
                 if ((DIST(corner, edge) == 15) &&
                     neighbors_are_previous(corner, edge, &sdata_struc))
                    make_current_all(corner, edge, &sdata_struc);
         }
      }

return;
}


/* ========================================================================= */
   void  init_globals(void)
/* ------------------------------------------------------------------------- */

{
int                    *edge_stabilizers;
int                    *edge_multiplicities;


printf("initializing transformation tables\n");
init_sym_x_invsym_to_sym();
init_invsym_on_twist();
init_twist_on_follow();
init_twist_on_corner();
init_sym_on_corner();

edge_stabilizers = (int *)malloc(sizeof(int [2 * N_EDGEQUOT]));
if (edge_stabilizers == NULL)
   exit_w_error_message("init_globals : couldn't get memory");

edge_multiplicities = &edge_stabilizers[N_EDGEQUOT];

init_edge_quotient(edge_stabilizers, edge_multiplicities);
init_twist_on_cornerperm();
init_twist_on_sliceedge();
printf("initializing distance table ... this will take several minutes\n");
init_distance_table(edge_stabilizers, edge_multiplicities);

free((void *)edge_stabilizers);

return;
}


/* ========================================================================= */
   int  string_to_cube(char  string[], Cube  *p_cube, int  give_err_msg)
/* ------------------------------------------------------------------------- */

/*  input:  string[]  */

{
char                    edge_str[12][3], corner_str[8][4];
int                     edge_arr[12], corner_arr[8];
int                     ii, jj, twist, flip, edge_par, corner_par, stat;


stat = 0;

if (sscanf(string, "%2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %2s %3s %3s %3s %3s %3s %3s %3s %3s",
           edge_str[0], edge_str[1], edge_str[2], edge_str[3],
           edge_str[4], edge_str[5], edge_str[6], edge_str[7],
           edge_str[8], edge_str[9], edge_str[10], edge_str[11],
           corner_str[0], corner_str[1], corner_str[2], corner_str[3],
           corner_str[4], corner_str[5], corner_str[6], corner_str[7]) < 20)
   {
   if (give_err_msg)
      printf("invalid input!\n");
   return 1;
   }

for (ii = 0; ii < 12; ii++)
    {
    for (jj = 0; jj < 24; jj++)
        if (strcmp(edge_str[ii], edge_cubie_str[jj]) == 0)
           {
           p_cube->edges[ii] = jj;
           break;
           }
    if (jj == 24)
       {
       if (give_err_msg)
          printf("invalid edge cubie: %s\n", edge_str[ii]);
       stat = 1;
       }
    }

for (ii = 0; ii < 8; ii++)
    {
    for (jj = 0; jj < 24; jj++)
        if (strcmp(corner_str[ii], corner_cubie_str[jj]) == 0)
           {
           p_cube->corners[ii] = jj;
           break;
           }
    if (jj == 24)
       {
       if (give_err_msg)
          printf("invalid corner cubie: %s\n", corner_str[ii]);
       stat = 1;
       }
    }

if (stat)
   return stat;

/*  fill out the remaining oriented edges and corners  */

for (ii = 12; ii < 24; ii++)
    p_cube->edges[ii] = (12 + p_cube->edges[ii - 12]) % 24;

for (ii = 8; ii < 24; ii++)
    p_cube->corners[ii] = (8 + p_cube->corners[ii - 8]) % 24;

/*  now check to see that it's a legal cube  */

if (perm_n_check(24, p_cube->edges))
   {
   if (give_err_msg)
      printf("bad edge cubies\n");
   stat = 1;
   }

if (perm_n_check(24, p_cube->corners))
   {
   if (give_err_msg)
      printf("bad corner cubies\n");
   stat = 1;
   }

if (stat)
   return stat;

flip = 0;
for (ii = 0; ii < 12; ii++)
    flip += (p_cube->edges[ii] / 12);

if ((flip % 2) != 0)
   {
   if (give_err_msg)
      printf("flip any edge cubie!\n");
   stat = 1;
   }

twist = 0;
for (ii = 0; ii < 8; ii++)
    twist += (p_cube->corners[ii] / 8);

twist %= 3;

if (twist != 0)
   {
   if (give_err_msg)
      printf("twist any corner cubie %sclockwise!\n",
              (twist == 1) ? "counter" : "");
   stat = 1;
   }

for (ii = 0; ii < 12; ii++)
    edge_arr[ii] = p_cube->edges[ii] % 12;

edge_par = perm_n_parity(12, edge_arr);

for (ii = 0; ii < 8; ii++)
    corner_arr[ii] = p_cube->corners[ii] % 8;

corner_par = perm_n_parity(8, corner_arr);

if (edge_par != corner_par)
   {
   if (give_err_msg)
      printf("swap any two edge cubies or any two corner cubies!\n");
   stat = 1;
   }

return stat;
}


/* ========================================================================= */
   int  user_enters_cube(Cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
char                     line_str[256];


printf("\nenter cube (Ctrl-D to exit):\n");

line_str[0] = '\n';

while (line_str[0] == '\n')           /*  ignore blank lines  */
      {
      if (fgets(line_str, 256, stdin) == NULL)
         return -1;

      if (line_str[0] == '%')         /*  echo comments  */
         {
         printf("%s", line_str);
         line_str[0] = '\n';
         }
      }

return string_to_cube(line_str, p_cube, 1);
}


/* ========================================================================= */
   void  calc_cube_urf(Cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
cube_init(p_cube);
three_cycle(p_cube->edges, EDGE_UF, EDGE_FR, EDGE_RU);
three_cycle(p_cube->edges, EDGE_UB, EDGE_FL, EDGE_RD);
three_cycle(p_cube->edges, EDGE_DB, EDGE_BL, EDGE_LD);
three_cycle(p_cube->edges, EDGE_DF, EDGE_BR, EDGE_LU);
three_cycle(p_cube->edges, EDGE_FU, EDGE_RF, EDGE_UR);
three_cycle(p_cube->edges, EDGE_BU, EDGE_LF, EDGE_DR);
three_cycle(p_cube->edges, EDGE_BD, EDGE_LB, EDGE_DL);
three_cycle(p_cube->edges, EDGE_FD, EDGE_RB, EDGE_UL);
three_cycle(p_cube->corners, CORNER_UFR, CORNER_FRU, CORNER_RUF);
three_cycle(p_cube->corners, CORNER_DLB, CORNER_BDL, CORNER_LBD);
three_cycle(p_cube->corners, CORNER_URB, CORNER_FUL, CORNER_RFD);
three_cycle(p_cube->corners, CORNER_UBL, CORNER_FLD, CORNER_RDB);
three_cycle(p_cube->corners, CORNER_RBU, CORNER_ULF, CORNER_FDR);
three_cycle(p_cube->corners, CORNER_BLU, CORNER_LDF, CORNER_DBR);
three_cycle(p_cube->corners, CORNER_BUR, CORNER_LFU, CORNER_DRF);
three_cycle(p_cube->corners, CORNER_LUB, CORNER_DFL, CORNER_BRD);

return;
}


/* ========================================================================= */
   void  cube_to_coset_coord(Cube  *p_cube, Coset_coord  *p_coset_coord)
/* ------------------------------------------------------------------------- */

/*  output:  *p_coset_coord  */

{
int                     corner_arr[8], edge_arr[12];
int                     ii, eflip, eloc, sym, corner;


for (ii = 0; ii < 12; ii++)
    edge_arr[ii] = p_cube->edges[ii] / 12;
eflip = eflip_pack(edge_arr);

for (ii = 0; ii < 12; ii++)
    edge_arr[ii] = (p_cube->edges[ii] % 12) / 8;
eloc = eloc_pack(edge_arr);

p_coset_coord->edge_state = (int)fulledge_to_edge[eloc * N_EFLIP + eflip];
p_coset_coord->sym_state = sym = (int)fulledge_to_sym[eloc * N_EFLIP + eflip];

for (ii = 0; ii < 8; ii++)
    corner_arr[ii] = p_cube->corners[ii] / 8;

corner = corner_pack(corner_arr);
p_coset_coord->corner_state =
                  (int)sym_on_corner[(int)sym_x_invsym_to_sym[0][sym]][corner];

return;
}


/* ========================================================================= */
   void  process_full_cube(Full_cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
Cube                    cube1, cube2, cube_urf;
int                     edges_to_ud[12], edges_to_rl[12], edges_to_fb[12];
int                     cornerperm_arr[8], sliceedge_arr[12], ii;


/*  p_cube->cubies  already filled in  */
/*  fill in other fields of  p_cube    */

for (ii = 0; ii < 8; ii++)
    cornerperm_arr[ii] = p_cube->cubies.corners[ii] % 8;

p_cube->cornerperm = cornerperm_pack(cornerperm_arr);
p_cube->parity = perm_n_parity(8, cornerperm_arr);


for (ii = 0; ii < 12; ii++)
    edges_to_ud[ii] = edges_to_fb[ii] = edges_to_rl[ii] = 0;

edges_to_ud[EDGE_FR] = 1;
edges_to_ud[EDGE_FL] = 2;
edges_to_ud[EDGE_BR] = 3;
edges_to_ud[EDGE_BL] = 4;

edges_to_rl[EDGE_UF] = 1;
edges_to_rl[EDGE_UB] = 2;
edges_to_rl[EDGE_DF] = 3;
edges_to_rl[EDGE_DB] = 4;

edges_to_fb[EDGE_UR] = 1;
edges_to_fb[EDGE_UL] = 2;
edges_to_fb[EDGE_DR] = 3;
edges_to_fb[EDGE_DL] = 4;


for (ii = 0; ii < 12; ii++)
    sliceedge_arr[ii] = edges_to_ud[(p_cube->cubies.edges[ii]) % 12];
p_cube->ud_sliceedge = sliceedge_pack(sliceedge_arr);

for (ii = 0; ii < 12; ii++)
    sliceedge_arr[ii] = edges_to_fb[(p_cube->cubies.edges[ii]) % 12];
p_cube->fb_sliceedge = sliceedge_pack(sliceedge_arr);

for (ii = 0; ii < 12; ii++)
    sliceedge_arr[ii] = edges_to_rl[(p_cube->cubies.edges[ii]) % 12];
p_cube->rl_sliceedge = sliceedge_pack(sliceedge_arr);


cube_to_coset_coord(&p_cube->cubies, &p_cube->ud);

calc_cube_urf(&cube_urf);

cube_conjugate(&p_cube->cubies, &cube_urf, &cube1);
cube_to_coset_coord(&cube1, &p_cube->rl);

cube_conjugate(&cube1, &cube_urf, &cube2);
cube_to_coset_coord(&cube2, &p_cube->fb);

return;
}


/* ========================================================================= */
   void  set_cube_symmetry(Full_cube  *p_cube, Cube  sym_cubes[N_CUBESYM],
                           int  subgroup_list[N_SYMSUBGRP][N_CUBESYM])
/* ------------------------------------------------------------------------- */

{
Cube                    temp_cube;
int                     subgroup[N_CUBESYM], sym, count;


if (p_current_options->use_symmetry)
   {
   count = 0;

   for (sym = 0; sym < N_CUBESYM; sym++)
       {
       cube_conjugate(&p_cube->cubies, &sym_cubes[sym], &temp_cube);
       subgroup[sym] = (cube_compare(&p_cube->cubies, &temp_cube) == 0);
       if (subgroup[sym])
          count++;
       }

   p_cube->sym_subgrp = which_subgroup(subgroup, subgroup_list);

   if (p_cube->sym_subgrp < 0)
      exit_w_error_message("set_cube_symmetry : unknown symmetry group");

   if (count > 1)
      printf("position has %d-fold symmetry (subgroup #%d)\n", count,
                                                           p_cube->sym_subgrp);
   else
      printf("asymmetric position\n");
   }
else
   p_cube->sym_subgrp = SUBGRP_TRIVIAL;

return;
}


/* ========================================================================= */
   void  output_solution(Search_node  *node_arr)
/* ------------------------------------------------------------------------- */

{
static char            *twist_string[] = {"F ", "F2", "F'", "R ", "R2", "R'",
                                          "U ", "U2", "U'", "B ", "B2", "B'",
                                          "L ", "L2", "L'", "D ", "D2", "D'"};
Search_node            *p_node;
int                     turn_list[MAX_TWISTS];
int                     ii, count, q_length, f_length;


count = 0;

for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
    turn_list[count++] = p_node[1].twist;

q_length = f_length = 0;

for (ii = 0; ii < count; ii++)
    {
    q_length += metric_q_length(turn_list[ii]);
    f_length += metric_f_length(turn_list[ii]);
    }

for (ii = 0; ii < count; ii++)
    printf(" %s", twist_string[turn_list[ii]]);

if (p_current_metric->metric == QUARTER_TURN_METRIC)
   printf("  (%dq*, %df)\n", q_length, f_length);
else
   printf("  (%df*, %dq)\n", f_length, q_length);
fflush(stdout);

sol_found = 1;

return;
}


/* ========================================================================= */
   int  test_for_solution(Full_cube  *p_cube, Search_node  *node_arr)
/* ------------------------------------------------------------------------- */

{
register Search_node   *p_node;
register int            cornerperm, sliceedge;


n_tests++;

cornerperm = p_cube->cornerperm;
for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
    cornerperm = (int)twist_on_cornerperm[p_node[1].twist][cornerperm];

if (cornerperm != CORNERPERM_START)
   return 0;                                  /*  not a solution  */

sliceedge = p_cube->ud_sliceedge;
for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
    sliceedge = (int)twist_on_sliceedge[p_node[1].twist][sliceedge];

if (sliceedge != UD_SLICEEDGE_START)
   return 0;                                  /*  not a solution  */

sliceedge = p_cube->rl_sliceedge;
for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
    sliceedge = (int)twist_on_sliceedge[p_node[1].twist][sliceedge];

if (sliceedge != RL_SLICEEDGE_START)
   return 0;                                  /*  not a solution  */

sliceedge = p_cube->fb_sliceedge;
for (p_node = node_arr; p_node->remain_depth > 0; p_node++)
    sliceedge = (int)twist_on_sliceedge[p_node[1].twist][sliceedge];

if (sliceedge != FB_SLICEEDGE_START)
   return 0;                                  /*  not a solution  */

output_solution(node_arr);                    /*  solution !  */

return 1;
}


/* ========================================================================= */
   void  search_tree(Full_cube  *p_cube, Search_node  *node_arr)
/* ------------------------------------------------------------------------- */

{
register Search_node   *p_node;
register int            twist, virtual_twist, new_sym_factor;


p_node = node_arr;

while (p_node >= node_arr)
      {
      if (p_node->remain_depth == 0)
         {
         if (test_for_solution(p_cube, node_arr) &&
             p_current_options->one_solution_only)
            return;
         p_node--;
         }
      else
         {
         for (twist = p_node[1].twist + 1; twist < N_TWIST; twist++)
             {
             p_node[1].follow_type =
                              (int)twist_on_follow[twist][p_node->follow_type];

             if (p_node[1].follow_type == FOLLOW_INVALID)
                continue;

             p_node[1].remain_depth = p_node->remain_depth -
                                         p_current_metric->twist_length[twist];
             if (p_node[1].remain_depth < 0)
                continue;

             n_nodes++;

             virtual_twist =
                          (int)invsym_on_twist_ud[p_node->ud.sym_state][twist];
             new_sym_factor =
                (int)twist_x_edge_to_sym[virtual_twist][p_node->ud.edge_state];
             p_node[1].ud.edge_state =
                      (int)twist_on_edge[virtual_twist][p_node->ud.edge_state];
             p_node[1].ud.sym_state =
                (int)sym_x_invsym_to_sym[p_node->ud.sym_state][new_sym_factor];
             p_node[1].ud.corner_state = (int)sym_on_corner[new_sym_factor]
                [(int)twist_on_corner[virtual_twist][p_node->ud.corner_state]];

             if (p_node[1].remain_depth <
                      DIST(p_node[1].ud.corner_state, p_node[1].ud.edge_state))
                continue;


             virtual_twist =
                          (int)invsym_on_twist_rl[p_node->rl.sym_state][twist];
             new_sym_factor =
                (int)twist_x_edge_to_sym[virtual_twist][p_node->rl.edge_state];
             p_node[1].rl.edge_state =
                      (int)twist_on_edge[virtual_twist][p_node->rl.edge_state];
             p_node[1].rl.sym_state =
                (int)sym_x_invsym_to_sym[p_node->rl.sym_state][new_sym_factor];
             p_node[1].rl.corner_state = (int)sym_on_corner[new_sym_factor]
                [(int)twist_on_corner[virtual_twist][p_node->rl.corner_state]];

             if (p_node[1].remain_depth <
                      DIST(p_node[1].rl.corner_state, p_node[1].rl.edge_state))
                continue;


             virtual_twist =
                          (int)invsym_on_twist_fb[p_node->fb.sym_state][twist];
             new_sym_factor =
                (int)twist_x_edge_to_sym[virtual_twist][p_node->fb.edge_state];
             p_node[1].fb.edge_state =
                      (int)twist_on_edge[virtual_twist][p_node->fb.edge_state];
             p_node[1].fb.sym_state =
                (int)sym_x_invsym_to_sym[p_node->fb.sym_state][new_sym_factor];
             p_node[1].fb.corner_state = (int)sym_on_corner[new_sym_factor]
                [(int)twist_on_corner[virtual_twist][p_node->fb.corner_state]];

             if (p_node[1].remain_depth <
                      DIST(p_node[1].fb.corner_state, p_node[1].fb.edge_state))
                continue;


             p_node[1].twist = twist;
             break;
             }

         if (twist == N_TWIST)
            p_node--;
         else
            {
            p_node++;
            p_node[1].twist = -1;
            }
         }
      }

return;
}


/* ========================================================================= */
   void  calc_sym_cubes(Cube  sym_conj[N_CUBESYM])
/* ------------------------------------------------------------------------- */

{
int                     ii;


cube_init(&sym_conj[0]);
cube_init(&sym_conj[1]);

four_cycle(sym_conj[1].edges, EDGE_UF, EDGE_UL, EDGE_UB, EDGE_UR);
four_cycle(sym_conj[1].edges, EDGE_DF, EDGE_DL, EDGE_DB, EDGE_DR);
four_cycle(sym_conj[1].edges, EDGE_FR, EDGE_LF, EDGE_BL, EDGE_RB);
four_cycle(sym_conj[1].edges, EDGE_FU, EDGE_LU, EDGE_BU, EDGE_RU);
four_cycle(sym_conj[1].edges, EDGE_FD, EDGE_LD, EDGE_BD, EDGE_RD);
four_cycle(sym_conj[1].edges, EDGE_RF, EDGE_FL, EDGE_LB, EDGE_BR);
four_cycle(sym_conj[1].corners, CORNER_UFR, CORNER_ULF, CORNER_UBL, CORNER_URB);
four_cycle(sym_conj[1].corners, CORNER_DRF, CORNER_DFL, CORNER_DLB, CORNER_DBR);
four_cycle(sym_conj[1].corners, CORNER_FRU, CORNER_LFU, CORNER_BLU, CORNER_RBU);
four_cycle(sym_conj[1].corners, CORNER_RFD, CORNER_FLD, CORNER_LBD, CORNER_BRD);
four_cycle(sym_conj[1].corners, CORNER_RUF, CORNER_FUL, CORNER_LUB, CORNER_BUR);
four_cycle(sym_conj[1].corners, CORNER_FDR, CORNER_LDF, CORNER_BDL, CORNER_RDB);

for (ii = 2; ii < 4; ii++)
    cube_compose(&sym_conj[1], &sym_conj[ii - 1], &sym_conj[ii]);

cube_init(&sym_conj[4]);

two_cycle(sym_conj[4].edges, EDGE_UF, EDGE_DF);
two_cycle(sym_conj[4].edges, EDGE_UR, EDGE_DL);
two_cycle(sym_conj[4].edges, EDGE_UB, EDGE_DB);
two_cycle(sym_conj[4].edges, EDGE_UL, EDGE_DR);
two_cycle(sym_conj[4].edges, EDGE_FR, EDGE_FL);
two_cycle(sym_conj[4].edges, EDGE_BR, EDGE_BL);
two_cycle(sym_conj[4].edges, EDGE_FU, EDGE_FD);
two_cycle(sym_conj[4].edges, EDGE_RU, EDGE_LD);
two_cycle(sym_conj[4].edges, EDGE_BU, EDGE_BD);
two_cycle(sym_conj[4].edges, EDGE_LU, EDGE_RD);
two_cycle(sym_conj[4].edges, EDGE_RF, EDGE_LF);
two_cycle(sym_conj[4].edges, EDGE_RB, EDGE_LB);
two_cycle(sym_conj[4].corners, CORNER_UFR, CORNER_DFL);
two_cycle(sym_conj[4].corners, CORNER_ULF, CORNER_DRF);
two_cycle(sym_conj[4].corners, CORNER_UBL, CORNER_DBR);
two_cycle(sym_conj[4].corners, CORNER_URB, CORNER_DLB);
two_cycle(sym_conj[4].corners, CORNER_FRU, CORNER_FLD);
two_cycle(sym_conj[4].corners, CORNER_LFU, CORNER_RFD);
two_cycle(sym_conj[4].corners, CORNER_BLU, CORNER_BRD);
two_cycle(sym_conj[4].corners, CORNER_RBU, CORNER_LBD);
two_cycle(sym_conj[4].corners, CORNER_RUF, CORNER_LDF);
two_cycle(sym_conj[4].corners, CORNER_FUL, CORNER_FDR);
two_cycle(sym_conj[4].corners, CORNER_LUB, CORNER_RDB);
two_cycle(sym_conj[4].corners, CORNER_BUR, CORNER_BDL);

for (ii = 5; ii < 8; ii++)
    cube_compose(&sym_conj[4], &sym_conj[ii - 4], &sym_conj[ii]);

cube_init(&sym_conj[8]);

two_cycle(sym_conj[8].edges, EDGE_UF, EDGE_DF);
two_cycle(sym_conj[8].edges, EDGE_UR, EDGE_DR);
two_cycle(sym_conj[8].edges, EDGE_UB, EDGE_DB);
two_cycle(sym_conj[8].edges, EDGE_UL, EDGE_DL);
two_cycle(sym_conj[8].edges, EDGE_FU, EDGE_FD);
two_cycle(sym_conj[8].edges, EDGE_RU, EDGE_RD);
two_cycle(sym_conj[8].edges, EDGE_BU, EDGE_BD);
two_cycle(sym_conj[8].edges, EDGE_LU, EDGE_LD);
two_cycle(sym_conj[8].corners, CORNER_UFR, CORNER_DRF);
two_cycle(sym_conj[8].corners, CORNER_ULF, CORNER_DFL);
two_cycle(sym_conj[8].corners, CORNER_UBL, CORNER_DLB);
two_cycle(sym_conj[8].corners, CORNER_URB, CORNER_DBR);
two_cycle(sym_conj[8].corners, CORNER_FRU, CORNER_FDR);
two_cycle(sym_conj[8].corners, CORNER_LFU, CORNER_LDF);
two_cycle(sym_conj[8].corners, CORNER_BLU, CORNER_BDL);
two_cycle(sym_conj[8].corners, CORNER_RBU, CORNER_RDB);
two_cycle(sym_conj[8].corners, CORNER_RUF, CORNER_RFD);
two_cycle(sym_conj[8].corners, CORNER_FUL, CORNER_FLD);
two_cycle(sym_conj[8].corners, CORNER_LUB, CORNER_LBD);
two_cycle(sym_conj[8].corners, CORNER_BUR, CORNER_BRD);

for (ii = 9; ii < 16; ii++)
    cube_compose(&sym_conj[8], &sym_conj[ii - 8], &sym_conj[ii]);

calc_cube_urf(&sym_conj[16]);

for (ii = 17; ii < 48; ii++)
    cube_compose(&sym_conj[16], &sym_conj[ii - 16], &sym_conj[ii]);

return;
}


/* ========================================================================= */
   void  pretty_print_unsigned_int(unsigned int  nn)
/* ------------------------------------------------------------------------- */

{
int                     digits[4], ii, started;


for (ii = 0; ii < 4; ii++)
    {
    digits[ii] = nn % 1000;
    nn /= 1000;
    }

started = 0;

for (ii = 3; ii >= 0; ii--)
    {
    if (started)
       {
       if (digits[ii] >= 100)
          printf("%3d", digits[ii]);
       else if (digits[ii] >= 10)
               printf("0%2d", digits[ii]);
       else
          printf("00%1d", digits[ii]);
       }
    else
       {
       if (digits[ii] >= 100)
          {
          printf("%3d", digits[ii]);
          started = 1;
          }
       else if (digits[ii] >= 10)
               {
               printf(" %2d", digits[ii]);
               started = 1;
               }
       else if ((digits[ii] >= 1) || (ii == 0))
               {
               printf("  %1d", digits[ii]);
               started = 1;
               }
       else
          printf("   ");
       }

    if (ii > 0)
       printf("%c", started ? ',' : ' ');
    }

return;
}


/* ========================================================================= */
   void  solve_cube(Cube  *p_cube)
/* ------------------------------------------------------------------------- */

{
static Cube             sym_cubes[N_CUBESYM];
static int              subgroup_list[N_SYMSUBGRP][N_CUBESYM];
static int              initialized = 0;
Full_cube               full_cube_struct;
Search_node             node_arr[MAX_TWISTS];
int                     ii, start_depth, search_limit;


if (initialized == 0)
   {
   calc_sym_cubes(sym_cubes);
   calc_subgroup_list(subgroup_list);
   initialized = 1;
   }

print_cube(p_cube);
if (cube_is_solved(p_cube))
   {
   printf("cube is already solved!\n");
   return;
   }

cube_conjugate(p_cube, &sym_cubes[0], &full_cube_struct.cubies);
process_full_cube(&full_cube_struct);

set_cube_symmetry(&full_cube_struct, sym_cubes, subgroup_list);

node_arr[0].follow_type = 1 + full_cube_struct.sym_subgrp;
node_arr[0].ud.corner_state = full_cube_struct.ud.corner_state;
node_arr[0].ud.edge_state = full_cube_struct.ud.edge_state;
node_arr[0].ud.sym_state = full_cube_struct.ud.sym_state;

node_arr[0].rl.corner_state = full_cube_struct.rl.corner_state;
node_arr[0].rl.edge_state = full_cube_struct.rl.edge_state;
node_arr[0].rl.sym_state = full_cube_struct.rl.sym_state;

node_arr[0].fb.corner_state = full_cube_struct.fb.corner_state;
node_arr[0].fb.edge_state = full_cube_struct.fb.edge_state;
node_arr[0].fb.sym_state = full_cube_struct.fb.sym_state;

sol_found = 0;
if ((p_current_metric->metric == QUARTER_TURN_METRIC) &&
    (full_cube_struct.parity == 0))
   start_depth = 2;
else
   start_depth = 1;

search_limit = p_current_options->search_limit;
if ((search_limit <= 0) || (search_limit >= MAX_TWISTS))
   search_limit = MAX_TWISTS - 1;

for (ii = start_depth; ii <= search_limit; ii += p_current_metric->increment)
    {
    n_nodes = (long long int)0;
    n_tests = (unsigned int)0;
    node_arr[0].remain_depth = ii;
    node_arr[1].twist = -1;
    search_tree(&full_cube_struct, node_arr);

    if ((p_current_options->one_solution_only == 0) || (sol_found == 0))
       {
       printf("depth %2d%c completed  (", ii, p_current_metric->metric_char);
       pretty_print_unsigned_int(n_nodes);
       printf(" nodes, ");
       pretty_print_unsigned_int(n_tests);
       printf(" tests)\n");
       fflush(stdout);
       }

    if (sol_found)
       break;
    }

return;
}


/* ========================================================================= */
   int  main(void)
/* ------------------------------------------------------------------------- */

{
Metric_data             metric_data;
Options                 user_options;
Cube                    cube_struct;
int                     stat;


init_options(&metric_data, &user_options);
init_globals();

signal(SIGINT, SIG_IGN);

while (1)
      {
      stat = user_enters_cube(&cube_struct);
      if (stat < 0)
         break;

      if (stat == 0)
         {
         if (sigsetjmp(jump_env, 1) == 0)
            {
            signal(SIGINT, user_interrupt);
            solve_cube(&cube_struct);
            }

         signal(SIGINT, SIG_IGN);
         }
      }

exit(EXIT_SUCCESS);

return 0;  /*  haha  */
}