multisolve.h (7815B)
1 /* 2 For now the only multicoordinate is DRFIN, and this solver reflects this. 3 For example, NISS is not available. 4 */ 5 6 typedef struct { 7 cube_t cube; 8 cube_t inverse; 9 uint8_t target_depth; 10 solution_moves_t *solution_moves; 11 solution_settings_t *solution_settings; 12 solution_list_t *solution_list; 13 multicoord_t *mcoord; 14 const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS]; 15 const unsigned char *ptable[MAX_MULTICOORD_NCOORDS]; 16 } dfsarg_solve_multicoord_t; 17 18 STATIC int64_t solve_multicoord(oriented_cube_t, multicoord_t [static 1], 19 uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, 20 const unsigned char *, size_t, char *, int (*)(void *), void *); 21 STATIC long long solve_multicoord_dispatch(oriented_cube_t, const char *, 22 unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, 23 unsigned long long, const unsigned char *, unsigned, char *, 24 long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); 25 STATIC bool multicoord_solution_admissible( 26 const dfsarg_solve_multicoord_t [static 1]); 27 STATIC bool multicoord_dfs_stop(const dfsarg_solve_multicoord_t [static 1]); 28 STATIC int64_t solve_multicoord_dfs(dfsarg_solve_multicoord_t [static 1]); 29 30 STATIC bool 31 multicoord_solution_admissible(const dfsarg_solve_multicoord_t arg[static 1]) 32 { 33 uint8_t n, i; 34 const coord_t *c; 35 36 n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; 37 if (arg->target_depth != n) 38 return false; 39 40 for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) { 41 c = arg->mcoord->coordinates[i]; 42 if (c->is_admissible != NULL && 43 !c->is_admissible(arg->solution_moves)) 44 return false; 45 } 46 47 return true; 48 } 49 50 STATIC bool 51 multicoord_dfs_stop(const dfsarg_solve_multicoord_t arg[static 1]) 52 { 53 uint8_t pval, i; 54 uint64_t cval; 55 const coord_t *c; 56 57 for (i = 0, pval = 0; arg->mcoord->coordinates[i] != NULL; i++) { 58 c = arg->mcoord->coordinates[i]; 59 60 cval = c->coord(arg->cube, arg->coord_data[i]); 61 pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval)); 62 63 cval = c->coord(arg->inverse, arg->coord_data[i]); 64 pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval)); 65 } 66 67 return arg->solution_moves->nmoves + pval > arg->target_depth; 68 } 69 70 STATIC int64_t 71 solve_multicoord_dfs(dfsarg_solve_multicoord_t arg[static 1]) 72 { 73 uint8_t m, l, i; 74 uint32_t mm; 75 uint64_t coord; 76 int64_t n, ret; 77 const coord_t *c; 78 cube_t backup_cube, backup_inverse; 79 80 for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) { 81 c = arg->mcoord->coordinates[i]; 82 coord = c->coord(arg->cube, arg->coord_data[i]); 83 if (!coord_is_solved(c, coord, arg->coord_data[i])) 84 goto solve_multicoord_dfs_notsolved; 85 } 86 87 /* All coordinates are solved */ 88 if (!multicoord_solution_admissible(arg)) 89 return 0; 90 return appendsolution(arg->solution_moves, 91 arg->solution_settings, arg->solution_list); 92 93 solve_multicoord_dfs_notsolved: 94 if (multicoord_dfs_stop(arg)) 95 return 0; 96 97 backup_cube = arg->cube; 98 backup_inverse = arg->inverse; 99 ret = 0; 100 101 l = arg->solution_moves->nmoves; 102 mm = arg->mcoord->moves_mask; 103 if (l != 0) { 104 m = arg->solution_moves->moves[l-1]; 105 mm &= allowedmask[movebase(m)]; 106 } 107 arg->solution_moves->nmoves++; 108 109 for (m = 0; m < NMOVES; m++) { 110 if (!(mm & (UINT32_C(1) << (uint32_t)m))) 111 continue; 112 113 arg->solution_moves->moves[l] = m; 114 arg->cube = move(backup_cube, m); 115 arg->inverse = premove(backup_inverse, m); 116 n = solve_multicoord_dfs(arg); 117 if (n < 0) 118 return n; 119 ret += n; 120 } 121 122 arg->solution_moves->nmoves--; 123 arg->cube = backup_cube; 124 arg->inverse = backup_inverse; 125 126 return ret; 127 } 128 129 STATIC long long 130 solve_multicoord_dispatch( 131 oriented_cube_t oc, 132 const char *coord_and_trans, 133 unsigned nissflag, 134 unsigned minmoves, 135 unsigned maxmoves, 136 unsigned maxsolutions, 137 unsigned optimal, 138 unsigned threads, 139 unsigned long long data_size, 140 const unsigned char *data, 141 unsigned solutions_size, 142 char *sols, 143 long long stats[static NISSY_SIZE_SOLVE_STATS], 144 int (*poll_status)(void *), 145 void *poll_status_data 146 ) 147 { 148 multicoord_t *mcoord; 149 uint8_t trans; 150 151 parse_coord_and_trans(coord_and_trans, NULL, &mcoord, &trans); 152 153 if (mcoord == NULL) { 154 LOG("Error: could not parse coordinate from '%s'\n", 155 coord_and_trans); 156 return NISSY_ERROR_INVALID_SOLVER; 157 } 158 159 if (trans == UINT8_ERROR) { 160 LOG("Error: could not parse transformation from '%s'\n", 161 coord_and_trans); 162 return NISSY_ERROR_INVALID_SOLVER; 163 } 164 165 return solve_multicoord(oc, mcoord, trans, minmoves, 166 maxmoves, maxsolutions, optimal, threads, data_size, data, 167 solutions_size, sols, poll_status, poll_status_data); 168 } 169 170 STATIC int64_t 171 solve_multicoord( 172 oriented_cube_t oc, 173 multicoord_t mcoord [static 1], 174 uint8_t trans, 175 uint8_t minmoves, 176 uint8_t maxmoves, 177 uint64_t maxsolutions, 178 uint8_t optimal, 179 uint8_t threads, 180 uint64_t data_size, 181 const unsigned char *data, 182 size_t solutions_size, 183 char *sols, 184 int (*poll_status)(void *), 185 void *poll_status_data 186 ) 187 { 188 int8_t d; 189 size_t j, of; 190 uint64_t i; 191 int64_t err; 192 cube_t c; 193 const coord_t *coord; 194 dfsarg_solve_multicoord_t arg; 195 tableinfo_t info; 196 solution_moves_t solution_moves; 197 solution_settings_t solution_settings; 198 solution_list_t solution_list; 199 200 c = transform(oc.cube, trans); 201 202 if (!mcoord->is_solvable(c)) 203 goto solve_multicoord_error_unsolvable; 204 205 if (!solution_list_init(&solution_list, solutions_size, sols)) 206 goto solve_multicoord_error_buffer; 207 208 solution_moves_reset(&solution_moves); 209 210 solution_settings = (solution_settings_t) { 211 .tmask = TM_SINGLE(inverse_trans(trans)), 212 .unniss = false, 213 .maxmoves = maxmoves, 214 .maxsolutions = maxsolutions, 215 .optimal = optimal, 216 .orientation = oc.orientation, 217 }; 218 219 arg = (dfsarg_solve_multicoord_t) { 220 .cube = c, 221 .inverse = inverse(c), 222 .mcoord = mcoord, 223 .solution_moves = &solution_moves, 224 .solution_settings = &solution_settings, 225 .solution_list = &solution_list, 226 }; 227 228 for (j = 0, of = INFOSIZE; mcoord->coordinates[j] != NULL; j++) { 229 if (readtableinfo(data_size-of, data+of, &info) != NISSY_OK) 230 goto solve_multicoord_error_data; 231 232 if (info.type == TABLETYPE_PRUNING) { 233 /* Only the pruning table */ 234 arg.coord_data[j] = NULL; 235 arg.ptable[j] = data + of + INFOSIZE; 236 of += info.fullsize; 237 } else { 238 /* Coordinate has extra data */ 239 arg.coord_data[j] = data + of + INFOSIZE; 240 arg.ptable[j] = data + of + info.next + INFOSIZE; 241 of += info.fullsize; 242 if (readtableinfo(data_size-of, data+of, &info) 243 != NISSY_OK) 244 goto solve_multicoord_error_data; 245 of += info.fullsize; 246 } 247 248 /* Skip padding */ 249 while (of % 8 != 0) 250 of++; 251 } 252 253 for (j = 0; mcoord->coordinates[j] != NULL; j++) { 254 coord = mcoord->coordinates[j]; 255 i = coord->coord(c, arg.coord_data[j]); 256 if (!coord_is_solved(coord, i, arg.coord_data[j])) 257 goto solve_multicoord_notsolved; 258 } 259 260 /* All coordinates are solved */ 261 if (minmoves == 0 && !appendsolution(&solution_moves, 262 &solution_settings, &solution_list)) 263 goto solve_multicoord_error_buffer; 264 goto solve_multicoord_done; 265 266 solve_multicoord_notsolved: 267 for ( 268 d = MAX(minmoves, 1); 269 !solutions_done(&solution_list, &solution_settings, d); 270 d++ 271 ) { 272 if (d >= 12) 273 LOG("[%s solve] Found %" PRIu64 " solutions, " 274 "searching at depth %" PRId8 "\n", 275 mcoord->name, solution_list.nsols, d); 276 277 arg.target_depth = d; 278 solution_moves_reset(arg.solution_moves); 279 if ((err = solve_multicoord_dfs(&arg)) < 0) 280 return err; 281 } 282 283 solve_multicoord_done: 284 return (int64_t)solution_list.nsols; 285 286 solve_multicoord_error_data: 287 LOG("[%s solve] Error reading table\n", mcoord->name); 288 return NISSY_ERROR_DATA; 289 290 solve_multicoord_error_buffer: 291 LOG("[%s solve] Error appending solution to buffer: size too small\n", 292 mcoord->name); 293 return NISSY_ERROR_BUFFER_SIZE; 294 295 solve_multicoord_error_unsolvable: 296 LOG("[%s solve] Error: cube not ready\n", mcoord->name); 297 return NISSY_ERROR_UNSOLVABLE_CUBE; 298 }