solve.c (11717B)
1 #include "solve.h" 2 3 /* Local functions ***********************************************************/ 4 5 static bool allowed_next(Move move, DfsArg *arg); 6 static bool cancel_niss(DfsArg *arg); 7 static void copy_dfsarg(DfsArg *src, DfsArg *dst); 8 static void dfs(DfsArg *arg); 9 static void dfs_branch(DfsArg *arg); 10 static bool dfs_check_solved(DfsArg *arg); 11 static bool dfs_switch(DfsArg *arg); 12 static void dfs_niss(DfsArg *arg); 13 static bool dfs_stop(DfsArg *arg); 14 static bool dfs_useless_niss(DfsArg *arg); 15 static void * instance_thread(void *arg); 16 static void invert_branch(DfsArg *arg); 17 static void multidfs(Cube c, Trans t, Step *s, SolveOptions *opts, 18 AlgList *sols, int d); 19 static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); 20 21 /* Local functions ***********************************************************/ 22 23 static bool 24 allowed_next(Move m, DfsArg *arg) 25 { 26 bool bad, allowed, order; 27 uint64_t mbit; 28 29 mbit = ((uint64_t)1) << m; 30 bad = mbit & arg->badmoves; 31 allowed = mbit & arg->step->moveset->mask[arg->last2][arg->last1]; 32 order = !commute(arg->last1, m) || arg->last1 < m; 33 34 return allowed && !bad && order; 35 } 36 37 static bool 38 cancel_niss(DfsArg *arg) 39 { 40 Moveset *ms; 41 Move i1, i2; 42 bool p, p1, p2, q, q1, q2; 43 44 if (arg->last1inv == NULLMOVE) 45 return false; 46 47 ms = arg->step->moveset; 48 i1 = inverse_move(arg->last1inv); 49 i2 = inverse_move(arg->last2inv); 50 51 p1 = !ms->allowed_next(arg->last2, arg->last1, i1); 52 p2 = !ms->allowed_next(arg->last2, i1, arg->last1); 53 p = p1 || (commute(i1, arg->last1) && p2); 54 55 q1 = !ms->allowed_next(arg->last2, arg->last1, i2); 56 q2 = !ms->allowed_next(arg->last2, i2, arg->last1); 57 q = q1 || (commute(i2, arg->last1) && q2); 58 59 return p || (commute(i1, i2) && q); 60 } 61 62 static void 63 copy_dfsarg(DfsArg *src, DfsArg *dst) 64 { 65 dst->step = src->step; 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 85 static void 86 dfs(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 96 if (arg->step->final && (sw = dfs_switch(arg))) 97 invert_branch(arg); 98 dfs_branch(arg); 99 100 if (arg->opts->nisstype == NISS && !arg->niss && !arg->step->final) 101 dfs_niss(arg); 102 103 if (sw) 104 invert_branch(arg); 105 } 106 107 static void 108 dfs_branch(DfsArg *arg) 109 { 110 int i; 111 Move m; 112 DfsArg *newarg; 113 114 newarg = malloc(sizeof(DfsArg)); 115 newarg->ed = malloc(sizeof(EstimateData)); 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 126 dfs(newarg); 127 128 arg->current_alg->len--; 129 } 130 } 131 132 free(newarg->ed); 133 free(newarg); 134 } 135 136 static bool 137 dfs_check_solved(DfsArg *arg) 138 { 139 if (!arg->step->is_done(arg->cube)) 140 return false; 141 142 if (arg->current_alg->len == arg->d && !dfs_useless_niss(arg)) { 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 151 transform_alg( 152 inverse_trans(arg->t), 153 arg->sols->last->alg 154 ); 155 if (arg->step->final) 156 inplace(unniss, arg->sols->last->alg); 157 158 if (arg->opts->verbose) 159 print_alg(stderr, 160 arg->sols->last->alg, false); 161 } 162 163 pthread_mutex_unlock(arg->sols_mutex); 164 } 165 } 166 167 return true; 168 } 169 170 static void 171 dfs_niss(DfsArg *arg) 172 { 173 DfsArg *newarg; 174 175 newarg = malloc(sizeof(DfsArg)); 176 newarg->ed = malloc(sizeof(EstimateData)); 177 178 copy_dfsarg(arg, newarg); 179 swapmove(&(newarg->last1), &(newarg->last1inv)); 180 swapmove(&(newarg->last2), &(newarg->last2inv)); 181 newarg->niss = !(arg->niss); 182 newarg->cube = inverse_cube(arg->cube); 183 184 dfs(newarg); 185 186 free(newarg->ed); 187 free(newarg); 188 } 189 190 static bool 191 dfs_stop(DfsArg *arg) 192 { 193 int lowerbound; 194 bool b; 195 196 lowerbound = arg->step->estimate(arg); 197 if (arg->opts->nisstype == NISS && !arg->niss) 198 lowerbound = MIN(1, lowerbound); 199 200 if (arg->current_alg->len + lowerbound > arg->d) { 201 b = true; 202 } else { 203 pthread_mutex_lock(arg->sols_mutex); 204 b = arg->sols->len >= arg->opts->max_solutions; 205 pthread_mutex_unlock(arg->sols_mutex); 206 } 207 208 return b; 209 } 210 211 static bool 212 dfs_switch(DfsArg *arg) 213 { 214 int i, bn, bi; 215 216 bn = 0; 217 for (i = 0; arg->step->moveset->sorted_moves[i] != NULLMOVE; i++) 218 if (allowed_next(arg->step->moveset->sorted_moves[i], arg)) 219 bn++; 220 221 swapmove(&(arg->last1), &(arg->last1inv)); 222 swapmove(&(arg->last2), &(arg->last2inv)); 223 swapu64(&(arg->badmoves), &(arg->badmovesinv)); 224 225 bi = 0; 226 for (i = 0; arg->step->moveset->sorted_moves[i] != NULLMOVE; i++) 227 if (allowed_next(arg->step->moveset->sorted_moves[i], arg)) 228 bi++; 229 230 swapmove(&(arg->last1), &(arg->last1inv)); 231 swapmove(&(arg->last2), &(arg->last2inv)); 232 swapu64(&(arg->badmoves), &(arg->badmovesinv)); 233 234 return bi < bn; 235 } 236 237 static bool 238 dfs_useless_niss(DfsArg *arg) 239 { 240 Cube c; 241 Move m = arg->last1inv; 242 243 if (m == NULLMOVE || !arg->niss) 244 return false; 245 246 c = apply_move(inverse_move(m), arg->cube); 247 248 return arg->step->is_done(c); 249 } 250 251 static void * 252 instance_thread(void *arg) 253 { 254 bool b; 255 Cube c; 256 ThreadDataSolve *td; 257 AlgListNode *node; 258 DfsArg darg; 259 260 td = (ThreadDataSolve *)arg; 261 262 while (1) { 263 b = false; 264 265 pthread_mutex_lock(td->start_mutex); 266 if ((node = *(td->node)) == NULL) 267 b = true; 268 else 269 *(td->node) = (*(td->node))->next; 270 pthread_mutex_unlock(td->start_mutex); 271 272 if (b) 273 break; 274 275 c = node->alg->inv[0] ? 276 apply_move(node->alg->move[0], inverse_cube(td->cube)) : 277 apply_move(node->alg->move[0], td->cube); 278 279 darg.step = td->step; 280 darg.opts = td->opts; 281 darg.t = td->t; 282 darg.cube = c; 283 darg.d = td->depth; 284 darg.niss = node->alg->inv[0]; 285 darg.last1 = node->alg->move[0]; 286 darg.last2 = NULLMOVE; 287 darg.last1inv = NULLMOVE; 288 darg.last2inv = NULLMOVE; 289 darg.sols = td->sols; 290 darg.sols_mutex = td->sols_mutex; 291 darg.current_alg = new_alg(""); 292 append_move(darg.current_alg, node->alg->move[0], 293 node->alg->inv[0]); 294 darg.ed = malloc(sizeof(EstimateData)); 295 reset_estimatedata(darg.ed); 296 darg.badmoves = 0; 297 darg.badmovesinv = 0; 298 299 dfs(&darg); 300 301 free_alg(darg.current_alg); 302 free(darg.ed); 303 } 304 305 return NULL; 306 } 307 308 static void 309 invert_branch(DfsArg *arg) 310 { 311 Cube aux; 312 313 aux = arg->cube; 314 arg->cube = is_solved(arg->inverse) ? 315 inverse_cube(arg->cube) : arg->inverse; 316 arg->inverse = aux; 317 318 swapu64(&(arg->badmoves), &(arg->badmovesinv)); 319 arg->niss = !(arg->niss); 320 swapmove(&(arg->last1), &(arg->last1inv)); 321 swapmove(&(arg->last2), &(arg->last2inv)); 322 invert_estimatedata(arg->ed); 323 } 324 325 static void 326 multidfs(Cube c, Trans tr, Step *s, SolveOptions *opts, AlgList *sols, int d) 327 { 328 int i; 329 Alg *alg; 330 AlgList *start; 331 AlgListNode **node; 332 pthread_t t[opts->nthreads]; 333 ThreadDataSolve td[opts->nthreads]; 334 pthread_mutex_t *start_mutex, *sols_mutex; 335 336 node = malloc(sizeof(AlgListNode *)); 337 start_mutex = malloc(sizeof(pthread_mutex_t)); 338 sols_mutex = malloc(sizeof(pthread_mutex_t)); 339 340 start = new_alglist(); 341 pthread_mutex_init(start_mutex, NULL); 342 pthread_mutex_init(sols_mutex, NULL); 343 344 for (i = 0; s->moveset->sorted_moves[i] != NULLMOVE; i++) { 345 alg = new_alg(""); 346 append_move(alg, s->moveset->sorted_moves[i], false); 347 append_alg(start, alg); 348 if (opts->nisstype == NISS || opts->nisstype == LINEAR) { 349 alg->inv[0] = true; 350 append_alg(start, alg); 351 } 352 free_alg(alg); 353 } 354 *node = start->first; 355 356 for (i = 0; i < opts->nthreads; i++) { 357 td[i].thid = i; 358 td[i].t = tr; 359 td[i].cube = c; 360 td[i].step = s; 361 td[i].depth = d; 362 td[i].opts = opts; 363 td[i].start = start; 364 td[i].node = node; 365 td[i].sols = sols; 366 td[i].start_mutex = start_mutex; 367 td[i].sols_mutex = sols_mutex; 368 pthread_create(&t[i], NULL, instance_thread, &td[i]); 369 } 370 371 for (i = 0; i < opts->nthreads; i++) 372 pthread_join(t[i], NULL); 373 374 free_alglist(start); 375 free(node); 376 free(start_mutex); 377 free(sols_mutex); 378 } 379 380 static bool 381 solvestop(int d, int op, SolveOptions *opts, AlgList *sols) 382 { 383 bool opt_done, max_moves_exceeded, max_sols_exceeded; 384 385 opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op; 386 max_moves_exceeded = d > opts->max_moves; 387 max_sols_exceeded = sols->len >= opts->max_solutions; 388 389 return opt_done || max_moves_exceeded || max_sols_exceeded; 390 } 391 392 /* Public functions **********************************************************/ 393 394 AlgList * 395 solve(Cube cube, Step *step, SolveOptions *opts) 396 { 397 bool ready; 398 int i, d, op, nt; 399 Alg *algaux; 400 AlgList *sols; 401 Cube c; 402 Trans tt[NTRANS]; 403 404 prepare_step(step, opts); 405 406 if (step->detect != NULL) { 407 nt = step->detect(cube, tt); 408 } else { 409 tt[0] = step->pre_trans; 410 ready = step->ready == NULL || 411 step->ready(apply_trans(tt[0], cube)); 412 nt = ready ? 1 : 0; 413 } 414 415 sols = new_alglist(); 416 417 if (nt == 0) { 418 fprintf(stderr, "Cube not ready for solving step: "); 419 fprintf(stderr, "%s\n", step->ready_msg); 420 return sols; 421 } 422 423 if (opts->min_moves == 0) { 424 for (i = 0; i < nt; i++) { 425 c = apply_trans(tt[i], cube); 426 if (step->is_done(c)) { 427 algaux = new_alg(""); 428 append_alg(sols, algaux); 429 free_alg(algaux); 430 return sols; 431 } 432 } 433 } 434 435 op = -1; 436 for (d = opts->min_moves; !solvestop(d, op, opts, sols); d++) { 437 if (opts->verbose) 438 fprintf(stderr, "Searching depth %d\n", d); 439 440 for (i = 0; i < nt && !solvestop(d, op, opts, sols); i++) { 441 c = apply_trans(tt[i], cube); 442 multidfs(c, tt[i], step, opts, sols, d); 443 if (sols->len > 0 && op == -1) 444 op = d; 445 } 446 } 447 448 return sols; 449 } 450 451 /* TODO: make more general! */ 452 Alg * 453 solve_2phase(Cube cube, int nthreads) 454 { 455 int bestlen, newb; 456 Alg *bestalg, *ret; 457 AlgList *sols1, *sols2; 458 AlgListNode *i; 459 Cube c; 460 SolveOptions opts1, opts2; 461 462 opts1.min_moves = 0; 463 opts1.max_moves = 13; 464 opts1.max_solutions = 20; 465 opts1.nthreads = nthreads; 466 opts1.optimal = 3; 467 opts1.nisstype = NORMAL; 468 opts1.verbose = false; 469 opts1.all = true; 470 471 opts2.min_moves = 0; 472 opts2.max_moves = 19; 473 opts2.max_solutions = 1; 474 opts2.nthreads = nthreads; 475 opts2.nisstype = NORMAL; 476 opts2.verbose = false; 477 478 /* We skip step1 if it is solved on any axis */ 479 if (drany_HTM.is_done(cube)) { 480 sols1 = new_alglist(); 481 append_alg(sols1, new_alg("")); 482 } else { 483 sols1 = solve(cube, &drany_HTM, &opts1); 484 } 485 bestalg = new_alg(""); 486 bestlen = 999; 487 for (i = sols1->first; i != NULL; i = i->next) { 488 c = apply_alg(i->alg, cube); 489 sols2 = solve(c, &dranyfin_DR, &opts2); 490 491 if (sols2->len > 0) { 492 newb = i->alg->len + sols2->first->alg->len; 493 if (newb < bestlen) { 494 bestlen = newb; 495 copy_alg(i->alg, bestalg); 496 compose_alg(bestalg, sols2->first->alg); 497 } 498 } 499 500 free_alglist(sols2); 501 } 502 503 free_alglist(sols1); 504 505 ret = cleanup(bestalg); 506 free_alg(bestalg); 507 508 return ret; 509 }