solutions.h (8476B)
1 STATIC void solution_moves_reset(solution_moves_t [static 1]); 2 STATIC void solution_moves_transform(solution_moves_t [static 1], size_t, 3 uint8_t); 4 STATIC void solution_moves_reorient(solution_moves_t [static 1], uint8_t); 5 STATIC bool solution_list_init(solution_list_t [static 1], size_t, char *); 6 STATIC bool solution_moves_equal( 7 const solution_moves_t [static 1], const solution_moves_t [static 1]); 8 STATIC bool last_solution_is_duplicate(const solution_list_t [static 1]); 9 STATIC bool appendchar(solution_list_t [static 1], char); 10 STATIC bool appendnormal( 11 const solution_moves_t [static 1], solution_list_t [static 1]); 12 STATIC bool appendinverse( 13 const solution_moves_t [static 1], solution_list_t [static 1]); 14 STATIC void appendsolution_dfs(const solution_moves_t [static 1], size_t, 15 const uint64_t *, size_t, uint8_t *, const solution_settings_t [static 1], 16 solution_list_t [static 1], 17 solution_moves_t [static NTRANS * SOLUTION_MAXLEN], int64_t [static 1]); 18 STATIC int64_t appendsolution(const solution_moves_t [static 1], 19 size_t, const uint64_t *, const solution_settings_t [static 1], 20 solution_list_t [static 1]); 21 STATIC bool solutions_done(const solution_list_t [static 1], 22 const solution_settings_t [static 1], int8_t depth); 23 24 STATIC void 25 solution_moves_reset(solution_moves_t sol[static 1]) 26 { 27 sol->nmoves = 0; 28 sol->npremoves = 0; 29 } 30 31 STATIC void 32 solution_moves_transform(solution_moves_t moves[static 1], size_t z, uint8_t t) 33 { 34 uint8_t i; 35 36 for (i = z; i < moves->nmoves; i++) 37 moves->moves[i] = transform_move(moves->moves[i], t); 38 39 for (i = 0; i < moves->npremoves; i++) 40 moves->premoves[i] = transform_move(moves->premoves[i], t); 41 } 42 43 STATIC void 44 solution_moves_reorient(solution_moves_t moves[static 1], uint8_t or) 45 { 46 uint8_t i; 47 48 for (i = 0; i < moves->nmoves; i++) 49 moves->moves[i] = 50 inverse_reorient_move(moves->moves[i], or); 51 52 for (i = 0; i < moves->npremoves; i++) 53 moves->premoves[i] = 54 inverse_reorient_move(moves->premoves[i], or); 55 } 56 57 STATIC bool 58 solution_list_init(solution_list_t sols[static 1], size_t n, char *buf) 59 { 60 if (n == 0) 61 return false; 62 63 sols->nsols = 0; 64 sols->shortest_sol = SOLUTION_MAXLEN + 1; 65 sols->size = n; 66 sols->used = 0; 67 sols->buf = buf; 68 sols->buf[0] = '\0'; 69 70 return true; 71 } 72 73 STATIC bool 74 solution_moves_equal( 75 const solution_moves_t a[static 1], 76 const solution_moves_t b[static 1] 77 ) 78 { 79 uint8_t i; 80 81 if (a->nmoves != b->nmoves || a->npremoves != b->npremoves) 82 return false; 83 84 for (i = 0; i < a->nmoves; i++) 85 if (a->moves[i] != b->moves[i]) 86 return false; 87 88 for (i = 0; i < a->npremoves; i++) 89 if (a->premoves[i] != b->premoves[i]) 90 return false; 91 92 return true; 93 } 94 95 STATIC bool 96 last_solution_is_duplicate(const solution_list_t l[static 1]) 97 { 98 size_t i, j; 99 100 if (l->nsols == 1) 101 return false; 102 103 /* We assume the list is newline-terminated */ 104 j = l->used-2; 105 while (true) { 106 for ( ; l->buf[j] != '\n'; j--) 107 if (j == 0) return false; 108 j--; 109 for (i = l->used-2; l->buf[i] == l->buf[j]; i--, j--) { 110 if (l->buf[i-1] == '\n') { 111 if (l->buf[j-1] == '\n' || j == 0) 112 return true; 113 else break; 114 } 115 } 116 } 117 118 return false; 119 } 120 121 STATIC bool 122 appendchar(solution_list_t solutions[static 1], char c) 123 { 124 if (solutions->size <= solutions->used) 125 return false; 126 127 solutions->buf[solutions->used++] = c; 128 129 return true; 130 } 131 132 STATIC bool 133 appendnormal( 134 const solution_moves_t moves[static 1], 135 solution_list_t list[static 1] 136 ) 137 { 138 int64_t strl; 139 140 if (moves->nmoves == 0) 141 return true; 142 143 if ((strl = writemoves(moves->nmoves, moves->moves, 144 list->size - list->used, list->buf + list->used)) < 0) 145 return false; 146 list->used += strl; 147 148 return true; 149 } 150 151 STATIC bool 152 appendinverse( 153 const solution_moves_t moves[static 1], 154 solution_list_t list[static 1] 155 ) 156 { 157 int64_t strl; 158 159 if (moves->npremoves == 0) 160 return true; 161 162 if (!appendchar(list, '(')) 163 return false; 164 165 if ((strl = writemoves(moves->npremoves, moves->premoves, 166 list->size - list->used, list->buf + list->used)) < 0) 167 return false; 168 list->used += strl; 169 170 return appendchar(list, ')'); 171 } 172 173 STATIC void 174 appendsolution_dfs( 175 const solution_moves_t moves[static 1], 176 size_t ntmask, 177 const uint64_t *tmask, 178 size_t itm, 179 uint8_t *tt, 180 const solution_settings_t settings[static 1], 181 solution_list_t list[static 1], 182 solution_moves_t tsol[static NTRANS * SOLUTION_MAXLEN], 183 int64_t r[static 1] 184 ) 185 { 186 /* 187 The logic here is quit complex because we have to address H48 188 solutions that may be reduced by symmetry in the first few moves. 189 */ 190 191 size_t i, last_start; 192 uint8_t t; 193 solution_moves_t moves_copy; 194 195 if (list->nsols >= settings->maxsolutions) 196 return; 197 198 if (ntmask == itm) { 199 tsol[*r] = *moves; 200 201 for (i = ntmask; i > 0; i--) 202 solution_moves_transform(&tsol[*r], i-1, tt[i-1]); 203 204 solution_moves_reorient(&tsol[*r], settings->orientation); 205 sortparallel_moves(tsol[*r].nmoves, tsol[*r].moves); 206 sortparallel_moves(tsol[*r].npremoves, tsol[*r].premoves); 207 208 last_start = list->used; 209 210 /* Append first the moves on the side that has more */ 211 /* E.g. write (U L F) B instead of B (U L F) */ 212 if (tsol[*r].nmoves >= tsol[*r].npremoves) { 213 if (!appendnormal(&tsol[*r], list)) 214 goto appendsolution_dfs_error_buffer; 215 216 if (tsol[*r].nmoves > 0 && tsol[*r].npremoves > 0) 217 if (!appendchar(list, ' ')) 218 goto appendsolution_dfs_error_buffer; 219 220 if (!appendinverse(&tsol[*r], list)) 221 goto appendsolution_dfs_error_buffer; 222 } else { 223 if (!appendinverse(&tsol[*r], list)) 224 goto appendsolution_dfs_error_buffer; 225 226 if (tsol[*r].nmoves > 0 && tsol[*r].npremoves > 0) 227 if (!appendchar(list, ' ')) 228 goto appendsolution_dfs_error_buffer; 229 230 if (!appendnormal(&tsol[*r], list)) 231 goto appendsolution_dfs_error_buffer; 232 } 233 234 if (!appendchar(list, '\n')) 235 goto appendsolution_dfs_error_buffer; 236 ++list->nsols; 237 238 /* 239 Normaly, it would be enough to check for duplicates in the 240 current "pack" of transformation-equivalent solutions. 241 However, in rare cases, the H48 solver may produce equivalent 242 "packs" of solutions. It would be more elegant to filter out 243 the corresponding tasks in solve_h48_maketasks(), but doing so 244 is not trivial. In the end, duplicate solutions are never 245 desirable, so we might as well do this clean up here. 246 */ 247 if (last_solution_is_duplicate(list)) { 248 --list->nsols; 249 list->used = last_start; 250 return; 251 } 252 253 list->shortest_sol = MIN( 254 list->shortest_sol, tsol[*r].nmoves + tsol[*r].npremoves); 255 (*r)++; 256 } else { 257 for (t = 0; t < NTRANS; t++) { 258 if (!(tmask[itm] & TM_SINGLE(t))) 259 continue; 260 moves_copy = *moves; 261 tt[itm] = t; 262 appendsolution_dfs(&moves_copy, ntmask, tmask, 263 itm+1, tt, settings, list, tsol, r); 264 if (*r < 0) 265 return; 266 } 267 } 268 269 return; 270 271 appendsolution_dfs_error_buffer: 272 list->buf[0] = '\0'; 273 *r = NISSY_ERROR_BUFFER_SIZE; 274 return; 275 } 276 277 STATIC int64_t 278 appendsolution( 279 const solution_moves_t moves[static 1], 280 size_t ntmask, 281 const uint64_t *tmask, 282 const solution_settings_t settings[static 1], 283 solution_list_t list[static 1] 284 ) 285 { 286 int64_t r; 287 int i; 288 uint8_t tt[SOLUTION_MAXLEN]; 289 solution_moves_t moves_copy, tsol[NTRANS * SOLUTION_MAXLEN]; 290 291 if (moves->nmoves + moves->npremoves > SOLUTION_MAXLEN) 292 goto appendsolution_error_solution_length; 293 294 moves_copy = *moves; 295 if (settings->unniss) { 296 moves_copy.nmoves += moves->npremoves; 297 moves_copy.npremoves = 0; 298 for (i = moves->npremoves-1; i >= 0; i--) 299 moves_copy.moves[moves_copy.nmoves - i - 1] = 300 inverse_move(moves->premoves[i]); 301 302 /* 303 This is a bit ugly: we have to sort now and then again 304 later, because the allowedmoves check would fail with 305 improperly sorted parallel moves, but then transforming 306 could swap the pairs the wrong way around. 307 */ 308 sortparallel_moves(moves_copy.nmoves, moves_copy.moves); 309 310 /* Check if unnissed premoves cancel with normal. */ 311 if (!allowedmoves(moves_copy.nmoves, moves_copy.moves)) 312 return 0; 313 } 314 315 r = 0; 316 memset(tt, TRANS_UFr, SOLUTION_MAXLEN); 317 appendsolution_dfs( 318 &moves_copy, ntmask, tmask, 0, tt, settings, list, tsol, &r); 319 if (r < 0) 320 return r; 321 322 list->buf[list->used] = '\0'; 323 return r; 324 325 appendsolution_error_solution_length: 326 list->buf[0] = '\0'; 327 return NISSY_ERROR_UNKNOWN; 328 } 329 330 STATIC bool 331 solutions_done( 332 const solution_list_t list[static 1], 333 const solution_settings_t settings[static 1], 334 int8_t depth 335 ) 336 { 337 return depth > settings->maxmoves || 338 depth > list->shortest_sol + settings->optimal || 339 list->nsols >= settings->maxsolutions; 340 }