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 | } |
---|