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