Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

optimal.c @ 2739
Tweet

Last change on this file since 2739 was 2739, checked in by kali, 14 years ago

introduce Michael Reid's optimal solver code in its original state

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

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

adding cube orientation to the cube structure

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

F R U B L D UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR

File size: 130.0 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

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

Download in other formats:

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