aboutsummaryrefslogtreecommitdiff
path: root/src/solve.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/solve.c')
-rw-r--r--src/solve.c513
1 files changed, 73 insertions, 440 deletions
diff --git a/src/solve.c b/src/solve.c
index d5a8f3d..41f99a2 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -2,485 +2,118 @@
2 2
3#include "solve.h" 3#include "solve.h"
4 4
5/* Local functions ***********************************************************/ 5void
6 6dfs(DfsArg *arg, Solver *solver, Threader *threader)
7static bool cancel_niss(DfsArg *arg);
8static void copy_dfsarg(DfsArg *src, DfsArg *dst);
9static void dfs(DfsArg *arg);
10static void dfs_add_sol(DfsArg *arg);
11static void dfs_niss(DfsArg *arg);
12static bool dfs_move_checkstop(DfsArg *arg);
13static void * instance_thread(void *arg);
14static void multidfs(DfsArg *arg);
15static bool niss_makes_sense(DfsArg *arg);
16static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols);
17
18/* Local functions ***********************************************************/
19
20static bool
21cancel_niss(DfsArg *arg)
22{
23 Moveset *ms;
24 Move i1, i2;
25 bool p, p1, p2, q, q1, q2;
26
27 if (arg->lastinv[0] == NULLMOVE)
28 return false;
29
30 ms = arg->s->moveset;
31 i1 = inverse_move(arg->lastinv[0]);
32 i2 = inverse_move(arg->lastinv[1]);
33
34 p1 = !ms->allowed_next(arg->last[1], arg->last[0], i1);
35 p2 = !ms->allowed_next(arg->last[1], i1, arg->last[0]);
36 p = p1 || (commute(i1, arg->last[0]) && p2);
37
38 q1 = !ms->allowed_next(arg->last[1], arg->last[0], i2);
39 q2 = !ms->allowed_next(arg->last[1], i2, arg->last[0]);
40 q = q1 || (commute(i2, arg->last[0]) && q2);
41
42 return p || (commute(i1, i2) && q);
43}
44
45static void
46copy_dfsarg(DfsArg *src, DfsArg *dst)
47{ 7{
48 int i; 8 int i;
49
50 dst->cube = src->cube;
51 dst->t = src->t;
52 dst->s = src->s;
53 dst->opts = src->opts;
54 dst->d = src->d;
55 dst->bound = src->bound; /* In theory not needed */
56 dst->niss = src->niss;
57 dst->sols = src->sols;
58 dst->sols_mutex = src->sols_mutex;
59 dst->current_alg = src->current_alg;
60
61 for (i = 0; i < 2; i++) {
62 dst->last[i] = src->last[i];
63 dst->lastinv[i] = src->lastinv[i];
64 }
65
66 for (i = 0; i < src->s->n_coord; i++) {
67 dst->ind[i].val = src->ind[i].val;
68 dst->ind[i].t = src->ind[i].t;
69 }
70
71 src->s->copy_extra(src, dst);
72}
73
74static void
75dfs(DfsArg *arg)
76{
77 int i;
78 Move m, l0, l1;
79 DfsArg newarg; 9 DfsArg newarg;
10 Alg *sol;
11 Move m;
80 12
81 if (dfs_move_checkstop(arg)) 13 if (arg->current_alg->len > arg->d)
82 return;
83
84 if (arg->bound == 0) {
85 if (arg->current_alg->len == arg->d)
86 dfs_add_sol(arg);
87 return; 14 return;
88 }
89
90 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) {
91 m = arg->s->moveset->sorted_moves[i];
92 l0 = arg->last[0];
93 l1 = arg->last[1];
94 if (possible_next(m, arg->s->moveset, l0, l1)) {
95 copy_dfsarg(arg, &newarg);
96 newarg.last[1] = l0;
97 newarg.last[0] = m;
98 append_move(arg->current_alg, m, newarg.niss);
99 dfs(&newarg);
100 arg->current_alg->len--;
101 }
102 }
103
104 if (niss_makes_sense(arg))
105 dfs_niss(arg);
106}
107
108static void
109dfs_add_sol(DfsArg *arg)
110{
111 bool valid, accepted, nisscanc;
112 15
113 valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); 16 if (solver->is_solved(solver->param, arg->cubedata)) {
114 accepted = valid || arg->opts->all; 17/* TODO: the "all" option should be re-implemented as setting
115 nisscanc = arg->s->final && cancel_niss(arg); 18validate to null */
116 19
117 if (accepted && !nisscanc) { 20/* TODO: we also have to check if cancel with NISS;
118 pthread_mutex_lock(arg->sols_mutex); 21we can't because we have no access to the s->final field
22this should be done by the step's validator? */
23 sol = solver->validate_solution(solver->param,arg->current_alg);
24 bool accepted = sol != NULL;
25 bool too_short = arg->current_alg->len != arg->d;
119 26
120 if (arg->sols->len < arg->opts->max_solutions) { 27 if (accepted && !too_short) {
121 append_alg(arg->sols, arg->current_alg); 28/* TODO: arg->t got lost in refactoring */
122 transform_alg( 29/* transform_alg(inverse_trans(arg->t), sol);*/
123 inverse_trans(arg->t), arg->sols->last->alg);
124 if (arg->opts->verbose) 30 if (arg->opts->verbose)
125 print_alg(arg->sols->last->alg, false); 31 print_alg(sol, false);
32 threader->append_sol(sol, arg->threaddata);
126 } 33 }
127 34 return;
128 pthread_mutex_unlock(arg->sols_mutex);
129 }
130}
131
132static void
133dfs_niss(DfsArg *arg)
134{
135 DfsArg newarg;
136 Alg *inv;
137 Cube *c;
138
139 copy_dfsarg(arg, &newarg);
140
141 /* Invert current alg and scramble */
142 newarg.cube = malloc(sizeof(Cube));
143 inv = inverse_alg(arg->current_alg);
144 c = malloc(sizeof(Cube));
145 make_solved(newarg.cube);
146 apply_alg(inv, newarg.cube);
147 copy_cube(arg->cube, c);
148 invert_cube(c);
149 compose(c, newarg.cube);
150
151 /* New indexes */
152 compute_ind(newarg.s, newarg.cube, newarg.ind);
153
154 swapmove(&(newarg.last[0]), &(newarg.lastinv[0]));
155 swapmove(&(newarg.last[1]), &(newarg.lastinv[1]));
156 newarg.niss = !(arg->niss);
157
158 dfs(&newarg);
159
160 free_alg(inv);
161 free(c);
162 free(newarg.cube);
163}
164
165static bool
166dfs_move_checkstop(DfsArg *arg)
167{
168 int i, goal, nsols;
169 Move mm;
170 Trans tt = uf; /* Avoid uninitialized warning */
171
172 /* Moving and computing bound */
173 arg->bound = 0;
174 goal = arg->d - arg->current_alg->len;
175 for (i = 0; i < arg->s->n_coord; i++) {
176 if (arg->last[0] != NULLMOVE) {
177 mm = transform_move(arg->ind[i].t, arg->last[0]);
178 arg->ind[i].val = move_coord(arg->s->coord[i],
179 mm, arg->ind[i].val, &tt);
180 arg->ind[i].t = transform_trans(tt, arg->ind[i].t);
181 }
182
183 arg->bound =
184 MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val));
185 if (arg->opts->can_niss && !arg->niss)
186 arg->bound = MIN(1, arg->bound);
187
188 if (arg->bound > goal)
189 return true;
190 }
191
192 pthread_mutex_lock(arg->sols_mutex);
193 nsols = arg->sols->len;
194 pthread_mutex_unlock(arg->sols_mutex);
195
196 return nsols >= arg->opts->max_solutions;
197}
198
199static void *
200instance_thread(void *arg)
201{
202 bool b, inv;
203 Cube c;
204 Move m;
205 ThreadDataSolve *td;
206 AlgListNode *node;
207 DfsArg darg;
208
209 td = (ThreadDataSolve *)arg;
210
211 while (1) {
212 b = false;
213
214 pthread_mutex_lock(td->start_mutex);
215 if ((node = *(td->node)) == NULL)
216 b = true;
217 else
218 *(td->node) = (*(td->node))->next;
219 pthread_mutex_unlock(td->start_mutex);
220
221 if (b)
222 break;
223
224 inv = node->alg->inv[0];
225 m = node->alg->move[0];
226
227 copy_cube(td->arg.cube, &c);
228 if (inv)
229 invert_cube(&c);
230
231 copy_dfsarg(&td->arg, &darg);
232 compute_ind(td->arg.s, &c, darg.ind);
233 darg.cube = &c;
234
235 darg.niss = inv;
236 darg.last[0] = m;
237 darg.last[1] = NULLMOVE;
238 darg.lastinv[0] = NULLMOVE;
239 darg.lastinv[1] = NULLMOVE;
240 darg.current_alg = new_alg("");
241 append_move(darg.current_alg, m, inv);
242
243 dfs(&darg);
244
245 free_alg(darg.current_alg);
246 } 35 }
247 36
248 return NULL; 37 if (arg->current_alg->len == arg->d)
249} 38 return;
250
251static void
252multidfs(DfsArg *arg)
253{
254 int i;
255 Cube local_cube;
256 Alg *alg;
257 AlgList *start;
258 AlgListNode **node;
259 pthread_t t[arg->opts->nthreads];
260 ThreadDataSolve td[arg->opts->nthreads];
261 pthread_mutex_t *start_mutex, *sols_mutex;
262 39
263 node = malloc(sizeof(AlgListNode *)); 40/* TODO: do not alloc */
264 start_mutex = malloc(sizeof(pthread_mutex_t)); 41 newarg.cubedata = solver->alloc_cubedata(solver->param);
265 sols_mutex = malloc(sizeof(pthread_mutex_t)); 42 for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) {
43 m = solver->moveset->sorted_moves[i];
44 if (solver->moveset->can_append(arg->current_alg, m, arg->niss)
45 && compare_last(arg->current_alg, m, arg->niss) >= 0) {
46 append_move(arg->current_alg, m, arg->niss);
266 47
267 start = new_alglist(); 48 solver->copy_cubedata(
268 pthread_mutex_init(start_mutex, NULL); 49 solver->param, arg->cubedata, newarg.cubedata);
269 pthread_mutex_init(sols_mutex, NULL); 50 newarg.threaddata = arg->threaddata;
51 newarg.opts = arg->opts;
52 newarg.d = arg->d;
53 newarg.niss = arg->niss;
54 newarg.current_alg = arg->current_alg;
55 if (!solver->move_check_stop(
56 solver->param, &newarg, threader))
57 dfs(&newarg, solver, threader);
270 58
271 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { 59 remove_last_move(arg->current_alg);
272 alg = new_alg("");
273 append_move(alg, arg->s->moveset->sorted_moves[i], false);
274 append_alg(start, alg);
275 if (arg->opts->can_niss && !arg->s->final) {
276 alg->inv[0] = true;
277 append_alg(start, alg);
278 } 60 }
279 free_alg(alg);
280 } 61 }
281 *node = start->first; 62 solver->free_cubedata(solver->param, newarg.cubedata);
282
283 copy_cube(arg->cube, &local_cube);
284
285 for (i = 0; i < arg->opts->nthreads; i++) {
286 copy_dfsarg(arg, &(td[i].arg));
287 td[i].arg.cube = &local_cube;
288 td[i].arg.sols_mutex = sols_mutex;
289
290 td[i].thid = i;
291 td[i].start = start;
292 td[i].node = node;
293 td[i].start_mutex = start_mutex;
294
295 pthread_create(&t[i], NULL, instance_thread, &td[i]);
296 }
297
298 for (i = 0; i < arg->opts->nthreads; i++)
299 pthread_join(t[i], NULL);
300
301 free_alglist(start);
302 free(node);
303 free(start_mutex);
304 free(sols_mutex);
305}
306
307static bool
308niss_makes_sense(DfsArg *arg)
309{
310 Move m, mm;
311 uint64_t u;
312 int i;
313
314 if (arg->s->final || arg->niss || !arg->opts->can_niss)
315 return false;
316
317 if (arg->last[0] == NULLMOVE)
318 return true;
319 63
320 m = inverse_move(arg->last[0]); 64 if (arg->opts->can_niss && !arg->niss &&
321 for (i = 0; i < arg->s->n_coord; i++) { 65 solver->niss_makes_sense(
322 mm = transform_move(arg->ind[i].t, m); 66 solver->param, arg->cubedata, arg->current_alg)) {
323 u = move_coord(arg->s->coord[i], mm, 0, NULL); 67 solver->invert_cube(solver->param, arg->cubedata);
324 if (ptableval(arg->s->pd[i], u) > 0) 68 arg->niss = true;
325 return true; 69 dfs(arg, solver, threader);
326 } 70 }
327
328 return false;
329} 71}
330 72
331static bool
332solvestop(int d, int op, SolveOptions *opts, AlgList *sols)
333{
334 bool opt_done, max_moves_exceeded, max_sols_exceeded;
335
336 opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op;
337 max_moves_exceeded = d > opts->max_moves;
338 max_sols_exceeded = sols->len >= opts->max_solutions;
339
340 return opt_done || max_moves_exceeded || max_sols_exceeded;
341}
342
343/* Public functions **********************************************************/
344
345AlgList * 73AlgList *
346solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) 74solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader)
347{ 75{
348 int i, j, d, op, est; 76 int i, d, optimal;
349 bool ready[99], one_ready, zerosol; 77 bool ready[MAX_SOLVERS], stop, one_ready;
350 Movable ind[99][10]; 78 DfsArg arg[MAX_SOLVERS];
351 AlgList *s; 79 AlgList *sols;
352 Cube *c[99];
353 DfsArg arg[99];
354
355 prepare_cs(cs, opts);
356 s = new_alglist();
357
358 for (i = 0, one_ready = false; cs->step[i] != NULL; i++) {
359 c[i] = malloc(sizeof(Cube));
360 copy_cube(cube, c[i]);
361 apply_trans(cs->t[i], c[i]);
362 80
363 arg[i].cube = c[i]; 81 one_ready = false;
364 arg[i].t = cs->t[i]; 82 for (i = 0; solver[i] != NULL; i++) {
365 arg[i].s = cs->step[i]; 83 arg[i].cubedata =
84 solver[i]->prepare_cube(solver[i]->param, cube);
366 arg[i].opts = opts; 85 arg[i].opts = opts;
367 arg[i].sols = s; 86 ready[i] = arg[i].cubedata != NULL;
368 87 one_ready = one_ready || ready[i];
369 if ((ready[i] = cs->step[i]->ready(c[i]))) {
370 one_ready = true;
371 /* Only for local use for 0 moves solutions */
372 compute_ind(cs->step[i], c[i], ind[i]);
373 }
374 }
375 if (!one_ready) {
376 fprintf(stderr, "Cube not ready for solving step: ");
377 fprintf(stderr, "%s\n", cs->ready_msg);
378 return s;
379 } 88 }
380 89
381 /* If the empty moves sequence is a solution for one of the 90 sols = new_alglist();
382 * alternatives, all longer solutions will be discarded, so we may 91 if (!one_ready) {
383 * just set its ready[] value to false. If the solution is accepted 92 fprintf(stderr, "Cube not ready for solving\n");
384 * we append it and start searching from d = 1. */ 93 return sols;
385 for (i = 0, zerosol = false; cs->step[i] != NULL; i++) {
386 if (ready[i]) {
387 est = 0;
388 for (j = 0; j < cs->step[i]->n_coord; j++)
389 est = MAX(est, ptableval(cs->step[i]->pd[j],
390 ind[i][j].val));
391 if (est == 0) {
392 ready[i] = false;
393 zerosol = true;
394 }
395 }
396 }
397 if (zerosol && opts->min_moves == 0) {
398 append_alg(s, new_alg(""));
399 opts->min_moves = 1;
400 if (opts->verbose)
401 printf("Step is already solved"
402 "(empty alg is a solution)\n");
403 } 94 }
404 95
405 for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { 96 optimal = opts->max_moves;
97 stop = false;
98 for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) {
406 if (opts->verbose) 99 if (opts->verbose)
407 fprintf(stderr, "Searching depth %d\n", d); 100 fprintf(stderr, "Searching depth %d\n", d);
408 101
409 for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { 102 for (i = 0; solver[i] != NULL && !stop; i++) {
410 if (!ready[i]) 103 if (!ready[i])
411 continue; 104 continue;
412 105
413 arg[i].d = d; 106 arg[i].d = d;
414 multidfs(&arg[i]); 107 threader->dispatch(&arg[i], sols, solver[i], threader);
415
416 if (s->len > 0 && op == -1)
417 op = d;
418 }
419 }
420
421 for (i = 0; cs->step[i] != NULL; i++)
422 free(c[i]);
423
424 return s;
425}
426 108
427/* TODO: make more general! */ 109 if (sols->len > 0)
428Alg * 110 optimal = MIN(optimal, d);
429solve_2phase(Cube *cube, int nthreads)
430{
431 int bestlen, newb;
432 Alg *bestalg, *ret;
433 AlgList *sols1, *sols2;
434 AlgListNode *i;
435 Cube c;
436 SolveOptions opts1, opts2;
437
438 opts1.min_moves = 0;
439 opts1.max_moves = 13;
440 opts1.max_solutions = 20;
441 opts1.nthreads = nthreads;
442 opts1.optimal = 3;
443 opts1.can_niss = false;
444 opts1.verbose = false;
445 opts1.all = true;
446 111
447 opts2.min_moves = 0; 112 stop = sols->len >= opts->max_solutions;
448 opts2.max_moves = 19;
449 opts2.max_solutions = 1;
450 opts2.nthreads = nthreads;
451 opts2.can_niss = false;
452 opts2.verbose = false;
453
454 /* We skip step1 if it is solved on U/D */
455 if (check_drud(cube)) {
456 sols1 = new_alglist();
457 append_alg(sols1, new_alg(""));
458 } else {
459 sols1 = solve(cube, &drud_HTM, &opts1);
460 }
461 bestalg = new_alg("");
462 bestlen = 999;
463 for (i = sols1->first; i != NULL; i = i->next) {
464 copy_cube(cube, &c);
465 apply_alg(i->alg, &c);
466 sols2 = solve(&c, &dranyfin_DR, &opts2);
467
468 if (sols2->len > 0) {
469 newb = i->alg->len + sols2->first->alg->len;
470 if (newb < bestlen) {
471 bestlen = newb;
472 copy_alg(i->alg, bestalg);
473 compose_alg(bestalg, sols2->first->alg);
474 }
475 } 113 }
476 114 stop = stop ||
477 free_alglist(sols2); 115 (opts->optimal != -1 && d >= opts->optimal + optimal);
478 } 116 }
479 117
480 free_alglist(sols1); 118 return sols;
481
482 ret = cleanup(bestalg);
483 free_alg(bestalg);
484
485 return ret;
486} 119}

Generated with cgit - Back to sebastiano.tronto.net