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