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

Generated with cgit - Back to sebastiano.tronto.net