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

Generated with cgit - Back to sebastiano.tronto.net