solve.h (10337B)
1 typedef struct { 2 cube_t cube; 3 cube_t inverse; 4 uint8_t target_depth; 5 solution_moves_t *solution_moves; 6 uint64_t tmask; 7 solution_settings_t *solution_settings; 8 solution_list_t *solution_list; 9 uint8_t nissflag; 10 bool lastisnormal; 11 coord_t *coord; 12 const unsigned char *coord_data; 13 const unsigned char *ptable; 14 } dfsarg_solve_coord_t; 15 16 STATIC int64_t solve_coord(oriented_cube_t, coord_t [static 1], uint8_t, 17 uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, 18 const unsigned char *, size_t, char *, int (*)(void *), void *); 19 STATIC long long solve_coord_dispatch(oriented_cube_t, const char *, unsigned, 20 unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long, 21 const unsigned char *, unsigned, char *, 22 long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); 23 STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [static 1]); 24 STATIC bool coord_continue_onnormal(const dfsarg_solve_coord_t [static 1]); 25 STATIC bool coord_continue_oninverse(const dfsarg_solve_coord_t [static 1]); 26 STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t [static 1]); 27 28 STATIC bool 29 coord_solution_admissible(const dfsarg_solve_coord_t arg[static 1]) 30 { 31 uint8_t n; 32 33 n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; 34 if (arg->target_depth != n) 35 return false; 36 37 return arg->coord->is_admissible == NULL || 38 arg->coord->is_admissible(arg->solution_moves); 39 } 40 41 STATIC bool 42 coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1]) 43 { 44 uint8_t flag, nn, ni, swbound_n, swbound_i, pval; 45 uint64_t coord; 46 47 flag = arg->nissflag; 48 nn = arg->solution_moves->nmoves; 49 ni = arg->solution_moves->npremoves; 50 swbound_n = arg->target_depth / 2; 51 swbound_i = DIV_ROUND_UP(arg->target_depth, 2) - 1; 52 53 /* If only inverse moves are allowed */ 54 if (flag == NISSY_NISSFLAG_INVERSE) 55 return false; 56 57 /* Pruning table check */ 58 if (!(flag & NISSY_NISSFLAG_MIXED) || ni != 0) { 59 coord = arg->coord->coord(arg->cube, arg->coord_data); 60 pval = get_coord_pval(arg->coord, arg->ptable, coord); 61 if (nn + ni + pval > arg->target_depth) 62 return false; 63 } 64 65 /* It's the first move */ 66 if (nn + ni == 0) 67 return true; 68 69 if (arg->lastisnormal) { 70 /* Can continue if we have already switched */ 71 if (ni > 0) 72 return true; 73 74 /* Check that we have enough moves left to switch */ 75 return flag & NISSY_NISSFLAG_NORMAL || nn < swbound_n; 76 } else { 77 /* Don't switch if not allowed */ 78 if (!(flag & NISSY_NISSFLAG_MIXED)) 79 return false; 80 81 /* Forbid switching multiple times */ 82 if (nn > 0) 83 return false; 84 85 /* Some coordinates are not allowed to switch */ 86 if (!coord_can_switch(arg->coord, arg->coord_data, 87 ni, arg->solution_moves->premoves)) 88 return false; 89 90 /* Only switch before half solution is found */ 91 return ni <= swbound_i; 92 } 93 } 94 95 STATIC bool 96 coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1]) 97 { 98 uint8_t flag, nn, ni, swbound_n, swbound_i, pval; 99 uint64_t coord; 100 101 flag = arg->nissflag; 102 nn = arg->solution_moves->nmoves; 103 ni = arg->solution_moves->npremoves; 104 swbound_n = arg->target_depth / 2; 105 swbound_i = DIV_ROUND_UP(arg->target_depth, 2) - 1; 106 107 /* If only normal moves are allowed */ 108 if (flag == NISSY_NISSFLAG_NORMAL) 109 return false; 110 111 /* Pruning table check */ 112 if (!(flag & NISSY_NISSFLAG_MIXED) || nn != 0) { 113 coord = arg->coord->coord(arg->inverse, arg->coord_data); 114 pval = get_coord_pval(arg->coord, arg->ptable, coord); 115 if (nn + ni + pval > arg->target_depth) 116 return false; 117 } 118 119 /* It's the first move */ 120 if (nn + ni == 0) 121 return true; 122 123 if (!arg->lastisnormal) { 124 /* Can continue if we have already switched */ 125 if (nn > 0) 126 return true; 127 128 /* Check that we have enough moves left to switch */ 129 return flag & NISSY_NISSFLAG_INVERSE || ni < swbound_i; 130 } else { 131 /* Don't switch if not allowed */ 132 if (!(flag & NISSY_NISSFLAG_MIXED)) 133 return false; 134 135 /* Forbid switching multiple times */ 136 if (ni > 0) 137 return false; 138 139 /* Some coordinates are not allowed to switch */ 140 if (!coord_can_switch(arg->coord, arg->coord_data, 141 nn, arg->solution_moves->moves)) 142 return false; 143 144 /* Only switch before half solution is found */ 145 return nn <= swbound_n; 146 } 147 } 148 149 STATIC int64_t 150 solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) 151 { 152 bool lastbackup; 153 uint8_t m, l, nnbackup, nibackup, nmoves; 154 uint32_t mm; 155 uint64_t coord; 156 int64_t n, ret; 157 cube_t backup_cube, backup_inverse; 158 159 if (arg->coord->solution_prune != NULL && 160 arg->coord->solution_prune(arg->solution_moves)) 161 return 0; 162 163 coord = arg->coord->coord(arg->cube, arg->coord_data); 164 if (coord_is_solved(arg->coord, coord, arg->coord_data)) { 165 if (!coord_solution_admissible(arg)) 166 return 0; 167 return appendsolution(arg->solution_moves, 1, &arg->tmask, 168 arg->solution_settings, arg->solution_list); 169 } 170 171 backup_cube = arg->cube; 172 backup_inverse = arg->inverse; 173 lastbackup = arg->lastisnormal; 174 nnbackup = arg->solution_moves->nmoves; 175 nibackup = arg->solution_moves->npremoves; 176 nmoves = nnbackup + nibackup; 177 178 if (nmoves >= arg->target_depth) 179 return 0; 180 181 ret = 0; 182 if (coord_continue_onnormal(arg)) { 183 l = arg->solution_moves->nmoves; 184 mm = arg->coord->moves_mask_solve; 185 if (l != 0) { 186 m = arg->solution_moves->moves[l-1]; 187 mm &= allowedmask[movebase(m)]; 188 } 189 arg->solution_moves->nmoves++; 190 arg->lastisnormal = true; 191 192 for (m = 0; m < NMOVES; m++) { 193 if (!(mm & (UINT32_C(1) << (uint32_t)m))) 194 continue; 195 196 arg->solution_moves->moves[l] = m; 197 arg->cube = move(backup_cube, m); 198 arg->inverse = premove(backup_inverse, m); 199 n = solve_coord_dfs(arg); 200 if (n < 0) 201 return n; 202 ret += n; 203 arg->solution_moves->npremoves = nibackup; 204 } 205 206 arg->solution_moves->nmoves--; 207 } 208 209 arg->cube = backup_cube; 210 arg->inverse = backup_inverse; 211 arg->lastisnormal = lastbackup; 212 213 if (coord_continue_oninverse(arg)) { 214 l = arg->solution_moves->npremoves; 215 mm = arg->coord->moves_mask_solve; 216 if (l != 0) { 217 m = arg->solution_moves->premoves[l-1]; 218 mm &= allowedmask[movebase(m)]; 219 } 220 arg->solution_moves->npremoves++; 221 arg->lastisnormal = false; 222 223 for (m = 0; m < NMOVES; m++) { 224 if (!(mm & (UINT32_C(1) << (uint32_t)m))) 225 continue; 226 227 arg->solution_moves->premoves[l] = m; 228 arg->inverse = move(backup_inverse, m); 229 arg->cube = premove(backup_cube, m); 230 n = solve_coord_dfs(arg); 231 if (n < 0) 232 return n; 233 ret += n; 234 arg->solution_moves->nmoves = nnbackup; 235 } 236 237 arg->solution_moves->npremoves--; 238 } 239 240 arg->cube = backup_cube; 241 arg->inverse = backup_inverse; 242 arg->lastisnormal = lastbackup; 243 244 return ret; 245 } 246 247 STATIC long long 248 solve_coord_dispatch( 249 oriented_cube_t oc, 250 const char *coord_and_trans, 251 unsigned nissflag, 252 unsigned minmoves, 253 unsigned maxmoves, 254 unsigned maxsolutions, 255 unsigned optimal, 256 unsigned threads, 257 unsigned long long data_size, 258 const unsigned char *data, 259 unsigned solutions_size, 260 char *sols, 261 long long stats[static NISSY_SIZE_SOLVE_STATS], 262 int (*poll_status)(void *), 263 void *poll_status_data 264 ) 265 { 266 coord_t *coord; 267 uint8_t trans; 268 269 parse_coord_and_trans(coord_and_trans, &coord, NULL, &trans); 270 271 if (coord == NULL) { 272 LOG("Error: could not parse coordinate from '%s'\n", 273 coord_and_trans); 274 return NISSY_ERROR_INVALID_SOLVER; 275 } 276 277 if (trans == UINT8_ERROR) { 278 LOG("Error: could not parse transformation from '%s'\n", 279 coord_and_trans); 280 return NISSY_ERROR_INVALID_SOLVER; 281 } 282 283 return solve_coord(oc, coord, trans, nissflag, minmoves, maxmoves, 284 maxsolutions, optimal, threads, data_size, data, 285 solutions_size, sols, poll_status, poll_status_data); 286 } 287 288 STATIC int64_t 289 solve_coord( 290 oriented_cube_t oc, 291 coord_t coord [static 1], 292 uint8_t trans, 293 uint8_t nissflag, 294 uint8_t minmoves, 295 uint8_t maxmoves, 296 uint64_t maxsolutions, 297 uint8_t optimal, 298 uint8_t threads, 299 uint64_t data_size, 300 const unsigned char *data, 301 size_t solutions_size, 302 char *sols, 303 int (*poll_status)(void *), 304 void *poll_status_data 305 ) 306 { 307 int8_t d; 308 uint64_t i; 309 int64_t err; 310 cube_t c; 311 const unsigned char *coord_data; 312 const unsigned char *ptable; 313 dfsarg_solve_coord_t arg; 314 tableinfo_t info; 315 solution_moves_t solution_moves; 316 solution_settings_t solution_settings; 317 solution_list_t solution_list; 318 319 c = transform(oc.cube, trans); 320 321 if (!coord->is_solvable(c)) 322 goto solve_coord_error_unsolvable; 323 324 if (!solution_list_init(&solution_list, solutions_size, sols)) 325 goto solve_coord_error_buffer; 326 327 if (readtableinfo(data_size, data, &info) != NISSY_OK) 328 goto solve_coord_error_data; 329 330 if (info.type == TABLETYPE_PRUNING) { 331 /* Only the pruning table */ 332 coord_data = NULL; 333 ptable = data + INFOSIZE; 334 } else { 335 /* Coordinate has extra data */ 336 coord_data = data + INFOSIZE; 337 ptable = data + info.next + INFOSIZE; 338 } 339 340 solution_moves_reset(&solution_moves); 341 342 solution_settings = (solution_settings_t) { 343 .unniss = false, 344 .maxmoves = maxmoves, 345 .maxsolutions = maxsolutions, 346 .optimal = optimal, 347 .orientation = oc.orientation, 348 }; 349 350 arg = (dfsarg_solve_coord_t) { 351 .cube = c, 352 .inverse = inverse(c), 353 .coord = coord, 354 .coord_data = coord_data, 355 .ptable = ptable, 356 .solution_moves = &solution_moves, 357 .solution_settings = &solution_settings, 358 .tmask = TM_SINGLE(inverse_trans(trans)), 359 .solution_list = &solution_list, 360 .nissflag = nissflag, 361 }; 362 363 i = coord->coord(c, coord_data); 364 if (coord_is_solved(coord, i, coord_data)) { 365 if (minmoves == 0 && !appendsolution(&solution_moves, 1, 366 &arg.tmask, &solution_settings, &solution_list)) 367 goto solve_coord_error_buffer; 368 goto solve_coord_done; 369 } 370 371 for ( 372 d = MAX(minmoves, 1); 373 !solutions_done(&solution_list, &solution_settings, d); 374 d++ 375 ) { 376 if (d >= 12) 377 LOG("[%s solve] Found %" PRIu64 " solutions, " 378 "searching at depth %" PRId8 "\n", 379 coord->name, solution_list.nsols, d); 380 381 arg.target_depth = d; 382 solution_moves_reset(arg.solution_moves); 383 if ((err = solve_coord_dfs(&arg)) < 0) 384 return err; 385 } 386 387 solve_coord_done: 388 return (int64_t)solution_list.nsols; 389 390 solve_coord_error_data: 391 LOG("[%s solve] Error reading table\n", coord->name); 392 return NISSY_ERROR_DATA; 393 394 solve_coord_error_buffer: 395 LOG("[%s solve] Error appending solution to buffer: size too small\n", 396 coord->name); 397 return NISSY_ERROR_BUFFER_SIZE; 398 399 solve_coord_error_unsolvable: 400 LOG("[%s solve] Error: cube not ready\n", coord->name); 401 return NISSY_ERROR_UNSOLVABLE_CUBE; 402 }