solve_old.c (10063B)
1 #define SOLVE_C 2 3 #include "solve.h" 4 5 /* Local functions ***********************************************************/ 6 7 static void copy_dfsarg(DfsArg *src, DfsArg *dst); 8 static void dfs(DfsArg *arg); 9 static void dfs_add_sol(DfsArg *arg); 10 static void dfs_niss(DfsArg *arg); 11 static bool dfs_move_checkstop(DfsArg *arg); 12 static void * instance_thread(void *arg); 13 static void multidfs(DfsArg *arg); 14 static bool niss_makes_sense(DfsArg *arg); 15 static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); 16 17 /* Local functions ***********************************************************/ 18 19 static void 20 copy_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 43 static void 44 dfs(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 74 static void 75 dfs_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 99 static void 100 dfs_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 130 static bool 131 dfs_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 164 static void * 165 instance_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 212 static void 213 multidfs(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 268 static bool 269 niss_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 292 static bool 293 solvestop(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 306 AlgList * 307 solve(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! */ 389 Alg * 390 solve_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 }