diff options
Diffstat (limited to 'src/solvers')
| -rw-r--r-- | src/solvers/coord/multisolve.h | 9 | ||||
| -rw-r--r-- | src/solvers/coord/solve.h | 9 | ||||
| -rw-r--r-- | src/solvers/h48/solve.h | 78 | ||||
| -rw-r--r-- | src/solvers/solutions.h | 224 | ||||
| -rw-r--r-- | src/solvers/solutions_types_macros.h | 1 |
5 files changed, 203 insertions, 118 deletions
diff --git a/src/solvers/coord/multisolve.h b/src/solvers/coord/multisolve.h index f3589e8..a45bd6a 100644 --- a/src/solvers/coord/multisolve.h +++ b/src/solvers/coord/multisolve.h | |||
| @@ -9,6 +9,7 @@ typedef struct { | |||
| 9 | uint8_t target_depth; | 9 | uint8_t target_depth; |
| 10 | solution_moves_t *solution_moves; | 10 | solution_moves_t *solution_moves; |
| 11 | solution_settings_t *solution_settings; | 11 | solution_settings_t *solution_settings; |
| 12 | uint64_t tmask; | ||
| 12 | solution_list_t *solution_list; | 13 | solution_list_t *solution_list; |
| 13 | multicoord_t *mcoord; | 14 | multicoord_t *mcoord; |
| 14 | const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS]; | 15 | const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS]; |
| @@ -87,7 +88,7 @@ solve_multicoord_dfs(dfsarg_solve_multicoord_t arg[static 1]) | |||
| 87 | /* All coordinates are solved */ | 88 | /* All coordinates are solved */ |
| 88 | if (!multicoord_solution_admissible(arg)) | 89 | if (!multicoord_solution_admissible(arg)) |
| 89 | return 0; | 90 | return 0; |
| 90 | return appendsolution(arg->solution_moves, | 91 | return appendsolution(arg->solution_moves, 1, &arg->tmask, |
| 91 | arg->solution_settings, arg->solution_list); | 92 | arg->solution_settings, arg->solution_list); |
| 92 | 93 | ||
| 93 | solve_multicoord_dfs_notsolved: | 94 | solve_multicoord_dfs_notsolved: |
| @@ -208,7 +209,6 @@ solve_multicoord( | |||
| 208 | solution_moves_reset(&solution_moves); | 209 | solution_moves_reset(&solution_moves); |
| 209 | 210 | ||
| 210 | solution_settings = (solution_settings_t) { | 211 | solution_settings = (solution_settings_t) { |
| 211 | .tmask = TM_SINGLE(inverse_trans(trans)), | ||
| 212 | .unniss = false, | 212 | .unniss = false, |
| 213 | .maxmoves = maxmoves, | 213 | .maxmoves = maxmoves, |
| 214 | .maxsolutions = maxsolutions, | 214 | .maxsolutions = maxsolutions, |
| @@ -222,6 +222,7 @@ solve_multicoord( | |||
| 222 | .mcoord = mcoord, | 222 | .mcoord = mcoord, |
| 223 | .solution_moves = &solution_moves, | 223 | .solution_moves = &solution_moves, |
| 224 | .solution_settings = &solution_settings, | 224 | .solution_settings = &solution_settings, |
| 225 | .tmask = TM_SINGLE(inverse_trans(trans)), | ||
| 225 | .solution_list = &solution_list, | 226 | .solution_list = &solution_list, |
| 226 | }; | 227 | }; |
| 227 | 228 | ||
| @@ -258,8 +259,8 @@ solve_multicoord( | |||
| 258 | } | 259 | } |
| 259 | 260 | ||
| 260 | /* All coordinates are solved */ | 261 | /* All coordinates are solved */ |
| 261 | if (minmoves == 0 && !appendsolution(&solution_moves, | 262 | if (minmoves == 0 && !appendsolution(&solution_moves, 1, |
| 262 | &solution_settings, &solution_list)) | 263 | &arg.tmask, &solution_settings, &solution_list)) |
| 263 | goto solve_multicoord_error_buffer; | 264 | goto solve_multicoord_error_buffer; |
| 264 | goto solve_multicoord_done; | 265 | goto solve_multicoord_done; |
| 265 | 266 | ||
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index 54309b1..9ea6d1a 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h | |||
| @@ -3,6 +3,7 @@ typedef struct { | |||
| 3 | cube_t inverse; | 3 | cube_t inverse; |
| 4 | uint8_t target_depth; | 4 | uint8_t target_depth; |
| 5 | solution_moves_t *solution_moves; | 5 | solution_moves_t *solution_moves; |
| 6 | uint64_t tmask; | ||
| 6 | solution_settings_t *solution_settings; | 7 | solution_settings_t *solution_settings; |
| 7 | solution_list_t *solution_list; | 8 | solution_list_t *solution_list; |
| 8 | uint8_t nissflag; | 9 | uint8_t nissflag; |
| @@ -163,7 +164,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) | |||
| 163 | if (coord_is_solved(arg->coord, coord, arg->coord_data)) { | 164 | if (coord_is_solved(arg->coord, coord, arg->coord_data)) { |
| 164 | if (!coord_solution_admissible(arg)) | 165 | if (!coord_solution_admissible(arg)) |
| 165 | return 0; | 166 | return 0; |
| 166 | return appendsolution(arg->solution_moves, | 167 | return appendsolution(arg->solution_moves, 1, &arg->tmask, |
| 167 | arg->solution_settings, arg->solution_list); | 168 | arg->solution_settings, arg->solution_list); |
| 168 | } | 169 | } |
| 169 | 170 | ||
| @@ -339,7 +340,6 @@ solve_coord( | |||
| 339 | solution_moves_reset(&solution_moves); | 340 | solution_moves_reset(&solution_moves); |
| 340 | 341 | ||
| 341 | solution_settings = (solution_settings_t) { | 342 | solution_settings = (solution_settings_t) { |
| 342 | .tmask = TM_SINGLE(inverse_trans(trans)), | ||
| 343 | .unniss = false, | 343 | .unniss = false, |
| 344 | .maxmoves = maxmoves, | 344 | .maxmoves = maxmoves, |
| 345 | .maxsolutions = maxsolutions, | 345 | .maxsolutions = maxsolutions, |
| @@ -355,14 +355,15 @@ solve_coord( | |||
| 355 | .ptable = ptable, | 355 | .ptable = ptable, |
| 356 | .solution_moves = &solution_moves, | 356 | .solution_moves = &solution_moves, |
| 357 | .solution_settings = &solution_settings, | 357 | .solution_settings = &solution_settings, |
| 358 | .tmask = TM_SINGLE(inverse_trans(trans)), | ||
| 358 | .solution_list = &solution_list, | 359 | .solution_list = &solution_list, |
| 359 | .nissflag = nissflag, | 360 | .nissflag = nissflag, |
| 360 | }; | 361 | }; |
| 361 | 362 | ||
| 362 | i = coord->coord(c, coord_data); | 363 | i = coord->coord(c, coord_data); |
| 363 | if (coord_is_solved(coord, i, coord_data)) { | 364 | if (coord_is_solved(coord, i, coord_data)) { |
| 364 | if (minmoves == 0 && !appendsolution(&solution_moves, | 365 | if (minmoves == 0 && !appendsolution(&solution_moves, 1, |
| 365 | &solution_settings, &solution_list)) | 366 | &arg.tmask, &solution_settings, &solution_list)) |
| 366 | goto solve_coord_error_buffer; | 367 | goto solve_coord_error_buffer; |
| 367 | goto solve_coord_done; | 368 | goto solve_coord_done; |
| 368 | } | 369 | } |
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index bf10723..ad66fd4 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h | |||
| @@ -13,6 +13,7 @@ typedef struct { | |||
| 13 | cube_t cube; | 13 | cube_t cube; |
| 14 | uint8_t moves[H48_STARTING_MOVES]; | 14 | uint8_t moves[H48_STARTING_MOVES]; |
| 15 | int64_t rank; | 15 | int64_t rank; |
| 16 | uint64_t tmask[H48_STARTING_MOVES]; | ||
| 16 | } solve_h48_task_t; | 17 | } solve_h48_task_t; |
| 17 | 18 | ||
| 18 | typedef struct { | 19 | typedef struct { |
| @@ -22,6 +23,7 @@ typedef struct { | |||
| 22 | int8_t target_depth; | 23 | int8_t target_depth; |
| 23 | solution_moves_t *solution_moves; | 24 | solution_moves_t *solution_moves; |
| 24 | solution_settings_t *solution_settings; | 25 | solution_settings_t *solution_settings; |
| 26 | const uint64_t *tmask; | ||
| 25 | solution_list_t *solution_list; | 27 | solution_list_t *solution_list; |
| 26 | int8_t lb_normal; | 28 | int8_t lb_normal; |
| 27 | int8_t lb_inverse; | 29 | int8_t lb_inverse; |
| @@ -55,6 +57,7 @@ typedef struct { | |||
| 55 | int8_t minmoves; | 57 | int8_t minmoves; |
| 56 | int8_t maxmoves; | 58 | int8_t maxmoves; |
| 57 | int8_t *shortest_sol; | 59 | int8_t *shortest_sol; |
| 60 | uint64_t tmask[H48_STARTING_MOVES]; | ||
| 58 | } dfsarg_solve_h48_maketasks_t; | 61 | } dfsarg_solve_h48_maketasks_t; |
| 59 | 62 | ||
| 60 | STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, | 63 | STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, |
| @@ -69,7 +72,7 @@ STATIC void *solve_h48_runthread(void *); | |||
| 69 | STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]); | 72 | STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]); |
| 70 | STATIC void solve_h48_log_solutions(solution_list_t [static 1], size_t); | 73 | STATIC void solve_h48_log_solutions(solution_list_t [static 1], size_t); |
| 71 | STATIC int solve_h48_compare_tasks(const void *, const void *); | 74 | STATIC int solve_h48_compare_tasks(const void *, const void *); |
| 72 | STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint8_t, uint8_t, | 75 | STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint64_t, uint8_t, |
| 73 | uint8_t, uint64_t, const unsigned char *, size_t, char *, | 76 | uint8_t, uint64_t, const unsigned char *, size_t, char *, |
| 74 | long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); | 77 | long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); |
| 75 | 78 | ||
| @@ -208,8 +211,8 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) | |||
| 208 | if (arg->target_depth != nm) | 211 | if (arg->target_depth != nm) |
| 209 | return 0; | 212 | return 0; |
| 210 | wrapthread_mutex_lock(arg->solutions_mutex); | 213 | wrapthread_mutex_lock(arg->solutions_mutex); |
| 211 | ret = appendsolution(arg->solution_moves, | 214 | ret = appendsolution(arg->solution_moves, H48_STARTING_MOVES, |
| 212 | arg->solution_settings, arg->solution_list); | 215 | arg->tmask, arg->solution_settings, arg->solution_list); |
| 213 | wrapthread_mutex_unlock(arg->solutions_mutex); | 216 | wrapthread_mutex_unlock(arg->solutions_mutex); |
| 214 | return ret; | 217 | return ret; |
| 215 | } | 218 | } |
| @@ -313,6 +316,7 @@ solve_h48_runthread(void *arg) | |||
| 313 | dfsarg->use_lb_inverse = false; | 316 | dfsarg->use_lb_inverse = false; |
| 314 | dfsarg->movemask_normal = MM18_ALLMOVES; | 317 | dfsarg->movemask_normal = MM18_ALLMOVES; |
| 315 | dfsarg->movemask_inverse = MM18_ALLMOVES; | 318 | dfsarg->movemask_inverse = MM18_ALLMOVES; |
| 319 | dfsarg->tmask = dfsarg->tasks[i].tmask; | ||
| 316 | 320 | ||
| 317 | solve_h48_dfs(dfsarg); | 321 | solve_h48_dfs(dfsarg); |
| 318 | 322 | ||
| @@ -341,7 +345,7 @@ solve_h48_runthread_end: | |||
| 341 | STATIC int64_t | 345 | STATIC int64_t |
| 342 | solve_h48_maketasks( | 346 | solve_h48_maketasks( |
| 343 | dfsarg_solve_h48_t solve_arg[static 1], | 347 | dfsarg_solve_h48_t solve_arg[static 1], |
| 344 | dfsarg_solve_h48_maketasks_t maketasks_arg[static 1], | 348 | dfsarg_solve_h48_maketasks_t mtarg[static 1], |
| 345 | solve_h48_task_t tasks[static H48_STARTING_CUBES], | 349 | solve_h48_task_t tasks[static H48_STARTING_CUBES], |
| 346 | int ntasks[static 1] | 350 | int ntasks[static 1] |
| 347 | ) | 351 | ) |
| @@ -353,59 +357,60 @@ solve_h48_maketasks( | |||
| 353 | cube_t backup_cube; | 357 | cube_t backup_cube; |
| 354 | solution_moves_t moves; | 358 | solution_moves_t moves; |
| 355 | 359 | ||
| 356 | if (equal(maketasks_arg->cube, SOLVED_CUBE)) { | 360 | if (equal(mtarg->cube, SOLVED_CUBE)) { |
| 357 | if (maketasks_arg->nmoves > maketasks_arg->maxmoves || | 361 | if (mtarg->nmoves > mtarg->maxmoves || |
| 358 | maketasks_arg->nmoves < maketasks_arg->minmoves || | 362 | mtarg->nmoves < mtarg->minmoves || |
| 359 | solutions_done(solve_arg->solution_list, | 363 | solutions_done(solve_arg->solution_list, |
| 360 | solve_arg->solution_settings, maketasks_arg->nmoves)) | 364 | solve_arg->solution_settings, mtarg->nmoves)) |
| 361 | return NISSY_OK; | 365 | return NISSY_OK; |
| 362 | 366 | ||
| 363 | solution_moves_reset(&moves); | 367 | solution_moves_reset(&moves); |
| 364 | moves.nmoves = maketasks_arg->nmoves; | 368 | moves.nmoves = mtarg->nmoves; |
| 365 | memcpy(moves.moves, | 369 | memcpy(moves.moves, mtarg->moves, mtarg->nmoves); |
| 366 | maketasks_arg->moves, maketasks_arg->nmoves); | ||
| 367 | 370 | ||
| 368 | appret = appendsolution(&moves, solve_arg->solution_settings, | 371 | appret = appendsolution(&moves, mtarg->nmoves, mtarg->tmask, |
| 369 | solve_arg->solution_list); | 372 | solve_arg->solution_settings, solve_arg->solution_list); |
| 370 | return appret < 0 ? appret : NISSY_OK; | 373 | return appret < 0 ? appret : NISSY_OK; |
| 371 | } | 374 | } |
| 372 | 375 | ||
| 373 | if (maketasks_arg->nmoves == H48_STARTING_MOVES) { | 376 | if (mtarg->nmoves == H48_STARTING_MOVES) { |
| 374 | tasks[*ntasks].cube = maketasks_arg->cube; | 377 | tasks[*ntasks].cube = mtarg->cube; |
| 375 | memcpy(tasks[*ntasks].moves, | 378 | memcpy(tasks[*ntasks].moves, mtarg->moves, |
| 376 | maketasks_arg->moves, H48_STARTING_MOVES); | 379 | H48_STARTING_MOVES * sizeof(uint8_t)); |
| 380 | memcpy(tasks[*ntasks].tmask, mtarg->tmask, | ||
| 381 | H48_STARTING_MOVES * sizeof(uint64_t)); | ||
| 377 | (*ntasks)++; | 382 | (*ntasks)++; |
| 378 | return NISSY_OK; | 383 | return NISSY_OK; |
| 379 | } | 384 | } |
| 380 | 385 | ||
| 381 | if (maketasks_arg->nmoves == 0) { | 386 | if (mtarg->nmoves == 0) { |
| 382 | mm = MM18_ALLMOVES; | 387 | mm = MM18_ALLMOVES; |
| 383 | } else { | 388 | } else { |
| 384 | m = maketasks_arg->moves[maketasks_arg->nmoves-1]; | 389 | m = mtarg->moves[mtarg->nmoves-1]; |
| 385 | mm = allowedmask[movebase(m)]; | 390 | mm = allowedmask[movebase(m)]; |
| 386 | } | 391 | } |
| 387 | 392 | ||
| 388 | maketasks_arg->nmoves++; | 393 | mtarg->tmask[mtarg->nmoves] = symmetry_mask(mtarg->cube); |
| 389 | backup_cube = maketasks_arg->cube; | 394 | |
| 395 | mtarg->nmoves++; | ||
| 396 | backup_cube = mtarg->cube; | ||
| 390 | for (m = 0; m < 18; m++) { | 397 | for (m = 0; m < 18; m++) { |
| 391 | if (!(mm & MM_SINGLE(m))) | 398 | if (!(mm & MM_SINGLE(m))) |
| 392 | continue; | 399 | continue; |
| 393 | maketasks_arg->moves[maketasks_arg->nmoves-1] = m; | 400 | |
| 394 | maketasks_arg->cube = move(backup_cube, m); | 401 | mtarg->moves[mtarg->nmoves-1] = m; |
| 395 | r = solve_h48_maketasks( | 402 | mtarg->cube = move(backup_cube, m); |
| 396 | solve_arg, maketasks_arg, tasks, ntasks); | 403 | r = solve_h48_maketasks(solve_arg, mtarg, tasks, ntasks); |
| 397 | if (r < 0) | 404 | if (r < 0) |
| 398 | return r; | 405 | return r; |
| 399 | 406 | ||
| 400 | /* Avoid symmetry-equivalent moves from the starting cube */ | 407 | /* Avoid symmetry-equivalent moves from the starting cube */ |
| 401 | if (maketasks_arg->nmoves == 1) | 408 | for (t = 0; t < NTRANS; t++) |
| 402 | for (t = 0; t < NTRANS; t++) | 409 | if (mtarg->tmask[mtarg->nmoves-1] & TM_SINGLE(t)) |
| 403 | if (solve_arg->solution_settings->tmask & | 410 | mm &= ~MM_SINGLE(transform_move(m, t)); |
| 404 | TM_SINGLE(t)) | ||
| 405 | mm &= ~MM_SINGLE(transform_move(m, t)); | ||
| 406 | } | 411 | } |
| 407 | maketasks_arg->nmoves--; | 412 | mtarg->nmoves--; |
| 408 | maketasks_arg->cube = backup_cube; | 413 | mtarg->cube = backup_cube; |
| 409 | 414 | ||
| 410 | return NISSY_OK; | 415 | return NISSY_OK; |
| 411 | } | 416 | } |
| @@ -441,7 +446,7 @@ solve_h48( | |||
| 441 | oriented_cube_t oc, | 446 | oriented_cube_t oc, |
| 442 | uint8_t minmoves, | 447 | uint8_t minmoves, |
| 443 | uint8_t maxmoves, | 448 | uint8_t maxmoves, |
| 444 | uint8_t maxsolutions, | 449 | uint64_t maxsolutions, |
| 445 | uint8_t optimal, | 450 | uint8_t optimal, |
| 446 | uint8_t threads, | 451 | uint8_t threads, |
| 447 | uint64_t data_size, | 452 | uint64_t data_size, |
| @@ -460,7 +465,7 @@ solve_h48( | |||
| 460 | int8_t d; | 465 | int8_t d; |
| 461 | dfsarg_solve_h48_t arg[THREADS]; | 466 | dfsarg_solve_h48_t arg[THREADS]; |
| 462 | solve_h48_task_t tasks[H48_STARTING_CUBES]; | 467 | solve_h48_task_t tasks[H48_STARTING_CUBES]; |
| 463 | dfsarg_solve_h48_maketasks_t maketasks_arg; | 468 | dfsarg_solve_h48_maketasks_t mtarg; |
| 464 | long double fallback_rate, lookups_per_node; | 469 | long double fallback_rate, lookups_per_node; |
| 465 | uint64_t offset; | 470 | uint64_t offset; |
| 466 | uint64_t nodes_visited, table_lookups, table_fallbacks; | 471 | uint64_t nodes_visited, table_lookups, table_fallbacks; |
| @@ -508,7 +513,6 @@ solve_h48( | |||
| 508 | fallback2 = h48data + offset; | 513 | fallback2 = h48data + offset; |
| 509 | 514 | ||
| 510 | settings = (solution_settings_t) { | 515 | settings = (solution_settings_t) { |
| 511 | .tmask = symmetry_mask(oc.cube), | ||
| 512 | .unniss = true, | 516 | .unniss = true, |
| 513 | .maxmoves = maxmoves, | 517 | .maxmoves = maxmoves, |
| 514 | .maxsolutions = maxsolutions, | 518 | .maxsolutions = maxsolutions, |
| @@ -543,14 +547,14 @@ solve_h48( | |||
| 543 | 547 | ||
| 544 | wrapthread_mutex_init(&solutions_mutex, NULL); | 548 | wrapthread_mutex_init(&solutions_mutex, NULL); |
| 545 | 549 | ||
| 546 | maketasks_arg = (dfsarg_solve_h48_maketasks_t) { | 550 | mtarg = (dfsarg_solve_h48_maketasks_t) { |
| 547 | .cube = oc.cube, | 551 | .cube = oc.cube, |
| 548 | .nmoves = 0, | 552 | .nmoves = 0, |
| 549 | .minmoves = minmoves, | 553 | .minmoves = minmoves, |
| 550 | .maxmoves = maxmoves, | 554 | .maxmoves = maxmoves, |
| 551 | }; | 555 | }; |
| 552 | ntasks = 0; | 556 | ntasks = 0; |
| 553 | solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks); | 557 | solve_h48_maketasks(&arg[0], &mtarg, tasks, &ntasks); |
| 554 | if (ntasks < 0) | 558 | if (ntasks < 0) |
| 555 | goto solve_h48_error_solutions_buffer; | 559 | goto solve_h48_error_solutions_buffer; |
| 556 | if (solutions_done(&sollist, &settings, | 560 | if (solutions_done(&sollist, &settings, |
diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h index 9f209d1..d92d5ad 100644 --- a/src/solvers/solutions.h +++ b/src/solvers/solutions.h | |||
| @@ -1,17 +1,23 @@ | |||
| 1 | STATIC void solution_moves_reset(solution_moves_t [static 1]); | 1 | STATIC void solution_moves_reset(solution_moves_t [static 1]); |
| 2 | STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t); | 2 | STATIC void solution_moves_transform(solution_moves_t [static 1], size_t, |
| 3 | uint8_t); | ||
| 3 | STATIC void solution_moves_reorient(solution_moves_t [static 1], uint8_t); | 4 | STATIC void solution_moves_reorient(solution_moves_t [static 1], uint8_t); |
| 4 | STATIC bool solution_list_init(solution_list_t [static 1], size_t, char *); | 5 | STATIC bool solution_list_init(solution_list_t [static 1], size_t, char *); |
| 5 | STATIC bool solution_moves_equal( | 6 | STATIC bool solution_moves_equal( |
| 6 | const solution_moves_t [static 1], const solution_moves_t [static 1]); | 7 | const solution_moves_t [static 1], const solution_moves_t [static 1]); |
| 7 | STATIC bool solution_moves_is_duplicate(size_t, const solution_moves_t *); | 8 | STATIC bool last_solution_is_duplicate(const solution_list_t [static 1]); |
| 8 | STATIC bool appendchar(solution_list_t [static 1], char); | 9 | STATIC bool appendchar(solution_list_t [static 1], char); |
| 9 | STATIC bool appendnormal( | 10 | STATIC bool appendnormal( |
| 10 | const solution_moves_t [static 1], solution_list_t [static 1]); | 11 | const solution_moves_t [static 1], solution_list_t [static 1]); |
| 11 | STATIC bool appendinverse( | 12 | STATIC bool appendinverse( |
| 12 | const solution_moves_t [static 1], solution_list_t [static 1]); | 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]); | ||
| 13 | STATIC int64_t appendsolution(const solution_moves_t [static 1], | 18 | STATIC int64_t appendsolution(const solution_moves_t [static 1], |
| 14 | const solution_settings_t [static 1], solution_list_t [static 1]); | 19 | size_t, const uint64_t *, const solution_settings_t [static 1], |
| 20 | solution_list_t [static 1]); | ||
| 15 | STATIC bool solutions_done(const solution_list_t [static 1], | 21 | STATIC bool solutions_done(const solution_list_t [static 1], |
| 16 | const solution_settings_t [static 1], int8_t depth); | 22 | const solution_settings_t [static 1], int8_t depth); |
| 17 | 23 | ||
| @@ -23,11 +29,11 @@ solution_moves_reset(solution_moves_t sol[static 1]) | |||
| 23 | } | 29 | } |
| 24 | 30 | ||
| 25 | STATIC void | 31 | STATIC void |
| 26 | solution_moves_transform(solution_moves_t moves[static 1], uint8_t t) | 32 | solution_moves_transform(solution_moves_t moves[static 1], size_t z, uint8_t t) |
| 27 | { | 33 | { |
| 28 | uint8_t i; | 34 | uint8_t i; |
| 29 | 35 | ||
| 30 | for (i = 0; i < moves->nmoves; i++) | 36 | for (i = z; i < moves->nmoves; i++) |
| 31 | moves->moves[i] = transform_move(moves->moves[i], t); | 37 | moves->moves[i] = transform_move(moves->moves[i], t); |
| 32 | 38 | ||
| 33 | for (i = 0; i < moves->npremoves; i++) | 39 | for (i = 0; i < moves->npremoves; i++) |
| @@ -87,13 +93,27 @@ solution_moves_equal( | |||
| 87 | } | 93 | } |
| 88 | 94 | ||
| 89 | STATIC bool | 95 | STATIC bool |
| 90 | solution_moves_is_duplicate(size_t n, const solution_moves_t *s) | 96 | last_solution_is_duplicate(const solution_list_t l[static 1]) |
| 91 | { | 97 | { |
| 92 | size_t i; | 98 | size_t i, j; |
| 99 | |||
| 100 | if (l->nsols == 1) | ||
| 101 | return false; | ||
| 93 | 102 | ||
| 94 | for (i = 0; i < n; i++) | 103 | /* We assume the list is newline-terminated */ |
| 95 | if (solution_moves_equal(&s[i], &s[n])) | 104 | j = l->used-2; |
| 96 | return true; | 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 | } | ||
| 97 | 117 | ||
| 98 | return false; | 118 | return false; |
| 99 | } | 119 | } |
| @@ -150,97 +170,157 @@ appendinverse( | |||
| 150 | return appendchar(list, ')'); | 170 | return appendchar(list, ')'); |
| 151 | } | 171 | } |
| 152 | 172 | ||
| 153 | STATIC int64_t | 173 | STATIC void |
| 154 | appendsolution( | 174 | appendsolution_dfs( |
| 155 | const solution_moves_t moves[static 1], | 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, | ||
| 156 | const solution_settings_t settings[static 1], | 180 | const solution_settings_t settings[static 1], |
| 157 | solution_list_t list[static 1] | 181 | solution_list_t list[static 1], |
| 182 | solution_moves_t tsol[static NTRANS * SOLUTION_MAXLEN], | ||
| 183 | int64_t r[static 1] | ||
| 158 | ) | 184 | ) |
| 159 | { | 185 | { |
| 160 | int64_t r; | 186 | /* |
| 161 | int i; | 187 | The logic here is quit complex because we have to address H48 |
| 162 | uint8_t t; | 188 | solutions that may be reduced by symmetry in the first few moves. |
| 163 | solution_moves_t tsol[NTRANS]; | 189 | */ |
| 164 | 190 | ||
| 165 | if (moves->nmoves + moves->npremoves > SOLUTION_MAXLEN) | 191 | size_t i, last_start; |
| 166 | goto appendsolution_error_solution_length; | 192 | uint8_t t; |
| 193 | solution_moves_t moves_copy; | ||
| 167 | 194 | ||
| 168 | for ( | 195 | if (list->nsols >= settings->maxsolutions) |
| 169 | t = 0, r = 0; | 196 | return; |
| 170 | t < NTRANS && list->nsols < settings->maxsolutions; | ||
| 171 | t++ | ||
| 172 | ) { | ||
| 173 | if (!(settings->tmask & TM_SINGLE(t))) | ||
| 174 | continue; | ||
| 175 | 197 | ||
| 176 | tsol[r] = *moves; | 198 | if (ntmask == itm) { |
| 177 | if (settings->unniss) { | 199 | tsol[*r] = *moves; |
| 178 | tsol[r].nmoves += moves->npremoves; | ||
| 179 | tsol[r].npremoves = 0; | ||
| 180 | for (i = moves->npremoves-1; i >= 0; i--) | ||
| 181 | tsol[r].moves[tsol[r].nmoves - i - 1] = | ||
| 182 | inverse_move(moves->premoves[i]); | ||
| 183 | 200 | ||
| 184 | /* | 201 | for (i = ntmask; i > 0; i--) |
| 185 | This is a bit ugly: we have to sort now and then again | 202 | solution_moves_transform(&tsol[*r], i-1, tt[i-1]); |
| 186 | later, because the allowedmoves check would fail with | ||
| 187 | improperly sorted parallel moves, but then transforming | ||
| 188 | could swap the pairs the wrong way around. | ||
| 189 | */ | ||
| 190 | sortparallel_moves(tsol[r].nmoves, tsol[r].moves); | ||
| 191 | 203 | ||
| 192 | /* Check if unnissed premoves cancel with normal. */ | 204 | solution_moves_reorient(&tsol[*r], settings->orientation); |
| 193 | if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) | 205 | sortparallel_moves(tsol[*r].nmoves, tsol[*r].moves); |
| 194 | continue; | 206 | sortparallel_moves(tsol[*r].npremoves, tsol[*r].premoves); |
| 195 | } | ||
| 196 | solution_moves_transform(&tsol[r], t); | ||
| 197 | solution_moves_reorient(&tsol[r], settings->orientation); | ||
| 198 | sortparallel_moves(tsol[r].nmoves, tsol[r].moves); | ||
| 199 | sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); | ||
| 200 | 207 | ||
| 201 | /* Skip duplicates that may appear after transforming */ | 208 | last_start = list->used; |
| 202 | if (solution_moves_is_duplicate(r, tsol)) | ||
| 203 | continue; | ||
| 204 | 209 | ||
| 205 | /* Append first the moves on the side that has more */ | 210 | /* Append first the moves on the side that has more */ |
| 206 | /* E.g. write (U L F) B instead of B (U L F) */ | 211 | /* E.g. write (U L F) B instead of B (U L F) */ |
| 207 | if (tsol[r].nmoves >= tsol[r].npremoves) { | 212 | if (tsol[*r].nmoves >= tsol[*r].npremoves) { |
| 208 | if (!appendnormal(&tsol[r], list)) | 213 | if (!appendnormal(&tsol[*r], list)) |
| 209 | goto appendsolution_error_buffer; | 214 | goto appendsolution_dfs_error_buffer; |
| 210 | 215 | ||
| 211 | if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) | 216 | if (tsol[*r].nmoves > 0 && tsol[*r].npremoves > 0) |
| 212 | if (!appendchar(list, ' ')) | 217 | if (!appendchar(list, ' ')) |
| 213 | return false; | 218 | goto appendsolution_dfs_error_buffer; |
| 214 | 219 | ||
| 215 | if (!appendinverse(&tsol[r], list)) | 220 | if (!appendinverse(&tsol[*r], list)) |
| 216 | goto appendsolution_error_buffer; | 221 | goto appendsolution_dfs_error_buffer; |
| 217 | } else { | 222 | } else { |
| 218 | if (!appendinverse(&tsol[r], list)) | 223 | if (!appendinverse(&tsol[*r], list)) |
| 219 | goto appendsolution_error_buffer; | 224 | goto appendsolution_dfs_error_buffer; |
| 220 | 225 | ||
| 221 | if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) | 226 | if (tsol[*r].nmoves > 0 && tsol[*r].npremoves > 0) |
| 222 | if (!appendchar(list, ' ')) | 227 | if (!appendchar(list, ' ')) |
| 223 | return false; | 228 | goto appendsolution_dfs_error_buffer; |
| 224 | 229 | ||
| 225 | if (!appendnormal(&tsol[r], list)) | 230 | if (!appendnormal(&tsol[*r], list)) |
| 226 | goto appendsolution_error_buffer; | 231 | goto appendsolution_dfs_error_buffer; |
| 227 | } | 232 | } |
| 228 | 233 | ||
| 229 | if (!appendchar(list, '\n')) | 234 | if (!appendchar(list, '\n')) |
| 230 | goto appendsolution_error_buffer; | 235 | goto appendsolution_dfs_error_buffer; |
| 231 | |||
| 232 | ++list->nsols; | 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 | |||
| 233 | list->shortest_sol = MIN( | 253 | list->shortest_sol = MIN( |
| 234 | list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); | 254 | list->shortest_sol, tsol[*r].nmoves + tsol[*r].npremoves); |
| 235 | r++; | 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 | } | ||
| 236 | } | 267 | } |
| 237 | 268 | ||
| 238 | list->buf[list->used] = '\0'; | 269 | return; |
| 239 | return r; | ||
| 240 | 270 | ||
| 241 | appendsolution_error_buffer: | 271 | appendsolution_dfs_error_buffer: |
| 242 | list->buf[0] = '\0'; | 272 | list->buf[0] = '\0'; |
| 243 | return NISSY_ERROR_BUFFER_SIZE; | 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; | ||
| 244 | 324 | ||
| 245 | appendsolution_error_solution_length: | 325 | appendsolution_error_solution_length: |
| 246 | list->buf[0] = '\0'; | 326 | list->buf[0] = '\0'; |
diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h index c8efc0b..4727e5a 100644 --- a/src/solvers/solutions_types_macros.h +++ b/src/solvers/solutions_types_macros.h | |||
| @@ -8,7 +8,6 @@ typedef struct { | |||
| 8 | } solution_moves_t; | 8 | } solution_moves_t; |
| 9 | 9 | ||
| 10 | typedef struct { | 10 | typedef struct { |
| 11 | uint64_t tmask; | ||
| 12 | bool unniss; | 11 | bool unniss; |
| 13 | uint8_t maxmoves; | 12 | uint8_t maxmoves; |
| 14 | uint64_t maxsolutions; | 13 | uint64_t maxsolutions; |
