solve.h (20332B)
1 #define H48_STARTING_MOVES 4 2 #define H48_STARTING_CUBES 43254 3 #define H48_SORT_TASKS_MIN_DEPTH 16 4 #define H48_LOG_PROGRESS_MIN_DEPTH 15 5 6 typedef struct { 7 cube_t cube; 8 uint8_t moves[H48_STARTING_MOVES]; 9 int64_t rank; 10 uint64_t tmask[H48_STARTING_MOVES]; 11 uint8_t pval; 12 } solve_h48_task_t; 13 14 typedef struct { 15 cube_t start_cube; 16 cube_t cube; 17 cube_t inverse; 18 int8_t target_depth; 19 solution_moves_t *solution_moves; 20 solution_settings_t *solution_settings; 21 const uint64_t *tmask; 22 solution_list_t *solution_list; 23 uint8_t lb_normal; 24 uint8_t lb_inverse; 25 uint8_t h; 26 uint8_t base; 27 const uint32_t *cocsepdata; 28 const unsigned char *h48data; 29 const unsigned char *eoesepdata; 30 uint64_t movemask_normal; 31 uint64_t movemask_inverse; 32 uint64_t nodes_visited; 33 uint64_t table_fallbacks; 34 uint64_t table_lookups; 35 int8_t threads; 36 int ntasks; 37 solve_h48_task_t *tasks; 38 int thread_id; 39 wrapthread_define_struct_mutex_t(*solutions_mutex); 40 wrapthread_atomic int *status; 41 wrapthread_atomic bool thread_done; 42 } dfsarg_solve_h48_t; 43 44 typedef struct { 45 cube_t cube; 46 int8_t nmoves; 47 uint8_t moves[H48_STARTING_MOVES]; 48 int8_t minmoves; 49 int8_t maxmoves; 50 int8_t *shortest_sol; 51 uint64_t tmask[H48_STARTING_MOVES]; 52 } dfsarg_solve_h48_maketasks_t; 53 54 typedef struct { 55 cube_t cube; 56 cube_t inverse; 57 uint64_t coord; 58 uint8_t m; 59 uint8_t pn; 60 uint8_t pi; 61 uint8_t stop; 62 } h48_prune_t; 63 64 STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, 65 unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long, 66 const unsigned char *, unsigned, char *, 67 long long [SIZE(NISSY_SIZE_SOLVE_STATS)], int (*)(void *), void *); 68 STATIC_INLINE void h48_prune_pipeline(dfsarg_solve_h48_t [NON_NULL], 69 h48_prune_t [SIZE(NMOVES)], uint8_t, bool); 70 STATIC_INLINE uint8_t h48_prune_lookup( 71 uint64_t, cube_t, dfsarg_solve_h48_t [NON_NULL]); 72 STATIC_INLINE uint8_t h48_prune_lookup_nocoord( 73 cube_t, dfsarg_solve_h48_t [NON_NULL]); 74 STATIC_INLINE void h48_prune_restore_normal(const h48_prune_t [NON_NULL], 75 dfsarg_solve_h48_t [NON_NULL], uint8_t); 76 STATIC_INLINE void h48_prune_restore_inverse(const h48_prune_t [NON_NULL], 77 dfsarg_solve_h48_t [NON_NULL], uint8_t); 78 STATIC int64_t solve_h48_maketasks( 79 dfsarg_solve_h48_t [NON_NULL], dfsarg_solve_h48_maketasks_t [NON_NULL], 80 solve_h48_task_t [SIZE(H48_STARTING_CUBES)], int [NON_NULL]); 81 STATIC wrapthread_return_t solve_h48_runthread(void *); 82 STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [NON_NULL]); 83 STATIC void solve_h48_log_solutions(solution_list_t [NON_NULL], size_t); 84 STATIC int solve_h48_compare_tasks(const void *, const void *); 85 STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint64_t, uint8_t, 86 uint8_t, uint64_t, const unsigned char *, size_t, char *, 87 long long [SIZE(NISSY_SIZE_SOLVE_STATS)], int (*)(void *), void *); 88 89 STATIC long long solve_h48_dispatch( 90 oriented_cube_t oc, 91 const char *solver, 92 unsigned nissflag, 93 unsigned minmoves, 94 unsigned maxmoves, 95 unsigned maxsols, 96 unsigned optimal, 97 unsigned threads, 98 unsigned long long data_size, 99 const unsigned char *data, 100 unsigned sols_size, 101 char *sols, 102 long long stats[SIZE(NISSY_SIZE_SOLVE_STATS)], 103 int (*poll_status)(void *), 104 void *poll_status_data 105 ) 106 { 107 uint8_t h; 108 long long err; 109 110 err = parse_h48h(solver, &h); 111 if (err != NISSY_OK) 112 return err; 113 114 return solve_h48(oc, (uint8_t)minmoves, (uint8_t)maxmoves, 115 (uint8_t)maxsols, (uint8_t)optimal, (uint8_t)threads, 116 data_size, data, sols_size, sols, stats, 117 poll_status, poll_status_data); 118 } 119 120 STATIC_INLINE uint8_t 121 h48_prune_lookup( 122 uint64_t coord, 123 cube_t cube, 124 dfsarg_solve_h48_t arg[NON_NULL] 125 ) 126 { 127 uint8_t p, pmin, pe; 128 129 arg->table_lookups++; 130 p = get_h48_pval_and_min(arg->h48data, coord, &pmin); 131 if (p == 0) { 132 arg->table_fallbacks++; 133 pe = get_eoesep_pval_cube(arg->eoesepdata, cube); 134 return MAX(pmin, pe); 135 } else { 136 return p + arg->base; 137 } 138 } 139 140 STATIC_INLINE uint8_t 141 h48_prune_lookup_nocoord( 142 cube_t cube, 143 dfsarg_solve_h48_t arg[NON_NULL] 144 ) 145 { 146 uint32_t cdata; 147 uint64_t coord; 148 149 get_h48_cdata(cube, arg->cocsepdata, &cdata); 150 coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), arg->h); 151 return h48_prune_lookup(coord, cube, arg); 152 } 153 154 STATIC_INLINE void 155 h48_prune_pipeline( 156 dfsarg_solve_h48_t arg[NON_NULL], 157 h48_prune_t prune[SIZE(NMOVES)], 158 uint8_t target, 159 bool normal 160 ) 161 { 162 uint64_t i; 163 uint32_t cdata; 164 uint8_t m, p; 165 166 /* Stage 0: initialize the neighbors array */ 167 memset(prune, 0, NMOVES * sizeof(h48_prune_t)); 168 if (normal) { 169 for (m = 0; m < NMOVES; m++) { 170 prune[m].pi = m % 3 == 1 ? arg->lb_inverse : 0; 171 if (!(arg->movemask_normal & MM_SINGLE(m)) || 172 prune[m].pi > target) { 173 prune[m].stop = 1; 174 continue; 175 } 176 prune[m].cube = move(arg->cube, m); 177 prune[m].inverse = premove(arg->inverse, m); 178 prune[m].m = m; 179 arg->nodes_visited++; 180 } 181 } else { 182 for (m = 0; m < NMOVES; m++) { 183 prune[m].pi = m % 3 == 1 ? arg->lb_normal : 0; 184 if (!(arg->movemask_inverse & MM_SINGLE(m)) || 185 prune[m].pi > target) { 186 prune[m].stop = 1; 187 continue; 188 } 189 prune[m].cube = move(arg->inverse, m); 190 prune[m].inverse = premove(arg->cube, m); 191 prune[m].m = m; 192 arg->nodes_visited++; 193 } 194 } 195 196 /* We'll never get a bound higher than base + 3 */ 197 if (target > arg->base + 3) 198 return; 199 200 /* Stage 1: cdata and prefetch inverse */ 201 for (m = 0; m < NMOVES; m++) { 202 if (prune[m].stop) 203 continue; 204 205 p = get_h48_cdata(prune[m].inverse, arg->cocsepdata, &cdata); 206 if (p > target) { 207 prune[m].stop = 1; 208 continue; 209 } 210 if (prune[m].pi == 0) { 211 prune[m].coord = coord_h48_edges(prune[m].inverse, 212 COCLASS(cdata), TTREP(cdata), arg->h); 213 i = H48_INDEX(H48_LINE_EXT(prune[m].coord)); 214 prefetch(arg->h48data, i); 215 } 216 } 217 218 /* Stage 2: get pval from inverse, prefetch normal */ 219 for (m = 0; m < NMOVES; m++) { 220 if (prune[m].stop) 221 continue; 222 223 if (prune[m].pi == 0) { 224 prune[m].pi = h48_prune_lookup( 225 prune[m].coord, prune[m].inverse, arg); 226 if (prune[m].pi > target) { 227 prune[m].stop = 1; 228 continue; 229 } 230 } 231 232 p = get_h48_cdata(prune[m].cube, arg->cocsepdata, &cdata); 233 if (p > target) { 234 prune[m].stop = 1; 235 continue; 236 } 237 prune[m].coord = coord_h48_edges( 238 prune[m].cube, COCLASS(cdata), TTREP(cdata), arg->h); 239 i = H48_INDEX(H48_LINE_EXT(prune[m].coord)); 240 prefetch(arg->h48data, i); 241 } 242 243 /* Stage 3: get pval from normal */ 244 for (m = 0; m < NMOVES; m++) { 245 if (prune[m].stop) 246 continue; 247 248 prune[m].pn = h48_prune_lookup( 249 prune[m].coord, prune[m].cube, arg); 250 prune[m].stop = prune[m].pn > target; 251 } 252 } 253 254 STATIC_INLINE void 255 h48_prune_restore_normal( 256 const h48_prune_t prune[NON_NULL], 257 dfsarg_solve_h48_t arg[NON_NULL], 258 uint8_t target 259 ) 260 { 261 uint8_t nm; 262 263 arg->cube = prune->cube; 264 arg->inverse = prune->inverse; 265 arg->lb_inverse = prune->pi; 266 arg->lb_normal = prune->pn; 267 268 nm = arg->solution_moves->nmoves; 269 arg->solution_moves->moves[nm-1] = prune->m; 270 arg->movemask_normal = allowedmask[movebase(prune->m)]; 271 272 if (arg->lb_inverse == target) 273 arg->movemask_normal &= MM18_NOHALFTURNS; 274 if (arg->lb_normal == target) 275 arg->movemask_inverse &= MM18_NOHALFTURNS; 276 } 277 278 STATIC_INLINE void 279 h48_prune_restore_inverse( 280 const h48_prune_t prune[NON_NULL], 281 dfsarg_solve_h48_t arg[NON_NULL], 282 uint8_t target 283 ) 284 { 285 uint8_t nm; 286 287 arg->cube = prune->inverse; 288 arg->inverse = prune->cube; 289 arg->lb_inverse = prune->pn; 290 arg->lb_normal = prune->pi; 291 292 nm = arg->solution_moves->npremoves; 293 arg->solution_moves->premoves[nm-1] = prune->m; 294 arg->movemask_inverse = allowedmask[movebase(prune->m)]; 295 296 if (arg->lb_inverse == target) 297 arg->movemask_normal &= MM18_NOHALFTURNS; 298 if (arg->lb_normal == target) 299 arg->movemask_inverse &= MM18_NOHALFTURNS; 300 } 301 302 STATIC int64_t 303 solve_h48_dfs(dfsarg_solve_h48_t arg[NON_NULL]) 304 { 305 int64_t ret, n; 306 uint8_t m, nm, nn, ni, target; 307 uint64_t mm_normal, mm_inverse; 308 cube_t cube, backup_cube, backup_inverse; 309 h48_prune_t prune[NMOVES]; 310 311 if (equal(arg->cube, SOLVED_CUBE) || /* Solved before target depth */ 312 arg->solution_list->nsols >= arg->solution_settings->maxsolutions) 313 return 0; 314 315 nn = arg->solution_moves->nmoves; 316 ni = arg->solution_moves->npremoves; 317 nm = nn + ni; 318 target = arg->target_depth - (nm + 1); 319 mm_normal = arg->movemask_normal; 320 mm_inverse = arg->movemask_inverse; 321 if (target == 0) { /* Last move */ 322 arg->solution_moves->nmoves++; 323 for (m = 0; m < NMOVES; m++) { 324 if (!(mm_normal & mm_inverse & MM_SINGLE(m))) 325 continue; 326 cube = move(arg->cube, m); 327 arg->solution_moves->moves[nn] = m; 328 arg->nodes_visited++; 329 if (!equal(cube, SOLVED_CUBE)) 330 continue; 331 wrapthread_mutex_lock(arg->solutions_mutex); 332 ret = appendsolution(arg->solution_moves, 333 H48_STARTING_MOVES, arg->tmask, 334 arg->solution_settings, arg->solution_list); 335 wrapthread_mutex_unlock(arg->solutions_mutex); 336 arg->solution_moves->nmoves--; 337 return ret; 338 } 339 arg->solution_moves->nmoves--; 340 return 0; 341 } 342 343 backup_cube = arg->cube; 344 backup_inverse = arg->inverse; 345 346 ret = 0; 347 if (popcount_u64(mm_normal) <= popcount_u64(mm_inverse)) { 348 h48_prune_pipeline(arg, prune, target, true); 349 arg->solution_moves->nmoves++; 350 for (m = 0; m < NMOVES; m++) { 351 if (prune[m].stop) 352 continue; 353 arg->movemask_normal = mm_normal; 354 arg->movemask_inverse = mm_inverse; 355 h48_prune_restore_normal(&prune[m], arg, target); 356 n = solve_h48_dfs(arg); 357 if (n < 0) 358 return n; 359 ret += n; 360 } 361 arg->solution_moves->nmoves--; 362 } else { 363 h48_prune_pipeline(arg, prune, target, false); 364 arg->solution_moves->npremoves++; 365 for (m = 0; m < NMOVES; m++) { 366 if (prune[m].stop) 367 continue; 368 arg->movemask_normal = mm_normal; 369 arg->movemask_inverse = mm_inverse; 370 h48_prune_restore_inverse(&prune[m], arg, target); 371 n = solve_h48_dfs(arg); 372 if (n < 0) 373 return n; 374 ret += n; 375 } 376 arg->solution_moves->npremoves--; 377 } 378 379 arg->cube = backup_cube; 380 arg->inverse = backup_inverse; 381 arg->movemask_normal = mm_normal; 382 arg->movemask_inverse = mm_inverse; 383 384 return ret; 385 } 386 387 STATIC wrapthread_return_t 388 solve_h48_runthread(void *arg) 389 { 390 int i, j; 391 uint8_t lastmove; 392 int64_t d, f, nprev; 393 dfsarg_solve_h48_t *dfsarg; 394 395 dfsarg = (dfsarg_solve_h48_t *)arg; 396 397 nprev = 0; 398 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) { 399 if (*dfsarg->status == NISSY_STATUS_STOP) 400 goto solve_h48_runthread_end; 401 while (*dfsarg->status == NISSY_STATUS_PAUSE) 402 msleep(BASE_SLEEP_TIME); 403 404 solution_moves_reset(dfsarg->solution_moves); 405 memcpy(dfsarg->solution_moves->moves, 406 dfsarg->tasks[i].moves, H48_STARTING_MOVES); 407 dfsarg->solution_moves->nmoves = H48_STARTING_MOVES; 408 409 dfsarg->cube = dfsarg->start_cube; 410 for (j = 0; j < H48_STARTING_MOVES; j++) 411 dfsarg->cube = 412 move(dfsarg->cube, dfsarg->tasks[i].moves[j]); 413 dfsarg->inverse = inverse(dfsarg->cube); 414 415 dfsarg->nodes_visited++; 416 if (dfsarg->tasks[i].pval + H48_STARTING_MOVES 417 > dfsarg->target_depth) 418 continue; 419 420 dfsarg->lb_normal = 0; 421 dfsarg->lb_inverse = 0; 422 dfsarg->movemask_normal = allowedmask[ 423 movebase(dfsarg->tasks[i].moves[H48_STARTING_MOVES-1])]; 424 dfsarg->movemask_inverse = MM18_ALLMOVES; 425 dfsarg->tmask = dfsarg->tasks[i].tmask; 426 427 solve_h48_dfs(dfsarg); 428 429 /* 430 We compute the "rank" of each taks, which is used in the next 431 step of the IDFS to sort them. This heuristically leads us 432 faster to a solution. The rank is computed by taking the 433 number of nodes visited, adjusted by a factor of about 434 sqrt(2)/sqrt(3) because there are more sequences starting with 435 U, R and F than with D, L and B, as we don't allow e.g. both 436 U D and D U, but only U D. 437 This trick was suggested by Chen Shuang, the implementation is 438 inspired by Andrew Skalski's vcube. 439 */ 440 lastmove = dfsarg->tasks[i].moves[H48_STARTING_MOVES-1]; 441 d = (int64_t)dfsarg->nodes_visited - nprev; 442 f = movebase(lastmove) % 2 == 0 ? 47525 : 58206; 443 dfsarg->tasks[i].rank = d * f; 444 nprev = dfsarg->nodes_visited; 445 } 446 447 solve_h48_runthread_end: 448 dfsarg->thread_done = true; 449 return wrapthread_return_val; 450 } 451 452 STATIC int64_t 453 solve_h48_maketasks( 454 dfsarg_solve_h48_t solve_arg[NON_NULL], 455 dfsarg_solve_h48_maketasks_t mtarg[NON_NULL], 456 solve_h48_task_t tasks[SIZE(H48_STARTING_CUBES)], 457 int ntasks[NON_NULL] 458 ) 459 { 460 int64_t r, appret; 461 uint8_t m, t; 462 uint64_t mm; 463 cube_t backup_cube; 464 solution_moves_t moves; 465 466 if (equal(mtarg->cube, SOLVED_CUBE)) { 467 if (mtarg->nmoves > mtarg->maxmoves || 468 mtarg->nmoves < mtarg->minmoves || 469 solutions_done(solve_arg->solution_list, 470 solve_arg->solution_settings, mtarg->nmoves)) 471 return NISSY_OK; 472 473 solution_moves_reset(&moves); 474 moves.nmoves = mtarg->nmoves; 475 memcpy(moves.moves, mtarg->moves, mtarg->nmoves); 476 477 appret = appendsolution(&moves, mtarg->nmoves, mtarg->tmask, 478 solve_arg->solution_settings, solve_arg->solution_list); 479 return appret < 0 ? appret : NISSY_OK; 480 } 481 482 if (mtarg->nmoves == H48_STARTING_MOVES) { 483 tasks[*ntasks].cube = mtarg->cube; 484 tasks[*ntasks].pval = 485 h48_prune_lookup_nocoord(mtarg->cube, solve_arg); 486 memcpy(tasks[*ntasks].moves, mtarg->moves, 487 H48_STARTING_MOVES * sizeof(uint8_t)); 488 memcpy(tasks[*ntasks].tmask, mtarg->tmask, 489 H48_STARTING_MOVES * sizeof(uint64_t)); 490 (*ntasks)++; 491 return NISSY_OK; 492 } 493 494 if (mtarg->nmoves == 0) { 495 mm = MM18_ALLMOVES; 496 } else { 497 m = mtarg->moves[mtarg->nmoves-1]; 498 mm = allowedmask[movebase(m)]; 499 } 500 501 mtarg->tmask[mtarg->nmoves] = symmetry_mask(mtarg->cube); 502 503 mtarg->nmoves++; 504 backup_cube = mtarg->cube; 505 for (m = 0; m < NMOVES; m++) { 506 if (!(mm & MM_SINGLE(m))) 507 continue; 508 509 mtarg->moves[mtarg->nmoves-1] = m; 510 mtarg->cube = move(backup_cube, m); 511 r = solve_h48_maketasks(solve_arg, mtarg, tasks, ntasks); 512 if (r < 0) 513 return r; 514 515 /* Avoid symmetry-equivalent moves from the starting cube */ 516 for (t = 0; t < NTRANS; t++) 517 if (mtarg->tmask[mtarg->nmoves-1] & TM_SINGLE(t)) 518 mm &= ~MM_SINGLE(transform_move(m, t)); 519 } 520 mtarg->nmoves--; 521 mtarg->cube = backup_cube; 522 523 return NISSY_OK; 524 } 525 526 STATIC void 527 solve_h48_log_solutions(solution_list_t s[NON_NULL], size_t e) 528 { 529 size_t i; 530 char b; 531 while (e != s->used) { 532 LOG("[h48 solve] Found solution: "); 533 for (i = e; s->buf[i] != '\n' && s->buf[i] != '\0'; i++) ; 534 b = s->buf[i]; 535 s->buf[i] = '\0'; 536 LOG("%s\n", s->buf + e); 537 s->buf[i] = b; 538 e = i + 1; 539 } 540 } 541 542 STATIC int 543 solve_h48_compare_tasks(const void *x, const void *y) 544 { 545 int64_t nodes_x = ((solve_h48_task_t *)x)->rank; 546 int64_t nodes_y = ((solve_h48_task_t *)y)->rank; 547 548 /* Same as returning nodes_y - nodes_x, but avoids overflow */ 549 return (nodes_x < nodes_y) - (nodes_x > nodes_y); 550 } 551 552 STATIC int64_t 553 solve_h48( 554 oriented_cube_t oc, 555 uint8_t minmoves, 556 uint8_t maxmoves, 557 uint64_t maxsolutions, 558 uint8_t optimal, 559 uint8_t threads, 560 uint64_t data_size, 561 const unsigned char *data, 562 size_t solutions_size, 563 char *solutions, 564 long long stats[SIZE(NISSY_SIZE_SOLVE_STATS)], 565 int (*poll_status)(void *), 566 void *poll_status_data 567 ) 568 { 569 int i, ntasks; 570 bool td; 571 wrapthread_atomic int status, prev_status; 572 size_t lastused; 573 int8_t d; 574 dfsarg_solve_h48_t arg[THREADS]; 575 solve_h48_task_t tasks[H48_STARTING_CUBES]; 576 dfsarg_solve_h48_maketasks_t mtarg; 577 long double fallback_rate, lookups_per_node; 578 uint64_t offset; 579 uint64_t nodes_visited, table_lookups, table_fallbacks; 580 tableinfo_t info, fbinfo2; 581 const uint32_t *cocsepdata; 582 const unsigned char *h48data; 583 const unsigned char *eoesep; 584 solution_moves_t solution_moves[THREADS]; 585 solution_settings_t settings; 586 solution_list_t sollist; 587 wrapthread_define_var_thread_t(thread[THREADS]); 588 wrapthread_define_var_mutex_t(solutions_mutex); 589 590 if (!solution_list_init(&sollist, solutions_size, solutions)) 591 goto solve_h48_error_solutions_buffer; 592 593 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) 594 goto solve_h48_error_data; 595 596 cocsepdata = (uint32_t *)(data + INFOSIZE); 597 h48data = data + COCSEP_FULLSIZE + INFOSIZE; 598 599 /* Read additional eoesep table */ 600 offset = info.next; 601 if (readtableinfo_n(data_size, data, 3, &fbinfo2) 602 != NISSY_OK) 603 goto solve_h48_error_data; 604 605 /* Some heuristic check to see that it is eoesep */ 606 if (fbinfo2.bits != 4 || fbinfo2.type != TABLETYPE_SPECIAL) 607 goto solve_h48_error_data; 608 eoesep = h48data + offset; 609 610 settings = (solution_settings_t) { 611 .unniss = true, 612 .maxmoves = maxmoves, 613 .maxsolutions = maxsolutions, 614 .optimal = optimal, 615 .orientation = oc.orientation, 616 }; 617 618 for (i = 0; i < threads; i++) { 619 arg[i] = (dfsarg_solve_h48_t) { 620 .start_cube = oc.cube, 621 .cube = oc.cube, 622 .h = info.h48h, 623 .base = info.base, 624 .cocsepdata = cocsepdata, 625 .h48data = h48data, 626 .eoesepdata = eoesep, 627 .solution_moves = &solution_moves[i], 628 .solution_settings = &settings, 629 .solution_list = &sollist, 630 .nodes_visited = 0, 631 .table_fallbacks = 0, 632 .table_lookups = 0, 633 .threads = threads, 634 .thread_id = i, 635 .solutions_mutex = &solutions_mutex, 636 .status = &status, 637 }; 638 639 } 640 641 wrapthread_mutex_init(&solutions_mutex); 642 643 mtarg = (dfsarg_solve_h48_maketasks_t) { 644 .cube = oc.cube, 645 .nmoves = 0, 646 .minmoves = minmoves, 647 .maxmoves = maxmoves, 648 }; 649 ntasks = 0; 650 solve_h48_maketasks(&arg[0], &mtarg, tasks, &ntasks); 651 if (ntasks < 0) 652 goto solve_h48_error_solutions_buffer; 653 if (solutions_done(&sollist, &settings, 654 MAX(minmoves, H48_STARTING_MOVES))) 655 goto solve_h48_done; 656 657 for (i = 0; i < threads; i++) { 658 arg[i].ntasks = ntasks; 659 arg[i].tasks = tasks; 660 } 661 662 LOG("[H48 solve] Prepared %d tasks\n", ntasks); 663 664 solve_h48_log_solutions(&sollist, 0); 665 lastused = sollist.used; 666 status = poll_status == NULL ? NISSY_STATUS_RUN : 667 poll_status(poll_status_data); 668 if (!NISSY_CANSLEEP) { 669 LOG("[solve h48] Pause / Stop / Resume functionality won't " 670 "be available on this system (can't sleep()).\n"); 671 } 672 for ( 673 d = MAX(minmoves, H48_STARTING_MOVES + 1); 674 !(solutions_done(&sollist, &settings, d)) && 675 status != NISSY_STATUS_STOP; 676 d++ 677 ) { 678 if (d >= H48_LOG_PROGRESS_MIN_DEPTH) { 679 LOG("[H48 solve] Found %" PRIu64 " solutions, " 680 "searching at depth %" PRId8 "\n", 681 sollist.nsols, d); 682 } 683 684 if (d >= H48_SORT_TASKS_MIN_DEPTH) 685 qsort(tasks, ntasks, sizeof(solve_h48_task_t), 686 solve_h48_compare_tasks); 687 688 for (i = 0; i < threads; i++) { 689 arg[i].target_depth = d; 690 arg[i].thread_done = false; 691 wrapthread_create( 692 &thread[i], solve_h48_runthread, &arg[i]); 693 } 694 695 /* Log solutions and handle pause / stop / resume */ 696 if (poll_status != NULL && d >= 15 && NISSY_CANSLEEP) { 697 td = false; 698 while (!td && status != NISSY_STATUS_STOP) { 699 msleep(BASE_SLEEP_TIME); 700 701 wrapthread_mutex_lock(&solutions_mutex); 702 solve_h48_log_solutions(&sollist, lastused); 703 lastused = sollist.used; 704 wrapthread_mutex_unlock(&solutions_mutex); 705 706 prev_status = status; 707 status = poll_status(poll_status_data); 708 if (status != prev_status) { 709 if (status == NISSY_STATUS_PAUSE) 710 LOG("[H48 solve] Paused\n"); 711 if (status == NISSY_STATUS_RUN) 712 LOG("[H48 solve] Resumed\n"); 713 } 714 715 for (td = true, i = 0; i < threads; i++) 716 td = td && arg[i].thread_done; 717 } 718 } 719 720 for (i = 0; i < threads; i++) 721 wrapthread_join(thread[i]); 722 723 solve_h48_log_solutions(&sollist, lastused); 724 lastused = sollist.used; 725 } 726 727 if (status == NISSY_STATUS_STOP) { 728 LOG("[H48 solve] Received stop request, ending solution " 729 "search early.\n"); 730 } 731 732 solve_h48_done: 733 nodes_visited = table_lookups = table_fallbacks = 0; 734 for (i = 0; i < threads; i++) { 735 nodes_visited += arg[i].nodes_visited; 736 table_fallbacks += arg[i].table_fallbacks; 737 table_lookups += arg[i].table_lookups; 738 } 739 740 stats[0] = nodes_visited; 741 stats[1] = table_lookups; 742 stats[2] = table_fallbacks; 743 lookups_per_node = table_lookups / (long double)nodes_visited; 744 fallback_rate = nodes_visited == 0 ? 0.0 : 745 (table_fallbacks * 100) / (long double)table_lookups; 746 LOG("[H48 solve] Nodes visited: %" PRId64 "\n", nodes_visited); 747 LOG("[H48 solve] Lookups: %" PRId64 " (%.3Lf per node)\n", 748 table_lookups, lookups_per_node); 749 LOG("[H48 solve] Table fallbacks: %" PRId64 " (%.3Lf%%)\n", 750 table_fallbacks, fallback_rate); 751 752 return sollist.nsols; 753 754 solve_h48_error_data: 755 LOG("[H48 solve] Error reading data table\n"); 756 return NISSY_ERROR_DATA; 757 758 solve_h48_error_solutions_buffer: 759 return NISSY_ERROR_BUFFER_SIZE; 760 }