solve.h (10381B)
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 [NON_NULL], 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 [SIZE(NISSY_SIZE_SOLVE_STATS)], int (*)(void *), void *); 23 STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [NON_NULL]); 24 STATIC bool coord_continue_onnormal(const dfsarg_solve_coord_t [NON_NULL]); 25 STATIC bool coord_continue_oninverse(const dfsarg_solve_coord_t [NON_NULL]); 26 STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t [NON_NULL]); 27 28 STATIC bool 29 coord_solution_admissible(const dfsarg_solve_coord_t arg[NON_NULL]) 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[NON_NULL]) 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[NON_NULL]) 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[NON_NULL]) 151 { 152 bool lastbackup; 153 uint8_t m, l, nnbackup, nibackup, nmoves; 154 uint64_t mm, 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, 1, &arg->tmask, 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 & (UINT64_C(1) << (uint64_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 & (UINT64_C(1) << (uint64_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[SIZE(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, (uint8_t)nissflag, 283 (uint8_t)minmoves, (uint8_t)maxmoves, (uint8_t)maxsolutions, 284 (uint8_t)optimal, (uint8_t)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 [NON_NULL], 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 }