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