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