multisolve.h (7895B)
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 [NON_NULL], 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 [SIZE(NISSY_SIZE_SOLVE_STATS)], int (*)(void *), void *); 26 STATIC bool multicoord_solution_admissible( 27 const dfsarg_solve_multicoord_t [NON_NULL]); 28 STATIC bool multicoord_dfs_stop(const dfsarg_solve_multicoord_t [NON_NULL]); 29 STATIC int64_t solve_multicoord_dfs(dfsarg_solve_multicoord_t [NON_NULL]); 30 31 STATIC bool 32 multicoord_solution_admissible(const dfsarg_solve_multicoord_t arg[NON_NULL]) 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[NON_NULL]) 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[NON_NULL]) 73 { 74 uint8_t m, l, i; 75 uint64_t mm, 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, 1, &arg->tmask, 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 & (UINT64_C(1) << (uint64_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[SIZE(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, (uint8_t)minmoves, 166 (uint8_t)maxmoves, (uint8_t)maxsolutions, (uint8_t)optimal, 167 (uint8_t)threads, data_size, data, solutions_size, sols, 168 poll_status, poll_status_data); 169 } 170 171 STATIC int64_t 172 solve_multicoord( 173 oriented_cube_t oc, 174 multicoord_t mcoord [NON_NULL], 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 }