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

Generated with cgit - Back to sebastiano.tronto.net