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