solve.h (13746B)
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 } dfsarg_solve_h48_t; 39 40 typedef struct { 41 cube_t cube; 42 int8_t nmoves; 43 uint8_t moves[STARTING_MOVES]; 44 int8_t minmoves; 45 int8_t maxmoves; 46 int8_t *shortest_sol; 47 } dfsarg_solve_h48_maketasks_t; 48 49 STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]); 50 STATIC int64_t solve_h48_maketasks( 51 dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], 52 solve_h48_task_t [static STARTING_CUBES], int [static 1]); 53 STATIC void *solve_h48_runthread(void *); 54 STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]); 55 STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint8_t, uint8_t, 56 uint8_t, uint64_t, const unsigned char *, size_t n, char [n], 57 long long [static NISSY_SIZE_SOLVE_STATS]); 58 59 STATIC_INLINE bool 60 solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) 61 { 62 uint32_t data, data_inv; 63 int64_t coord; 64 int8_t target, nh, n; 65 uint8_t pval_cocsep, pval_eoesep; 66 67 n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; 68 target = arg->target_depth - n; 69 if (target <= 0 || 70 arg->solution_list->nsols >= arg->solution_settings->maxsolutions || 71 n > arg->solution_list->shortest_sol + 72 arg->solution_settings->optimal) 73 return true; 74 75 arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES; 76 arg->nodes_visited++; 77 78 /* Preliminary probing using last computed bound, if possible */ 79 80 if ((arg->use_lb_normal && arg->lb_normal > target) || 81 (arg->use_lb_inverse && arg->lb_inverse > target)) 82 return true; 83 84 /* Preliminary corner probing */ 85 86 if (get_h48_cdata(arg->cube, arg->cocsepdata, &data) > target || 87 get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv) > target) 88 return true; 89 90 /* Inverse probing */ 91 92 if (!arg->use_lb_inverse) { 93 coord = coord_h48_edges( 94 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h); 95 arg->lb_inverse = get_h48_pval(arg->h48data, coord, arg->k); 96 arg->table_lookups++; 97 98 if (arg->k == 2 && arg->lb_inverse == 0) { 99 arg->table_fallbacks++; 100 101 pval_cocsep = get_h48_pval( 102 arg->h48data_fallback_h0k4, coord >> arg->h, 4); 103 pval_eoesep = get_eoesep_pval_cube( 104 arg->h48data_fallback_eoesep, arg->inverse); 105 arg->lb_inverse = MAX(pval_cocsep, pval_eoesep); 106 } else { 107 arg->lb_inverse += arg->base; 108 } 109 110 arg->use_lb_inverse = true; 111 } 112 113 if (arg->lb_inverse > target) 114 return true; 115 nh = arg->lb_inverse == target; 116 arg->movemask_normal = nh * MM18_NOHALFTURNS + (1-nh) * MM18_ALLMOVES; 117 118 /* Normal probing */ 119 120 if (!arg->use_lb_normal) { 121 coord = coord_h48_edges( 122 arg->cube, COCLASS(data), TTREP(data), arg->h); 123 arg->lb_normal = get_h48_pval(arg->h48data, coord, arg->k); 124 arg->table_lookups++; 125 126 if (arg->k == 2 && arg->lb_normal == 0) { 127 arg->table_fallbacks++; 128 129 pval_cocsep = get_h48_pval( 130 arg->h48data_fallback_h0k4, coord >> arg->h, 4); 131 pval_eoesep = get_eoesep_pval_cube( 132 arg->h48data_fallback_eoesep, arg->cube); 133 arg->lb_normal = MAX(pval_cocsep, pval_eoesep); 134 } else { 135 arg->lb_normal += arg->base; 136 } 137 138 arg->use_lb_normal = true; 139 } 140 141 if (arg->lb_normal > target) 142 return true; 143 nh = arg->lb_normal == target; 144 arg->movemask_inverse = nh * MM18_NOHALFTURNS + (1-nh) * MM18_ALLMOVES; 145 146 return false; 147 } 148 149 STATIC int64_t 150 solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) 151 { 152 int64_t ret, n; 153 uint8_t m, nm, lbn, lbi; 154 uint64_t mm_normal, mm_inverse; 155 bool ulbi, ulbn; 156 cube_t backup_cube, backup_inverse; 157 158 if (equal(arg->cube, SOLVED_CUBE)) { 159 nm = arg->solution_moves->nmoves 160 + arg->solution_moves->npremoves; 161 if (arg->target_depth != nm) 162 return 0; 163 pthread_mutex_lock(arg->solutions_mutex); 164 ret = appendsolution(arg->solution_moves, 165 arg->solution_settings, arg->solution_list, true, "H48"); 166 pthread_mutex_unlock(arg->solutions_mutex); 167 return ret; 168 } 169 170 if (solve_h48_stop(arg)) 171 return 0; 172 173 backup_cube = arg->cube; 174 backup_inverse = arg->inverse; 175 lbn = arg->lb_normal; 176 lbi = arg->lb_inverse; 177 ulbn = arg->use_lb_normal; 178 ulbi = arg->use_lb_inverse; 179 180 ret = 0; 181 mm_normal = arg->movemask_normal; 182 if (arg->solution_moves->nmoves > 0) { 183 m = arg->solution_moves->moves[arg->solution_moves->nmoves-1]; 184 mm_normal &= allowedmask[movebase(m)]; 185 } 186 mm_inverse = arg->movemask_inverse; 187 if (arg->solution_moves->npremoves > 0) { 188 m = arg->solution_moves->premoves[arg->solution_moves->npremoves-1]; 189 mm_inverse &= allowedmask[movebase(m)]; 190 } 191 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { 192 arg->solution_moves->nmoves++; 193 for (m = 0; m < 18; m++) { 194 if (!(mm_normal & MM_SINGLE(m))) 195 continue; 196 arg->solution_moves->moves[ 197 arg->solution_moves->nmoves-1] = m; 198 arg->cube = move(backup_cube, m); 199 arg->inverse = premove(backup_inverse, m); 200 arg->lb_inverse = lbi; 201 arg->use_lb_normal = false; 202 arg->use_lb_inverse = ulbi && m % 3 == 1; 203 n = solve_h48_dfs(arg); 204 if (n < 0) 205 return n; 206 ret += n; 207 } 208 arg->solution_moves->nmoves--; 209 } else { 210 arg->solution_moves->npremoves++; 211 for (m = 0; m < 18; m++) { 212 if(!(mm_inverse & MM_SINGLE(m))) 213 continue; 214 arg->solution_moves->premoves[ 215 arg->solution_moves->npremoves-1] = m; 216 arg->inverse = move(backup_inverse, m); 217 arg->cube = premove(backup_cube, m); 218 arg->lb_normal = lbn; 219 arg->use_lb_inverse = false; 220 arg->use_lb_normal = ulbn && m % 3 == 1; 221 n = solve_h48_dfs(arg); 222 if (n < 0) 223 return n; 224 ret += n; 225 } 226 arg->solution_moves->npremoves--; 227 } 228 229 arg->cube = backup_cube; 230 arg->inverse = backup_inverse; 231 232 return ret; 233 } 234 235 STATIC void * 236 solve_h48_runthread(void *arg) 237 { 238 int i, j; 239 solve_h48_task_t task; 240 dfsarg_solve_h48_t *dfsarg; 241 242 dfsarg = (dfsarg_solve_h48_t *)arg; 243 244 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) { 245 task = dfsarg->tasks[i]; 246 247 solution_moves_reset(dfsarg->solution_moves); 248 memcpy( 249 dfsarg->solution_moves->moves, task.moves, STARTING_MOVES); 250 dfsarg->solution_moves->nmoves = STARTING_MOVES; 251 252 dfsarg->cube = dfsarg->start_cube; 253 for (j = 0; j < STARTING_MOVES; j++) 254 dfsarg->cube = move(dfsarg->cube, task.moves[j]); 255 dfsarg->inverse = inverse(dfsarg->cube); 256 257 dfsarg->lb_normal = 0; 258 dfsarg->lb_inverse = 0; 259 dfsarg->use_lb_normal = false; 260 dfsarg->use_lb_inverse = false; 261 dfsarg->movemask_normal = MM18_ALLMOVES; 262 dfsarg->movemask_inverse = MM18_ALLMOVES; 263 264 solve_h48_dfs(dfsarg); 265 } 266 267 return NULL; 268 } 269 270 STATIC int64_t 271 solve_h48_maketasks( 272 dfsarg_solve_h48_t solve_arg[static 1], 273 dfsarg_solve_h48_maketasks_t maketasks_arg[static 1], 274 solve_h48_task_t tasks[static STARTING_CUBES], 275 int ntasks[static 1] 276 ) 277 { 278 int r; 279 int64_t appret; 280 uint8_t m, t; 281 uint64_t mm; 282 cube_t backup_cube; 283 solution_moves_t moves; 284 285 if (equal(maketasks_arg->cube, SOLVED_CUBE)) { 286 if (maketasks_arg->nmoves > maketasks_arg->maxmoves || 287 maketasks_arg->nmoves < maketasks_arg->minmoves || 288 solutions_done(solve_arg->solution_list, 289 solve_arg->solution_settings, maketasks_arg->nmoves)) 290 return NISSY_OK; 291 292 solution_moves_reset(&moves); 293 moves.nmoves = maketasks_arg->nmoves; 294 memcpy(moves.moves, 295 maketasks_arg->moves, maketasks_arg->nmoves); 296 297 appret = appendsolution(&moves, solve_arg->solution_settings, 298 solve_arg->solution_list, true, "H48"); 299 return appret < 0 ? appret : NISSY_OK; 300 } 301 302 if (maketasks_arg->nmoves == STARTING_MOVES) { 303 tasks[*ntasks].cube = maketasks_arg->cube; 304 memcpy(tasks[*ntasks].moves, 305 maketasks_arg->moves, STARTING_MOVES); 306 (*ntasks)++; 307 return NISSY_OK; 308 } 309 310 if (maketasks_arg->nmoves == 0) { 311 mm = MM18_ALLMOVES; 312 } else { 313 m = maketasks_arg->moves[maketasks_arg->nmoves-1]; 314 mm = allowedmask[movebase(m)]; 315 } 316 317 maketasks_arg->nmoves++; 318 backup_cube = maketasks_arg->cube; 319 for (m = 0; m < 18; m++) { 320 if (!(mm & MM_SINGLE(m))) 321 continue; 322 maketasks_arg->moves[maketasks_arg->nmoves-1] = m; 323 maketasks_arg->cube = move(backup_cube, m); 324 r = solve_h48_maketasks( 325 solve_arg, maketasks_arg, tasks, ntasks); 326 if (r < 0) 327 return r; 328 329 /* Avoid symmetry-equivalent moves from the starting cube */ 330 if (maketasks_arg->nmoves == 1) 331 for (t = 0; t < NTRANS; t++) 332 if (solve_arg->solution_settings->tmask & 333 TM_SINGLE(t)) 334 mm &= ~MM_SINGLE(transform_move(m, t)); 335 } 336 maketasks_arg->nmoves--; 337 maketasks_arg->cube = backup_cube; 338 339 return NISSY_OK; 340 } 341 342 STATIC int64_t 343 solve_h48( 344 oriented_cube_t oc, 345 uint8_t minmoves, 346 uint8_t maxmoves, 347 uint8_t maxsolutions, 348 uint8_t optimal, 349 uint8_t threads, 350 uint64_t data_size, 351 const unsigned char *data, 352 size_t solutions_size, 353 char solutions[solutions_size], 354 long long stats[static NISSY_SIZE_SOLVE_STATS] 355 ) 356 { 357 int i, ntasks, eoesep_table_index; 358 int8_t d; 359 dfsarg_solve_h48_t arg[THREADS]; 360 solve_h48_task_t tasks[STARTING_CUBES]; 361 dfsarg_solve_h48_maketasks_t maketasks_arg; 362 long double fallback_rate, lookups_per_node; 363 uint64_t offset; 364 int64_t nodes_visited, table_lookups, table_fallbacks; 365 tableinfo_t info, fbinfo, fbinfo2; 366 const uint32_t *cocsepdata; 367 const unsigned char *fallback, *h48data; 368 const unsigned char *fallback2; 369 solution_moves_t solution_moves[THREADS]; 370 solution_settings_t settings; 371 solution_list_t sollist; 372 pthread_t thread[THREADS]; 373 pthread_mutex_t solutions_mutex; 374 375 if (!solution_list_init(&sollist, solutions_size, solutions)) 376 goto solve_h48_error_solutions_buffer; 377 378 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) 379 goto solve_h48_error_data; 380 381 cocsepdata = (uint32_t *)(data + INFOSIZE); 382 h48data = data + COCSEP_FULLSIZE + INFOSIZE; 383 384 /* Read fallback table(s) */ 385 fallback = NULL; 386 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK) 387 goto solve_h48_error_data; 388 offset = info.next; 389 eoesep_table_index = 3; 390 if (info.bits == 2) { 391 /* We only support h0k4 as fallback table */ 392 if (fbinfo.h48h != 0 || fbinfo.bits != 4) 393 goto solve_h48_error_data; 394 fallback = h48data + offset; 395 offset += fbinfo.next; 396 eoesep_table_index++; 397 } 398 399 if (readtableinfo_n(data_size, data, eoesep_table_index, &fbinfo2) 400 != NISSY_OK) 401 goto solve_h48_error_data; 402 403 /* Some heuristic check to see that it is eoesep */ 404 if (fbinfo2.bits != 4 || fbinfo2.type != TABLETYPE_SPECIAL) 405 goto solve_h48_error_data; 406 fallback2 = h48data + offset; 407 408 settings = (solution_settings_t) { 409 .tmask = symmetry_mask(oc.cube), 410 .unniss = true, 411 .maxmoves = maxmoves, 412 .maxsolutions = maxsolutions, 413 .optimal = optimal, 414 .orientation = oc.orientation, 415 }; 416 417 for (i = 0; i < threads; i++) { 418 arg[i] = (dfsarg_solve_h48_t) { 419 .start_cube = oc.cube, 420 .cube = oc.cube, 421 .h = info.h48h, 422 .k = info.bits, 423 .base = info.base, 424 .cocsepdata = cocsepdata, 425 .h48data = h48data, 426 .h48data_fallback_h0k4 = fallback, 427 .h48data_fallback_eoesep = fallback2, 428 .solution_moves = &solution_moves[i], 429 .solution_settings = &settings, 430 .solution_list = &sollist, 431 .nodes_visited = 0, 432 .table_fallbacks = 0, 433 .table_lookups = 0, 434 .threads = threads, 435 .thread_id = i, 436 .solutions_mutex = &solutions_mutex, 437 }; 438 439 } 440 441 pthread_mutex_init(&solutions_mutex, NULL); 442 443 maketasks_arg = (dfsarg_solve_h48_maketasks_t) { 444 .cube = oc.cube, 445 .nmoves = 0, 446 .minmoves = minmoves, 447 .maxmoves = maxmoves, 448 }; 449 ntasks = 0; 450 solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks); 451 if (ntasks < 0) 452 goto solve_h48_error_solutions_buffer; 453 if (solutions_done(&sollist, &settings, MAX(minmoves, STARTING_MOVES))) 454 goto solve_h48_done; 455 456 for (i = 0; i < threads; i++) { 457 arg[i].ntasks = ntasks; 458 arg[i].tasks = tasks; 459 } 460 461 LOG("[H48 solve] Prepared %d tasks\n", ntasks); 462 463 for ( 464 d = MAX(minmoves, STARTING_MOVES + 1); 465 !solutions_done(&sollist, &settings, d); 466 d++ 467 ) { 468 if (d >= 15) 469 LOG("[H48 solve] Found %" PRId64 " solutions, " 470 "searching at depth %" PRId8 "\n", 471 sollist.nsols, d); 472 for (i = 0; i < threads; i++) { 473 arg[i].target_depth = d; 474 pthread_create( 475 &thread[i], NULL, solve_h48_runthread, &arg[i]); 476 } 477 for (i = 0; i < threads; i++) 478 pthread_join(thread[i], NULL); 479 } 480 481 solve_h48_done: 482 nodes_visited = table_lookups = table_fallbacks = 0; 483 for (i = 0; i < threads; i++) { 484 nodes_visited += arg[i].nodes_visited; 485 table_fallbacks += arg[i].table_fallbacks; 486 table_lookups += arg[i].table_lookups; 487 } 488 489 stats[0] = nodes_visited; 490 stats[1] = table_lookups; 491 stats[2] = table_fallbacks; 492 lookups_per_node = table_lookups / (long double)nodes_visited; 493 fallback_rate = nodes_visited == 0 ? 0.0 : 494 (table_fallbacks * 100) / (long double)table_lookups; 495 LOG("[H48 solve] Nodes visited: %" PRId64 "\n", nodes_visited); 496 LOG("[H48 solve] Lookups: %" PRId64 " (%.3Lf per node)\n", 497 table_lookups, lookups_per_node); 498 LOG("[H48 solve] Table fallbacks: %" PRId64 " (%.3Lf%%)\n", 499 table_fallbacks, fallback_rate); 500 501 return sollist.nsols; 502 503 solve_h48_error_data: 504 LOG("[H48 solve] Error reading data table\n"); 505 return NISSY_ERROR_DATA; 506 507 solve_h48_error_solutions_buffer: 508 return NISSY_ERROR_BUFFER_SIZE; 509 }