solve.h (9371B)
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 n, char [n], int (*)(void *), void *); 18 STATIC int64_t solve_coord_dispatch(oriented_cube_t, const char *, uint8_t, 19 uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, 20 const unsigned char *, size_t n, char [n], int (*)(void *), void *); 21 STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [static 1]); 22 STATIC bool solve_coord_dfs_stop(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 solve_coord_dfs_stop(const dfsarg_solve_coord_t arg[static 1]) 42 { 43 bool hasnissed; 44 uint8_t n, pval; 45 uint64_t coord; 46 const cube_t *c; 47 48 n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; 49 if (n >= arg->target_depth) 50 return true; 51 52 hasnissed = arg->solution_moves->nmoves > 0 && 53 arg->solution_moves->npremoves > 0; 54 if (!hasnissed && (arg->nissflag & NISSY_NISSFLAG_MIXED)) 55 return false; 56 57 c = arg->lastisnormal ? &arg->cube : &arg->inverse; 58 59 coord = arg->coord->coord(*c, arg->coord_data); 60 pval = get_coord_pval(arg->coord, arg->ptable, coord); 61 62 return n + pval > arg->target_depth; 63 } 64 65 STATIC bool 66 coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1]) 67 { 68 uint8_t f, nn, ni, th; 69 70 f = arg->nissflag; 71 nn = arg->solution_moves->nmoves; 72 ni = arg->solution_moves->npremoves; 73 th = DIV_ROUND_UP(arg->target_depth, 2); 74 75 if (nn + ni == 0) 76 return f & (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_MIXED); 77 78 if (arg->lastisnormal) 79 return (f & NISSY_NISSFLAG_NORMAL) || 80 ((f & NISSY_NISSFLAG_MIXED) && (ni > 0 || nn <= th)); 81 82 return (f & NISSY_NISSFLAG_MIXED) && nn == 0 && ni < th && 83 coord_can_switch(arg->coord, arg->coord_data, 84 ni, arg->solution_moves->premoves); 85 } 86 87 STATIC bool 88 coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1]) 89 { 90 uint8_t f, nn, ni, th; 91 92 f = arg->nissflag; 93 nn = arg->solution_moves->nmoves; 94 ni = arg->solution_moves->npremoves; 95 th = DIV_ROUND_UP(arg->target_depth, 2); 96 97 if (nn + ni == 0) 98 return f & (NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED); 99 100 if (!arg->lastisnormal) 101 return (f & NISSY_NISSFLAG_INVERSE) || 102 ((f & NISSY_NISSFLAG_MIXED) && (nn > 0 || ni < th)); 103 104 return (f & NISSY_NISSFLAG_MIXED) && ni == 0 && nn <= th && 105 coord_can_switch(arg->coord, arg->coord_data, 106 nn, arg->solution_moves->moves); 107 } 108 109 STATIC int64_t 110 solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) 111 { 112 bool lastbackup; 113 uint8_t m, l, nnbackup, nibackup; 114 uint32_t mm; 115 uint64_t coord; 116 int64_t n, ret; 117 cube_t backup_cube, backup_inverse; 118 119 coord = arg->coord->coord(arg->cube, arg->coord_data); 120 if (coord == 0) { 121 if (!coord_solution_admissible(arg)) 122 return 0; 123 return appendsolution(arg->solution_moves, 124 arg->solution_settings, arg->solution_list, true, 125 arg->coord->name); 126 } 127 128 if (solve_coord_dfs_stop(arg)) 129 return 0; 130 131 backup_cube = arg->cube; 132 backup_inverse = arg->inverse; 133 lastbackup = arg->lastisnormal; 134 nnbackup = arg->solution_moves->nmoves; 135 nibackup = arg->solution_moves->npremoves; 136 137 ret = 0; 138 if (coord_continue_onnormal(arg)) { 139 l = arg->solution_moves->nmoves; 140 mm = arg->coord->moves_mask; 141 if (l != 0) { 142 m = arg->solution_moves->moves[l-1]; 143 mm &= allowedmask[movebase(m)]; 144 } 145 arg->solution_moves->nmoves++; 146 arg->lastisnormal = true; 147 148 for (m = 0; m < NMOVES; m++) { 149 if (!(mm & (UINT32_C(1) << (uint32_t)m))) 150 continue; 151 152 arg->solution_moves->moves[l] = m; 153 arg->cube = move(backup_cube, m); 154 arg->inverse = premove(backup_inverse, m); 155 n = solve_coord_dfs(arg); 156 if (n < 0) 157 return n; 158 ret += n; 159 arg->solution_moves->npremoves = nibackup; 160 } 161 162 arg->solution_moves->nmoves--; 163 } 164 165 arg->lastisnormal = lastbackup; 166 167 if (coord_continue_oninverse(arg)) { 168 l = arg->solution_moves->npremoves; 169 mm = arg->coord->moves_mask; 170 if (l != 0) { 171 m = arg->solution_moves->premoves[l-1]; 172 mm &= allowedmask[movebase(m)]; 173 } 174 arg->solution_moves->npremoves++; 175 arg->lastisnormal = false; 176 177 for (m = 0; m < NMOVES; m++) { 178 if (!(mm & (UINT32_C(1) << (uint32_t)m))) 179 continue; 180 181 arg->solution_moves->premoves[l] = m; 182 arg->inverse = move(backup_inverse, m); 183 arg->cube = premove(backup_cube, m); 184 n = solve_coord_dfs(arg); 185 if (n < 0) 186 return n; 187 ret += n; 188 arg->solution_moves->nmoves = nnbackup; 189 } 190 191 arg->solution_moves->npremoves--; 192 } 193 194 arg->cube = backup_cube; 195 arg->inverse = backup_inverse; 196 arg->lastisnormal = lastbackup; 197 198 return ret; 199 } 200 201 STATIC int64_t 202 solve_coord_dispatch( 203 oriented_cube_t oc, 204 const char *coord_and_axis, 205 uint8_t nissflag, 206 uint8_t minmoves, 207 uint8_t maxmoves, 208 uint64_t maxsolutions, 209 uint8_t optimal, 210 uint8_t threads, 211 uint64_t data_size, 212 const unsigned char *data, 213 size_t solutions_size, 214 char sols[solutions_size], 215 int (*poll_status)(void *), 216 void *poll_status_data 217 ) 218 { 219 coord_t *coord; 220 uint8_t axis; 221 222 parse_coord_and_axis( 223 strlen(coord_and_axis), coord_and_axis, &coord, &axis); 224 225 if (coord == NULL) { 226 LOG("Error: could not parse coordinate from '%s'\n", 227 coord_and_axis); 228 return NISSY_ERROR_INVALID_SOLVER; 229 } 230 231 if (axis == UINT8_ERROR) { 232 LOG("Error: could not parse axis from '%s'\n", coord_and_axis); 233 return NISSY_ERROR_INVALID_SOLVER; 234 } 235 236 return solve_coord(oc, coord, axis, nissflag, minmoves, maxmoves, 237 maxsolutions, optimal, threads, data_size, data, 238 solutions_size, sols, poll_status, poll_status_data); 239 } 240 241 STATIC int64_t 242 solve_coord( 243 oriented_cube_t oc, 244 coord_t coord [static 1], 245 uint8_t axis, 246 uint8_t nissflag, 247 uint8_t minmoves, 248 uint8_t maxmoves, 249 uint64_t maxsolutions, 250 uint8_t optimal, 251 uint8_t threads, 252 uint64_t data_size, 253 const unsigned char *data, 254 size_t solutions_size, 255 char sols[solutions_size], 256 int (*poll_status)(void *), 257 void *poll_status_data 258 ) 259 { 260 int8_t d; 261 uint8_t t; 262 int64_t ndepth; 263 cube_t c; 264 const unsigned char *coord_data; 265 const unsigned char *ptable; 266 dfsarg_solve_coord_t arg; 267 tableinfo_t info; 268 solution_moves_t solution_moves; 269 solution_settings_t solution_settings; 270 solution_list_t solution_list; 271 272 t = coord->axistrans[axis]; 273 c = transform(oc.cube, t); 274 275 if (!coord->is_solvable(c)) 276 goto solve_coord_error_unsolvable; 277 278 if (!solution_list_init(&solution_list, solutions_size, sols)) 279 goto solve_coord_error_buffer; 280 281 if (readtableinfo(data_size, data, &info) != NISSY_OK) 282 goto solve_coord_error_data; 283 284 if (info.type == TABLETYPE_PRUNING) { 285 /* Only the pruning table */ 286 coord_data = NULL; 287 ptable = data + INFOSIZE; 288 } else { 289 /* Coordinate has extra data */ 290 coord_data = data + INFOSIZE; 291 ptable = data + info.next + INFOSIZE; 292 } 293 294 solution_moves_reset(&solution_moves); 295 296 solution_settings = (solution_settings_t) { 297 .tmask = TM_SINGLE(inverse_trans(t)), 298 .unniss = false, 299 .maxmoves = maxmoves, 300 .maxsolutions = maxsolutions, 301 .optimal = optimal, 302 .orientation = oc.orientation, 303 }; 304 305 arg = (dfsarg_solve_coord_t) { 306 .cube = c, 307 .inverse = inverse(c), 308 .coord = coord, 309 .coord_data = coord_data, 310 .ptable = ptable, 311 .solution_moves = &solution_moves, 312 .solution_settings = &solution_settings, 313 .solution_list = &solution_list, 314 .nissflag = nissflag, 315 316 /* 317 Since no move has been done yet, this field should be 318 neither true nor false; using its value now is logically 319 undefined behavior. 320 TODO: find a more elegant solution 321 */ 322 .lastisnormal = true, 323 }; 324 325 if (coord->coord(c, coord_data) == 0) { 326 if (minmoves == 0 && !appendsolution(&solution_moves, 327 &solution_settings, &solution_list, true, coord->name)) 328 goto solve_coord_error_buffer; 329 goto solve_coord_done; 330 } 331 332 for ( 333 d = MAX(minmoves, 1); 334 !solutions_done(&solution_list, &solution_settings, d); 335 d++ 336 ) { 337 if (d >= 12) 338 LOG("[%s solve] Found %" PRIu64 " solutions, " 339 "searching at depth %" PRId8 "\n", 340 coord->name, solution_list.nsols, d); 341 342 arg.target_depth = d; 343 solution_moves_reset(arg.solution_moves); 344 ndepth = solve_coord_dfs(&arg); 345 346 if (ndepth < 0) 347 return ndepth; 348 349 solution_list.nsols += (uint64_t)ndepth; 350 } 351 352 solve_coord_done: 353 return (int64_t)solution_list.nsols; 354 355 solve_coord_error_data: 356 LOG("[%s solve] Error reading table\n", coord->name); 357 return NISSY_ERROR_DATA; 358 359 solve_coord_error_buffer: 360 LOG("[%s solve] Error appending solution to buffer: size too small\n", 361 coord->name); 362 return NISSY_ERROR_BUFFER_SIZE; 363 364 solve_coord_error_unsolvable: 365 LOG("[%s solve] Error: cube not ready\n", coord->name); 366 return NISSY_ERROR_UNSOLVABLE_CUBE; 367 }