aboutsummaryrefslogtreecommitdiff
path: root/src/solver.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/solver.c1058
1 files changed, 0 insertions, 1058 deletions
diff --git a/src/solver.c b/src/solver.c
deleted file mode 100644
index 48e845f..0000000
--- a/src/solver.c
+++ /dev/null
@@ -1,1058 +0,0 @@
1#include <stdint.h>
2#include <stdio.h>
3
4#include "utils.h"
5#include "coordinates.h"
6#include "moves.h"
7#include "io.h"
8#include "pruning_tables.h"
9
10/* Applies inverse of moves, inverse of prev_moves and then inverse of scramble
11 * and returns a coordinate determined by t_table. */
12int premoves_inverse(int moves[30], int scramble[], int prev_moves[30],
13 int t_table[][19]) {
14 int nprevmoves, nmoves, nscramble, coord = 0;
15
16 for (nmoves = 0; moves[nmoves]; nmoves++);
17 for (nprevmoves = 0; prev_moves[nprevmoves]; nprevmoves++);
18 for (nscramble = 0; scramble[nscramble]; nscramble++);
19
20 for (int i = nmoves - 1; i >= 0; i--)
21 coord = t_table[coord][inverse_move[moves[i]]];
22 for (int i = nprevmoves - 1; i >= 0; i--)
23 coord = t_table[coord][inverse_move[prev_moves[i]]];
24 for (int i = nscramble - 1; i >= 0; i--)
25 coord = t_table[coord][inverse_move[scramble[i]]];
26
27 return coord;
28}
29
30
31/******/
32/* EO */
33/******/
34void niss_eo_dfs(int eo, int scramble[], int eo_list[][30], int *eo_count,
35 int t_table[pow2to11][19], int p_table[pow2to11],
36 int last1, int last2, int moves, int m, int d, int niss,
37 int can_use_niss, int hide) {
38
39
40 if (*eo_count >= m || moves > d ||
41 ((!can_use_niss || niss) && moves + p_table[eo] > d))
42 return;
43
44 eo_list[*eo_count][moves] = 0;
45
46 if (eo == 0) {
47 /* If an early EO is found, or if "case F2 B", or if hide is on. */
48 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
49 (hide && moves > 0 &&
50 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
51 return;
52 /* Copy moves for the next solution */
53 if (*eo_count < m - 1)
54 copy_moves(eo_list[*eo_count], eo_list[(*eo_count)+1]);
55 (*eo_count)++;
56 return;
57 }
58
59 for (int i = 1; i < 19; i++) {
60 if (possible_next[last1][last2] & (1 << i)) {
61 eo_list[*eo_count][moves] = niss ? -i : i;
62 niss_eo_dfs(t_table[eo][i], scramble, eo_list, eo_count, t_table,
63 p_table, i, last1, moves+1, m, d, niss,
64 can_use_niss, hide);
65 }
66 }
67
68 if (*eo_count >= m)
69 return;
70 eo_list[*eo_count][moves] = 0;
71
72 /* If not nissing already and we either have not done any move yet or
73 * the last move was F/F' etc, and if I am allowed to niss, try niss! */
74 if (!niss && (last1 == 0 || t_table[0][last1] != 0) && can_use_niss &&
75 !(hide && moves > 0 &&
76 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0)))) {
77 int aux[] = {0,0};
78 niss_eo_dfs(premoves_inverse(eo_list[*eo_count], scramble, aux, t_table),
79 scramble, eo_list, eo_count, t_table, p_table,
80 0, 0, moves, m, d, 1, can_use_niss, hide);
81 }
82}
83
84int eo_scram_spam(int scram[], int eo_list[][30], int fb, int rl, int ud,
85 int m, int b, int niss, int h) {
86
87 init_small_pruning_tables();
88
89 int n = 0, eofb = 0, eorl = 0, eoud = 0;
90 for (int i = 0; scram[i]; i++) {
91 eofb = eofb_transition_table[eofb][scram[i]];
92 eorl = eorl_transition_table[eorl][scram[i]];
93 eoud = eoud_transition_table[eoud][scram[i]];
94 }
95 for (int i = 0; i <= b; i++) {
96 if (fb)
97 niss_eo_dfs(eofb, scram, eo_list, &n, eofb_transition_table,
98 eofb_pruning_table, 0, 0, 0, m, i, 0, niss, h);
99 if (rl)
100 niss_eo_dfs(eorl, scram, eo_list, &n, eorl_transition_table,
101 eorl_pruning_table, 0, 0, 0, m, i, 0, niss, h);
102 if (ud)
103 niss_eo_dfs(eoud, scram, eo_list, &n, eoud_transition_table,
104 eoud_pruning_table, 0, 0, 0, m, i, 0, niss, h);
105 }
106 return n;
107}
108
109
110/******/
111/* CO */
112/******/
113void niss_co_dfs(int co, int scramble[], int co_list[][30], int *co_count,
114 int t_table[pow3to7][19], int p_table[pow3to7],
115 int last1, int last2, int moves, int m, int d, int niss,
116 int can_use_niss, int hide, int ignore) {
117
118
119 if (*co_count >= m || moves > d ||
120 ((!can_use_niss || niss) && ((!ignore && moves + p_table[co] > d) ||
121 ( ignore && moves + p_table[co] - 2 > d))))
122 return;
123
124 co_list[*co_count][moves] = 0;
125
126 if (co == 0 || (ignore && ( t_table[t_table[co][F]][B] == 0 ||
127 t_table[t_table[co][R]][L] == 0 ||
128 t_table[t_table[co][U]][D] == 0 ))) {
129 /* If an early CO is found, or if "case F2 B", or if hide is on. */
130 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
131 (hide && moves > 0 &&
132 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
133 return;
134 /* Copy moves for the next solution */
135 if (*co_count < m - 1)
136 copy_moves(co_list[*co_count], co_list[(*co_count)+1]);
137 (*co_count)++;
138 return;
139 }
140
141 for (int i = 1; i < 19; i++) {
142 if (possible_next[last1][last2] & (1 << i)) {
143 co_list[*co_count][moves] = niss ? -i : i;
144 niss_co_dfs(t_table[co][i], scramble, co_list, co_count, t_table,
145 p_table, i, last1, moves+1, m, d, niss,
146 can_use_niss, hide, ignore);
147 }
148 }
149
150 if (*co_count >= m)
151 return;
152 co_list[*co_count][moves] = 0;
153
154 /* If not nissing already and we either have not done any move yet or
155 * the last move was F/F' etc, and if I am allowed to niss, try niss! */
156 if (!niss && (last1 == 0 || t_table[0][last1] != 0) && can_use_niss &&
157 !(hide && moves > 0 &&
158 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0)))) {
159 int aux[] = {0,0};
160 niss_co_dfs(premoves_inverse(co_list[*co_count], scramble, aux, t_table),
161 scramble, co_list, co_count, t_table, p_table,
162 0, 0, moves, m, d, 1, can_use_niss, hide, ignore);
163 }
164}
165
166int co_scram_spam(int scram[], int co_list[][30], int fb, int rl, int ud,
167 int m, int b, int niss, int h, int ignore) {
168
169 init_small_pruning_tables();
170
171 int n = 0, cofb = 0, corl = 0, coud = 0;
172 for (int i = 0; scram[i]; i++) {
173 cofb = cofb_transition_table[cofb][scram[i]];
174 corl = corl_transition_table[corl][scram[i]];
175 coud = coud_transition_table[coud][scram[i]];
176 }
177 for (int i = 0; i <= b; i++) {
178 if (fb)
179 niss_co_dfs(cofb, scram, co_list, &n, cofb_transition_table,
180 cofb_pruning_table, 0, 0, 0, m, i, 0, niss, h, ignore);
181 if (rl)
182 niss_co_dfs(corl, scram, co_list, &n, corl_transition_table,
183 corl_pruning_table, 0, 0, 0, m, i, 0, niss, h, ignore);
184 if (ud)
185 niss_co_dfs(coud, scram, co_list, &n, coud_transition_table,
186 coud_pruning_table, 0, 0, 0, m, i, 0, niss, h, ignore);
187 }
188 return n;
189}
190
191
192/**************/
193/* DR from EO */
194/**************/
195
196
197/* Scramble includes premoves for previous EO */
198void niss_dr_from_eo_dfs(int co, int epos, int scramble[], int eo_moves[30],
199 int dr_list[][30], int *dr_count,
200 int co_t_table[pow3to7][19],
201 int epos_t_table[binom12on4][19],
202 int8_t p_table[pow3to7][binom12on4], int mask,
203 int last1, int last2, int last1_inv, int last2_inv,
204 int moves, int m, int d, int niss,
205 int can_use_niss, int hide) {
206
207 if (*dr_count >= m || moves > d ||
208 ((!can_use_niss || niss) && moves + p_table[co][epos] > d))
209 return;
210
211 dr_list[*dr_count][moves] = 0;
212
213 if (co == 0 && epos == 0) {
214 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
215 (hide && moves > 0 &&
216 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
217 return;
218 /* Copy moves for the next solution */
219 if (*dr_count < m - 1)
220 copy_moves(dr_list[*dr_count], dr_list[(*dr_count)+1]);
221 (*dr_count)++;
222 return;
223 }
224
225 for (int i = 1; i < 19; i++) {
226 if (possible_next[last1][last2] & (1 << i) & mask) {
227 dr_list[*dr_count][moves] = niss ? -i : i;
228 niss_dr_from_eo_dfs(co_t_table[co][i], epos_t_table[epos][i],
229 scramble, eo_moves, dr_list, dr_count,
230 co_t_table, epos_t_table, p_table, mask,
231 i, last1, last1_inv, last2_inv,
232 moves+1, m, d, niss, can_use_niss, hide);
233 }
234 }
235
236 if (*dr_count >= m)
237 return;
238 dr_list[*dr_count][moves] = 0;
239
240 /* If not nissing already and we either have not done any move yet or
241 * the last move was F/F' etc and I am allowed to niss, try niss! */
242 if (!niss && (last1 == 0 || co_t_table[0][last1] != 0) && can_use_niss &&
243 !(hide && moves > 0 &&
244 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
245 niss_dr_from_eo_dfs(premoves_inverse(dr_list[*dr_count], scramble,
246 eo_moves, co_t_table),
247 premoves_inverse(dr_list[*dr_count], scramble,
248 eo_moves, epos_t_table),
249 scramble, eo_moves, dr_list, dr_count,
250 co_t_table, epos_t_table, p_table,
251 mask, last1_inv, last2_inv, 0, 0,
252 moves, m, d, 1, can_use_niss, hide);
253}
254
255int drfrom_scram_spam(int scram[], int dr_list[][30], int from, int fb,
256 int rl, int ud, int m, int b, int niss, int hide) {
257
258 init_drfromeo_pruning_tables();
259
260 int n = 0;
261 int eofb = 0, eorl = 0, eoud = 0;
262 int epose = 0, eposm = 0, eposs = 0;
263 int coud = 0, corl = 0, cofb = 0;
264
265 for (int i = 0; scram[i]; i++) {
266 eofb = eofb_transition_table[eofb][scram[i]];
267 eorl = eorl_transition_table[eorl][scram[i]];
268 eoud = eoud_transition_table[eoud][scram[i]];
269
270 cofb = cofb_transition_table[cofb][scram[i]];
271 corl = corl_transition_table[corl][scram[i]];
272 coud = coud_transition_table[coud][scram[i]];
273
274 epose = epose_transition_table[epose][scram[i]];
275 eposm = eposm_transition_table[eposm][scram[i]];
276 eposs = eposs_transition_table[eposs][scram[i]];
277 }
278
279 int fake_eom[2] = {0, 0}; /* Fake EO moves */
280
281 if (from == 1) {
282 if (eofb)
283 return -1;
284 for (int i = 0; i <= b; i++) {
285 if (ud)
286 niss_dr_from_eo_dfs(coud, epose, scram, fake_eom, dr_list, &n,
287 coud_transition_table, epose_transition_table,
288 coud_epose_from_eofb_pruning_table, move_mask_eofb,
289 0, 0, 0, 0, 0, m, i, 0, niss, hide);
290 if (rl)
291 niss_dr_from_eo_dfs(corl, eposm, scram, fake_eom, dr_list, &n,
292 corl_transition_table, eposm_transition_table,
293 corl_eposm_from_eofb_pruning_table, move_mask_eofb,
294 0, 0, 0, 0, 0, m, i, 0, niss, hide);
295 }
296 } else if (from == 2) {
297 if (eorl)
298 return -1;
299 for (int i = 0; i <= b; i++) {
300 if (fb)
301 niss_dr_from_eo_dfs(cofb, eposs, scram, fake_eom, dr_list, &n,
302 cofb_transition_table, eposs_transition_table,
303 cofb_eposs_from_eorl_pruning_table, move_mask_eorl,
304 0, 0, 0, 0, 0, m, i, 0, niss, hide);
305 if (ud)
306 niss_dr_from_eo_dfs(coud, epose, scram, fake_eom, dr_list, &n,
307 coud_transition_table, epose_transition_table,
308 coud_epose_from_eorl_pruning_table, move_mask_eorl,
309 0, 0, 0, 0, 0, m, i, 0, niss, hide);
310 }
311 } else if (from == 3) {
312 if (eoud)
313 return -1;
314 for (int i = 0; i <= b; i++) {
315 if (rl)
316 niss_dr_from_eo_dfs(corl, eposm, scram, fake_eom, dr_list, &n,
317 corl_transition_table, eposm_transition_table,
318 corl_eposm_from_eoud_pruning_table, move_mask_eoud,
319 0, 0, 0, 0, 0, m, i, 0, niss, hide);
320 if (fb)
321 niss_dr_from_eo_dfs(cofb, eposs, scram, fake_eom, dr_list, &n,
322 cofb_transition_table, eposs_transition_table,
323 cofb_eposs_from_eoud_pruning_table, move_mask_eoud,
324 0, 0, 0, 0, 0, m, i, 0, niss, hide);
325 }
326 } else {
327 return -1;
328 }
329 return n;
330}
331
332
333/***************/
334/* HTR from DR */
335/***************/
336
337/* Scramble includes premoves for previous DR */
338void niss_htr_from_dr_dfs(int cp, int eo3, int scramble[], int eodr_moves[30],
339 int htr_list[][30], int *htr_count,
340 int eo3_t_table[pow2to11][19],
341 int cp_to_htr_pruning_table[factorial8],
342 int cp_htr_pruning_table[factorial8],
343 int cp_finish_pruning_table[factorial8],
344 int mask, int last1, int last2,
345 int last1_inv, int last2_inv, int moves,
346 int m, int d, int niss,
347 int can_use_niss, int hide) {
348
349 if (*htr_count >= m || moves > d ||
350 ((!can_use_niss || niss) && moves + cp_to_htr_pruning_table[cp] > d) ||
351 moves + cp_finish_pruning_table[cp] - 4 > d)
352 return;
353
354 htr_list[*htr_count][moves] = 0;
355
356 if ((cp == 0 || cp_htr_pruning_table[cp]) && eo3 == 0) {
357 if (moves != d || (parallel(last1, last2) && last2 % 3 == 2) ||
358 (hide && moves > 0 &&
359 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
360 return;
361 /* Copy moves for the next solution */
362 if (*htr_count < m - 1)
363 copy_moves(htr_list[*htr_count], htr_list[(*htr_count)+1]);
364 (*htr_count)++;
365 return;
366 }
367
368 for (int i = 1; i < 19; i++) {
369 if (possible_next[last1][last2] & (1 << i) & mask) {
370 htr_list[*htr_count][moves] = niss ? -i : i;
371 niss_htr_from_dr_dfs(cp_transition_table[cp][i], eo3_t_table[eo3][i],
372 scramble, eodr_moves, htr_list, htr_count,
373 eo3_t_table, cp_to_htr_pruning_table,
374 cp_htr_pruning_table, cp_finish_pruning_table,
375 mask, i, last1, last1_inv, last2_inv,
376 moves+1, m, d, niss, can_use_niss, hide);
377 }
378 }
379
380 if (*htr_count >= m)
381 return;
382 htr_list[*htr_count][moves] = 0;
383
384 /* If not nissing already and we either have not done any move yet or
385 * the last move was a quarter turn and I am allowed to niss, try niss! */
386 if (!niss && last1 % 3 != 2 && can_use_niss &&
387 !(hide && moves > 0 &&
388 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
389 niss_htr_from_dr_dfs(premoves_inverse(htr_list[*htr_count], scramble,
390 eodr_moves, cp_transition_table),
391 premoves_inverse(htr_list[*htr_count], scramble,
392 eodr_moves, eo3_t_table),
393 scramble, eodr_moves, htr_list, htr_count,
394 eo3_t_table, cp_to_htr_pruning_table,
395 cp_htr_pruning_table, cp_finish_pruning_table,
396 mask, last1_inv, last2_inv,
397 0, 0, moves, m, d, 1, can_use_niss, hide);
398}
399
400int htr_scram_spam(int scram[], int htr_list[][30], int from,
401 int m, int b, int niss, int hide) {
402
403 init_small_pruning_tables();
404
405 int n = 0;
406 int eofb = 0, eorl = 0, eoud = 0;
407 int coud = 0, corl = 0, cofb = 0;
408 int cp = 0;
409
410 for (int i = 0; scram[i]; i++) {
411 eofb = eofb_transition_table[eofb][scram[i]];
412 eorl = eorl_transition_table[eorl][scram[i]];
413 eoud = eoud_transition_table[eoud][scram[i]];
414
415 cofb = cofb_transition_table[cofb][scram[i]];
416 corl = corl_transition_table[corl][scram[i]];
417 coud = coud_transition_table[coud][scram[i]];
418
419 cp = cp_transition_table[cp][scram[i]];
420 }
421
422 int fake_drm[2] = {0, 0}; /* Fake DR moves */
423
424 if ((from == 1 || from == 0) && (!eofb && !eorl && !coud)) {
425 for (int i = 0; i <= b; i++) {
426 niss_htr_from_dr_dfs(cp, eoud, scram, fake_drm, htr_list, &n,
427 eoud_transition_table, cpud_to_htr_pruning_table,
428 cp_htr_pruning_table, cp_drud_pruning_table,
429 move_mask_drud, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
430 }
431 } else if ((from == 2 || from == 0) && (!eorl && !eoud && !cofb)) {
432 for (int i = 0; i <= b; i++) {
433 niss_htr_from_dr_dfs(cp, eofb, scram, fake_drm, htr_list, &n,
434 eofb_transition_table, cpfb_to_htr_pruning_table,
435 cp_htr_pruning_table, cp_drfb_pruning_table,
436 move_mask_drfb, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
437 }
438 } else if ((from == 3 || from == 0) && (!eoud && !eofb && !corl)) {
439 for (int i = 0; i <= b; i++) {
440 niss_htr_from_dr_dfs(cp, eorl, scram, fake_drm, htr_list, &n,
441 eorl_transition_table, cprl_to_htr_pruning_table,
442 cp_htr_pruning_table, cp_drrl_pruning_table,
443 move_mask_drrl, 0, 0, 0, 0, 0, m, i, 0, niss, hide);
444 }
445 } else {
446 return -1;
447 }
448 return n;
449}
450
451
452/***********************/
453/* Direct DR (no NISS) */
454/***********************/
455void dr_dfs(int eo, int eo2, int eslice, int co,
456 int dr_list[][30], int *dr_count,
457 int eo_t_table[pow2to11][19], int eo2_t_table[pow2to11][19],
458 int eslice_t_table[binom12on4][19], int co_t_table[pow3to7][19],
459 int8_t eo_eslice_p_table[pow2to11][binom12on4],
460 int8_t eo_co_p_table[pow2to11][pow3to7],
461 int8_t eo2_co_p_table[pow2to11][pow3to7],
462 int last1, int last2, int moves, int max_sol,
463 int depth, int hide) {
464 if (*dr_count >= max_sol || moves + eo_eslice_p_table[eo][eslice] > depth ||
465 moves + eo_co_p_table[eo][co] > depth ||
466 moves + eo2_co_p_table[eo2][co] > depth)
467 return;
468
469 dr_list[*dr_count][moves] = 0;
470
471 if (eo == 0 && eslice == 0 && co == 0) {
472 /* If an early DR is found, or if "case R2 L". */
473 if (moves != depth || (parallel(last1, last2) && last2 % 3 == 2) ||
474 (hide && moves > 0 &&
475 (last1 % 3 == 0 || (parallel(last1, last2) && last2 % 3 == 0))))
476 return;
477 /* Copy moves for the next solution */
478 if (*dr_count < max_sol - 1)
479 copy_moves(dr_list[*dr_count], dr_list[(*dr_count)+1]);
480 (*dr_count)++;
481 return;
482 }
483
484 for (int i = 1; i < 19; i++) {
485 if (possible_next[last1][last2] & (1 << i)) {
486 dr_list[*dr_count][moves] = i;
487 dr_dfs(eo_t_table[eo][i], eo2_t_table[eo2][i],
488 eslice_t_table[eslice][i], co_t_table[co][i],
489 dr_list, dr_count,
490 eo_t_table, eo2_t_table, eslice_t_table, co_t_table,
491 eo_eslice_p_table, eo_co_p_table, eo2_co_p_table,
492 i, last1, moves+1, max_sol, depth, hide);
493 }
494 }
495}
496
497int dr_scram_spam(int scram[], int dr_list[][30], int fb, int rl, int ud,
498 int m, int b, int h) {
499
500 init_directdr_pruning_tables();
501
502 int n = 0;
503 int eofb = 0, eorl = 0, eoud = 0;
504 int epose = 0, eposm = 0, eposs = 0;
505 int coud = 0, corl = 0, cofb = 0;
506
507 for (int i = 0; scram[i]; i++) {
508 eofb = eofb_transition_table[eofb][scram[i]];
509 eorl = eorl_transition_table[eorl][scram[i]];
510 eoud = eoud_transition_table[eoud][scram[i]];
511
512 cofb = cofb_transition_table[cofb][scram[i]];
513 corl = corl_transition_table[corl][scram[i]];
514 coud = coud_transition_table[coud][scram[i]];
515
516 epose = epose_transition_table[epose][scram[i]];
517 eposm = eposm_transition_table[eposm][scram[i]];
518 eposs = eposs_transition_table[eposs][scram[i]];
519 }
520
521 for (int i = 0; i <= b; i++) {
522 if (ud)
523 dr_dfs(eofb, eorl, epose, coud, dr_list, &n,
524 eofb_transition_table, eorl_transition_table,
525 epose_transition_table, coud_transition_table,
526 eofb_epose_pruning_table, eofb_coud_pruning_table,
527 eorl_coud_pruning_table, 0, 0, 0, m, i, h);
528 if (fb)
529 dr_dfs(eorl, eoud, eposs, cofb, dr_list, &n,
530 eorl_transition_table, eoud_transition_table,
531 eposs_transition_table, cofb_transition_table,
532 eorl_eposs_pruning_table, eorl_cofb_pruning_table,
533 eoud_cofb_pruning_table, 0, 0, 0, m, i, h);
534 if (rl)
535 dr_dfs(eoud, eofb, eposm, corl, dr_list, &n,
536 eoud_transition_table, eofb_transition_table,
537 eposm_transition_table, corl_transition_table,
538 eoud_eposm_pruning_table, eoud_corl_pruning_table,
539 eofb_corl_pruning_table, 0, 0, 0, m, i, h);
540 }
541 return n;
542}
543
544
545/*************/
546/* DR finish */
547/*************/
548void dr_finish_dfs(int cp, int ep8, int ep4, int sol[][30], int *sol_count,
549 int ep8_t_table[factorial8][19],
550 int ep4_t_table[factorial4][19],
551 int cp_p_table[factorial8],
552 int ep8_p_table[factorial8],
553 int mask, int last1, int last2, int moves, int m, int d) {
554
555
556 if (*sol_count >= m || moves + cp_p_table[cp] > d ||
557 moves + ep8_p_table[ep8] > d)
558 return;
559
560 sol[*sol_count][moves] = 0;
561
562 if (cp == 0 && ep8 == 0 && ep4 == 0) {
563 if (moves != d)
564 return;
565 /* Copy moves for the next solution */
566 if (*sol_count < m - 1)
567 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
568 (*sol_count)++;
569 return;
570 }
571
572 for (int i = 1; i < 19; i++) {
573 if (possible_next[last1][last2] & (1 << i) & mask) {
574 sol[*sol_count][moves] = i;
575 dr_finish_dfs(cp_transition_table[cp][i], ep8_t_table[ep8][i],
576 ep4_t_table[ep4][i], sol, sol_count,
577 ep8_t_table, ep4_t_table,
578 cp_p_table, ep8_p_table,
579 mask, i, last1, moves+1, m, d);
580 }
581 }
582
583 return;
584}
585
586int dr_finish_scram_spam(int scram[], int sol[][30], int from, int m, int b) {
587
588 init_small_pruning_tables();
589
590 int n = 0;
591 int eofb = 0, eorl = 0, eoud = 0;
592 int coud = 0, corl = 0, cofb = 0;
593 int cp = 0;
594 int ep[12];
595 ep_int_to_array(0, ep);
596
597 for (int i = 0; scram[i]; i++) {
598 eofb = eofb_transition_table[eofb][scram[i]];
599 eorl = eorl_transition_table[eorl][scram[i]];
600 eoud = eoud_transition_table[eoud][scram[i]];
601
602 cofb = cofb_transition_table[cofb][scram[i]];
603 corl = corl_transition_table[corl][scram[i]];
604 coud = coud_transition_table[coud][scram[i]];
605
606 cp = cp_transition_table[cp][scram[i]];
607 apply_move_ep_array(scram[i], ep);
608 }
609
610 if ((from == 1 && (eofb || eorl || coud)) ||
611 (from == 2 && (eorl || eoud || cofb)) ||
612 (from == 3 && (eoud || eofb || corl)) ||
613 ((eofb || eorl || coud) && (eorl || eoud ||cofb) && (eoud ||eofb || corl)))
614 return -1;
615
616 for (int i = 0; i <= b; i++) {
617 if ((from == 1 || from == 0) && (!eofb && !eorl && !coud))
618 dr_finish_dfs(cp, epud_array_to_int(ep), epe_array_to_int(ep),
619 sol, &n, epud_transition_table, epe_transition_table,
620 cp_drud_pruning_table, epud_pruning_table,
621 move_mask_drud, 0, 0, 0, m, i);
622 if ((from == 2 || from == 0) && (!eorl && !eoud && !cofb))
623 dr_finish_dfs(cp, epfb_array_to_int(ep), eps_array_to_int(ep),
624 sol, &n, epfb_transition_table, eps_transition_table,
625 cp_drfb_pruning_table, epfb_pruning_table,
626 move_mask_drfb, 0, 0, 0, m, i);
627 if ((from == 3 || from == 0) && (!eoud && !eofb && !corl))
628 dr_finish_dfs(cp, eprl_array_to_int(ep), epm_array_to_int(ep),
629 sol, &n, eprl_transition_table, epm_transition_table,
630 cp_drrl_pruning_table, eprl_pruning_table,
631 move_mask_drrl, 0, 0, 0, m, i);
632 }
633
634 return n;
635}
636
637int htr_finish_scram_spam(int scram[], int sol[][30], int m, int b) {
638
639 init_small_pruning_tables();
640
641 int n = 0;
642 int eofb = 0, eorl = 0, eoud = 0;
643 int coud = 0, cp = 0;
644 int ep[12];
645 ep_int_to_array(0, ep);
646
647 for (int i = 0; scram[i]; i++) {
648 eofb = eofb_transition_table[eofb][scram[i]];
649 eorl = eorl_transition_table[eorl][scram[i]];
650 eoud = eoud_transition_table[eoud][scram[i]];
651
652 coud = coud_transition_table[coud][scram[i]];
653
654 cp = cp_transition_table[cp][scram[i]];
655 apply_move_ep_array(scram[i], ep);
656 }
657
658 if (eofb || eorl || eoud || coud || cpud_to_htr_pruning_table[cp] != 0)
659 return -1;
660
661 for (int i = 0; i <= b; i++)
662 dr_finish_dfs(cp, epud_array_to_int(ep), epe_array_to_int(ep),
663 sol, &n, epud_transition_table, epe_transition_table,
664 cp_drud_pruning_table, epud_pruning_table,
665 move_mask_htr, 0, 0, 0, m, i);
666
667 return n;
668}
669
670
671/**************/
672/* DR corners */
673/**************/
674void dr_corners_dfs(int cp, int sol[][30], int *sol_count,
675 int cp_p_table[factorial8], int mask, int last1, int last2,
676 int moves, int m, int d, int ignore) {
677
678 if (*sol_count >= m || (!ignore && moves + cp_p_table[cp] > d) ||
679 (ignore && moves + cp_p_table[cp] - 2 > d))
680 return;
681
682
683 sol[*sol_count][moves] = 0;
684
685 if (cp == 0 ||
686 (ignore && mask == move_mask_drud &&
687 (cp_transition_table[cp_transition_table[cp][U]][D3] == 0 ||
688 cp_transition_table[cp_transition_table[cp][U2]][D2] == 0 ||
689 cp_transition_table[cp_transition_table[cp][U3]][D] == 0 )) ||
690 (ignore && mask == move_mask_drfb &&
691 (cp_transition_table[cp_transition_table[cp][F]][B3] == 0 ||
692 cp_transition_table[cp_transition_table[cp][F2]][B2] == 0 ||
693 cp_transition_table[cp_transition_table[cp][F3]][B] == 0 )) ||
694 (ignore && mask == move_mask_drrl &&
695 (cp_transition_table[cp_transition_table[cp][R]][L3] == 0 ||
696 cp_transition_table[cp_transition_table[cp][R2]][L2] == 0 ||
697 cp_transition_table[cp_transition_table[cp][R3]][L] == 0 ))
698 ) {
699 if (moves != d)
700 return;
701 /* Copy moves for the next solution */
702 if (*sol_count < m - 1)
703 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
704 (*sol_count)++;
705 return;
706 }
707
708 for (int i = 1; i < 19; i++) {
709 if (possible_next[last1][last2] & (1 << i) & mask) {
710 sol[*sol_count][moves] = i;
711 dr_corners_dfs(cp_transition_table[cp][i], sol, sol_count,
712 cp_p_table, mask, i, last1, moves+1, m, d, ignore);
713 }
714 }
715}
716
717int dr_corners_scram_spam(int scram[], int sol[][30], int from, int m, int b,
718 int ignore) {
719
720 init_small_pruning_tables();
721
722 int n = 0;
723 int eofb = 0, eorl = 0, eoud = 0;
724 int coud = 0, corl = 0, cofb = 0;
725 int cp = 0;
726
727 for (int i = 0; scram[i]; i++) {
728 eofb = eofb_transition_table[eofb][scram[i]];
729 eorl = eorl_transition_table[eorl][scram[i]];
730 eoud = eoud_transition_table[eoud][scram[i]];
731
732 cofb = cofb_transition_table[cofb][scram[i]];
733 corl = corl_transition_table[corl][scram[i]];
734 coud = coud_transition_table[coud][scram[i]];
735
736 cp = cp_transition_table[cp][scram[i]];
737 }
738
739 if ((from == 1 && coud) || (from == 2 && cofb) || (from == 3 && corl) ||
740 (coud && cofb && corl))
741 return -1;
742
743 for (int i = 0; i <= b; i++) {
744 if ((from == 1 || from == 0) && !coud)
745 dr_corners_dfs(cp, sol, &n, cp_drud_pruning_table, move_mask_drud,
746 0, 0, 0, m, i, ignore);
747 if ((from == 2 || from == 0) && !cofb)
748 dr_corners_dfs(cp, sol, &n, cp_drfb_pruning_table, move_mask_drfb,
749 0, 0, 0, m, i, ignore);
750 if ((from == 3 || from == 0) && !corl)
751 dr_corners_dfs(cp, sol, &n, cp_drrl_pruning_table, move_mask_drrl,
752 0, 0, 0, m, i, ignore);
753 }
754
755 return n;
756}
757
758/***************/
759/* Full solver */
760/***************/
761
762int is_ep_solved(int ep, int moves[30]) {
763 int ep_arr[12];
764 ep_int_to_array(ep, ep_arr);
765 for (int i = 0; moves[i]; i++)
766 apply_move_ep_array(moves[i], ep_arr);
767 return !ep_array_to_int(ep_arr);
768}
769
770/* Solves directly using only small tables. Suitable for short solutions. */
771void small_optimal_dfs(int eofb, int eorl, int eoud, int ep,
772 int coud, int cofb, int corl, int cp,
773 int sol[][30], int *sol_count, int last1, int last2,
774 int moves, int m, int d) {
775 if (moves + eofb_pruning_table[eofb] > d ||
776 moves + eorl_pruning_table[eorl] > d ||
777 moves + eoud_pruning_table[eoud] > d ||
778 moves + coud_pruning_table[coud] > d ||
779 moves + cofb_pruning_table[cofb] > d ||
780 moves + corl_pruning_table[corl] > d ||
781 moves + cp_pruning_table[cp] > d ||
782 *sol_count >= m)
783 return;
784
785 sol[*sol_count][moves] = 0;
786
787 if (eofb == 0 && coud == 0 && cp == 0) {
788 if (is_ep_solved(ep, sol[*sol_count])) {
789 if (moves != d)
790 return;
791 if (*sol_count < m - 1)
792 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
793 (*sol_count)++;
794 return;
795 }
796 }
797
798 for (int i = 1; i < 19; i++) {
799 if (possible_next[last1][last2] & (1 << i)) {
800 sol[*sol_count][moves] = i;
801 small_optimal_dfs(eofb_transition_table[eofb][i],
802 eorl_transition_table[eorl][i],
803 eoud_transition_table[eoud][i], ep,
804 coud_transition_table[coud][i],
805 cofb_transition_table[cofb][i],
806 corl_transition_table[corl][i],
807 cp_transition_table[cp][i],
808 sol, sol_count, i, last1, moves+1, m, d);
809 }
810 }
811}
812
813/* Solves directly using only medium tables. Suitable for short solutions.
814void medium_optimal_dfs(int eofb, int eorl, int eoud,
815 int epose, int eposs, int eposm, int ep,
816 int coud, int cofb, int corl, int cp,
817 int sol[][30], int *sol_count, int last1, int last2,
818 int moves, int m, int d) {
819 if (moves + eofb_epose_pruning_table[eofb][epose] > d ||
820 moves + eorl_eposs_pruning_table[eorl][eposs] > d ||
821 moves + eoud_eposm_pruning_table[eoud][eposm] > d ||
822 moves + eofb_coud_pruning_table[eofb][coud] > d ||
823 moves + eofb_corl_pruning_table[eofb][corl] > d ||
824 moves + eorl_coud_pruning_table[eorl][coud] > d ||
825 moves + eorl_cofb_pruning_table[eorl][cofb] > d ||
826 moves + eoud_cofb_pruning_table[eoud][cofb] > d ||
827 moves + eoud_corl_pruning_table[eoud][corl] > d ||
828 moves + cp_pruning_table[cp] > d ||
829 *sol_count >= m)
830 return;
831
832 sol[*sol_count][moves] = 0;
833
834 if (eofb == 0 && coud == 0 && cp == 0) {
835 if (is_ep_solved(ep, sol[*sol_count])) {
836 if (moves != d)
837 return;
838 if (*sol_count < m - 1)
839 copy_moves(sol[*sol_count], sol[(*sol_count)+1]);
840 (*sol_count)++;
841 return;
842 }
843 }
844
845 for (int i = 1; i < 19; i++) {
846 if (possible_next[last1][last2] & (1 << i)) {
847 sol[*sol_count][moves] = i;
848 medium_optimal_dfs(eofb_transition_table[eofb][i],
849 eorl_transition_table[eorl][i],
850 eoud_transition_table[eoud][i],
851 epose_transition_table[epose][i],
852 eposs_transition_table[eposs][i],
853 eposm_transition_table[eposm][i], ep,
854 coud_transition_table[coud][i],
855 cofb_transition_table[cofb][i],
856 corl_transition_table[corl][i],
857 cp_transition_table[cp][i],
858 sol, sol_count, i, last1, moves+1, m, d);
859 }
860 }
861}
862*/
863
864/* Uses huge tables */
865int optimal_dfs(int ep, int cp, int eo, int co, int emslices,
866 int sol[][30], int last1, int last2, int moves, int d) {
867 if (moves + cp_co_pruning_table[cp][co] > d ||
868 moves + triple_eo_pruning_table[eo][emslices] > d)
869 return 0;
870
871 sol[0][moves] = 0;
872
873 /* If solved, no need to check the depth */
874 if (cp == 0 && co == 0 && eo == 0 && emslices == 0)
875 if (is_ep_solved(ep, sol[0]))
876 return 1;
877
878 for (int i = 1; i < 19; i++) {
879 if (possible_next[last1][last2] & (1 << i)) {
880 sol[0][moves] = i;
881 if (optimal_dfs(ep, cp_transition_table[cp][i],
882 eofb_transition_table[eo][i],
883 coud_transition_table[co][i],
884 emslices_transition_table[emslices][i],
885 sol, i, last1, moves+1, d))
886 return 1;
887 }
888 }
889 return 0;
890}
891
892int solve_scram(int scram[], int sol[][30], int m, int b, int optimal) {
893
894 /* Initialize pieces. */
895 int eofb = 0, eorl = 0, eoud = 0, ep = 0;
896 int epose = 0, eposs = 0, eposm = 0;
897 int coud = 0, cofb = 0, corl = 0, cp = 0;
898 int emslices = 0;
899 for (int i = 0; scram[i]; i++) {
900 eofb = eofb_transition_table[eofb][scram[i]];
901 eorl = eorl_transition_table[eorl][scram[i]];
902 eoud = eoud_transition_table[eoud][scram[i]];
903
904 epose = epose_transition_table[epose][scram[i]];
905 eposs = eposs_transition_table[eposs][scram[i]];
906 eposm = eposm_transition_table[eposm][scram[i]];
907
908 ep = apply_move_ep_int(scram[i], ep);
909
910 coud = coud_transition_table[coud][scram[i]];
911 cofb = cofb_transition_table[cofb][scram[i]];
912 corl = corl_transition_table[corl][scram[i]];
913 cp = cp_transition_table[cp][scram[i]];
914
915 emslices = emslices_transition_table[emslices][scram[i]];
916 }
917
918 /* First we check if there are solutions of up to max_small moves. */
919 int max_small = 10;
920 int n = 0;
921 init_small_pruning_tables();
922 for (int i = 0; i <= min(b, max_small); i++) {
923 small_optimal_dfs(eofb, eorl, eoud, ep, coud, cofb, corl, cp,
924 sol, &n, 0, 0, 0, m, i);
925 if (n > 0 && optimal)
926 b = min(b, len(sol[0]));
927 }
928
929
930 if (n >= m || b <= 10)
931 return n;
932
933
934 /* If we found at least a solution, we return */
935 if (n > 0)
936 return n;
937
938 /* Then we try a 2-step solver */
939 int max_step1 = 100;
940 int db = 12;
941 int step1[max_step1+10][30];
942 int ss[300], step2[2][30];
943 int best = b+1;
944
945 /* TODO maybe: for now, multiple solutions can be found only using the
946 * short solver. */
947
948 int n_step1 = dr_scram_spam(scram, step1, 1, 1, 1, max_step1, min(b, db), 0);
949 for (int i = 0; i < n_step1; i++) {
950 copy_moves(scram, ss);
951 append_moves(step1[i], ss);
952 if (dr_finish_scram_spam(ss, step2, 0, 1, min(best-1,b) - len(step1[i]))) {
953 copy_moves(step1[i], sol[0]);
954 append_moves(step2[0], sol[0]);
955 best = len(sol[0]);
956 }
957 }
958
959 /* If optimal solving was not required, or we have already found an optimal
960 * solution, we return. */
961 if (best <= len(step1[n_step1-1]) || !optimal)
962 return best > b ? 0 : 1;
963
964 /* Otherwise, we go on with the optimal solver. */
965 int searched = len(step1[n_step1-1])-1;
966
967 printf("Searched up to %d moves, no solution found.\n", searched);
968 printf("Using huge pruning tables, if not loaded it might take a while.\n");
969 init_huge_pruning_tables();
970
971 for (int i = searched+1; i <= min(b, best-1); i++) {
972 if (i >= 10)
973 printf("Searching at depth %d.\n", i);
974 if (optimal_dfs(ep, cp, eofb, coud, emslices, sol, 0, 0, 0, i)) {
975 return 1;
976 }
977 }
978 return best > b ? 0 : 1;
979}
980
981/* Given eofb, coud, ep and cp it finds a scramble that reaches that state.
982 * It uses a simple 3-step solver to find a preliminary "solution", and then
983 * gives this solutions as a scramble to a better solver (see above). */
984int reach_state(int eofb, int coud, int ep, int cp, int sol[][30]) {
985
986 int fake_count = 0, fake_scram[30];
987 int eo_list[2][30], dr_list[2][30], finish_list[2][30];
988
989 /* Convert ep to array */
990 int ep_arr[12];
991 ep_int_to_array(ep, ep_arr);
992
993 /* Find EO */
994 init_small_pruning_tables();
995 for (int d = 0; d < 10; d++) {
996 niss_eo_dfs(eofb, fake_scram, eo_list, &fake_count, eofb_transition_table,
997 eofb_pruning_table, 0, 0, 0, 1, d, 0, 0, 0);
998 if (fake_count) {
999 fake_count = 0;
1000 break;
1001 }
1002 }
1003
1004 /* Apply moves found, find epose */
1005 for (int i = 0; eo_list[0][i]; i++) {
1006 coud = coud_transition_table[coud][eo_list[0][i]];
1007 cp = cp_transition_table[cp][eo_list[0][i]];
1008 apply_move_ep_array(eo_list[0][i], ep_arr);
1009 }
1010 int epose = epose_array_to_int(ep_arr);
1011
1012 /* Find DR */
1013 init_drfromeo_pruning_tables();
1014 for (int d = 0; d < 16; d++) {
1015 niss_dr_from_eo_dfs(coud, epose, fake_scram, fake_scram, dr_list,
1016 &fake_count, coud_transition_table,
1017 epose_transition_table,
1018 coud_epose_from_eofb_pruning_table, move_mask_eofb,
1019 0, 0, 0, 0, 0, 1, d, 0, 0, 0);
1020 if (fake_count) {
1021 fake_count = 0;
1022 break;
1023 }
1024 }
1025
1026 /* Apply moves found, find epud and epe */
1027 for (int i = 0; dr_list[0][i]; i++) {
1028 cp = cp_transition_table[cp][dr_list[0][i]];
1029 apply_move_ep_array(dr_list[0][i], ep_arr);
1030 }
1031 int epud = epud_array_to_int(ep_arr);
1032 int epe = epe_array_to_int(ep_arr);
1033
1034 /* Find finish */
1035 init_small_pruning_tables();
1036 for (int d = 0; d < 16; d++) {
1037 dr_finish_dfs(cp, epud, epe, finish_list, &fake_count,
1038 epud_transition_table, epe_transition_table,
1039 cp_drud_pruning_table, epud_pruning_table, move_mask_drud,
1040 0, 0, 0, 1, d);
1041 if (fake_count) {
1042 fake_count = 0;
1043 break;
1044 }
1045 }
1046
1047 int scram[50];
1048
1049 /* Debug */
1050 /*print_moves(eo_list[0]); printf("\n");
1051 print_moves(dr_list[0]); printf("\n");
1052 print_moves(finish_list[0]); printf("\n");*/
1053
1054 copy_moves(eo_list[0], scram);
1055 append_moves(dr_list[0], scram);
1056 append_moves(finish_list[0], scram);
1057 return solve_scram(scram, sol, 1, 25, 0);
1058}

Generated with cgit - Back to sebastiano.tronto.net