commit 147b0c3c4615c32478a4923242909b8ae5a30d03 parent 78ec0d22d927bc4287aa090469d5ba5f84e8780b Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sun, 23 Nov 2025 16:16:31 +0100 Fix duplicate solutions, overflow in maxsols and improve symmetry reduction for H48. This commit fixes two bugs: - A bug that caused duplicates solutions for symmetric scrambles. - An overflow in the maxsols parameter for the H48 solver, which caused it to find much fewer solutions than existed. Moreover, the H48 solvers has been improved by reducing by symmetry not only from the starting position, but also up to the first 4 moves. Diffstat:
24 files changed, 311 insertions(+), 162 deletions(-)
diff --git a/.gitignore b/.gitignore @@ -46,3 +46,4 @@ tools/results python/*.pyd python/*.exp python/*.lib +*.sketch diff --git a/benchmarks/benchmarks.md b/benchmarks/benchmarks.md @@ -71,9 +71,9 @@ Time per cube (in seconds, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 k2|56.1GiB | 0.23 | 1.15 | 5.08 | 31.30 | 278.47 | +|H48 h11 k2|56.1GiB | 0.23 | 1.15 | 5.08 | 31.30 | 53.67 | |vcube 404 |31.8GiB | 0.30 | 1.25 | 6.87 | 57.49 | 291.31 | -|H48 h10 k2|28.1GiB | 0.34 | 1.80 | 7.77 | | | +|H48 h10 k2|28.1GiB | 0.34 | 1.80 | 7.77 | | 81.89 | |vcube 308 |21.2GiB | 0.20 | 1.11 | 6.92 | | | |H48 h9 k2 |14.1GiB | 0.42 | 2.84 | 12.86 | | | |vcube 208 | 7.3GiB | 0.57 | 4.41 | 20.75 | | | @@ -86,9 +86,9 @@ Time per cube adjusted for tables size (in seconds \* GiB, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 k2|56.1GiB | 12.90 | 64.51 | 284.99 |1755.93 |15622.17 | +|H48 h11 k2|56.1GiB | 12.90 | 64.51 | 284.99 |1755.93 | 3010.89 | |vcube 404 |31.8GiB | 9.54 | 39.75 | 218.47 |1828.18 | 9263.66 | -|H48 h10 k2|28.1GiB | 9.55 | 50.58 | 218.34 | | | +|H48 h10 k2|28.1GiB | 9.55 | 50.58 | 218.34 | | 2301.11 | |vcube 308 |21.2GiB | 4.24 | 23.53 | 146.70 | | | |H48 h9 k2 |14.1GiB | 5.92 | 40.04 | 181.33 | | | |vcube 208 | 7.3GiB | 4.16 | 32.19 | 151.48 | | | @@ -110,11 +110,11 @@ Time per cube (in seconds, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 k2|56.1GiB | 0.06 | 0.31 | 1.31 | 7.96 | 77.81 | +|H48 h11 k2|56.1GiB | 0.06 | 0.31 | 1.31 | 7.96 | 14.01 | |vcube 404 |31.8GiB | 0.10 | 0.38 | 1.88 | 16.98 | (a) | -|H48 h10 k2|28.1GiB | 0.10 | 0.47 | 2.00 | 13.54 | 114.35 | +|H48 h10 k2|28.1GiB | 0.10 | 0.47 | 2.00 | 13.54 | 21.96 | |vcube 308 |21.2GiB | 0.06 | 0.42 | 1.95 | 17.73 | (a) | -|H48 h9 k2 |14.1GiB | 0.14 | 0.83 | 3.82 | 25.98 | 162.72 | +|H48 h9 k2 |14.1GiB | 0.14 | 0.83 | 3.82 | 25.98 | 31.68 | |vcube 208 | 7.3GiB | 0.17 | 1.49 | 5.88 | | (a) | |H48 h8 k2 | 7.1GiB | 0.27 | 2.02 | 7.94 | | | |H48 h7 k2 | 3.6GiB | 0.35 | 2.59 | 12.41 | | | @@ -125,11 +125,11 @@ Time per cube adjusted for tables size (in seconds \* GiB, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 k2|56.1GiB | 3.37 | 17.39 | 73.49 | 446.56 | 4365.92 | +|H48 h11 k2|56.1GiB | 3.37 | 17.39 | 73.49 | 446.56 | 785.96 | |vcube 404 |31.8GiB | 3.80 | 12.08 | 59.78 | 539.96 | (a) | -|H48 h10 k2|28.1GiB | 2.81 | 13.21 | 56.20 | 380.47 | 3213.24 | +|H48 h10 k2|28.1GiB | 2.81 | 13.21 | 56.20 | 380.47 | 617.08 | |vcube 308 |21.2GiB | 1.27 | 8.90 | 41.34 | 375.88 | (a) | -|H48 h9 k2 |14.1GiB | 1.97 | 11.70 | 53.86 | 366.32 | 2294.35 | +|H48 h9 k2 |14.1GiB | 1.97 | 11.70 | 53.86 | 366.32 | 446.69 | |vcube 208 | 7.3GiB | 1.24 | 10.88 | 42.92 | | (a) | |H48 h8 k2 | 7.1GiB | 1.92 | 14.34 | 56.37 | | | |H48 h7 k2 | 3.6GiB | 1.26 | 9.32 | 44.68 | | | @@ -152,11 +152,11 @@ Time per cube (in seconds, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 k2|56.1GiB | 0.02 | 0.10 | 0.43 | 2.48 | 26.29 | +|H48 h11 k2|56.1GiB | 0.02 | 0.10 | 0.43 | 2.48 | 5.67 | |vcube 404 |31.8GiB | 0.03 | 0.16 | 0.67 | 6.36 | (a) | -|H48 h10 k2|28.1GiB | 0.03 | 0.16 | 0.74 | 4.43 | | +|H48 h10 k2|28.1GiB | 0.03 | 0.16 | 0.74 | 4.43 | 8.81 | |vcube 308 |21.2GiB | 0.04 | 0.22 | 0.89 | 9.53 | (a) | -|H48 h9 k2 |14.1GiB | 0.04 | 0.26 | 1.18 | 8.31 | | +|H48 h9 k2 |14.1GiB | 0.04 | 0.26 | 1.18 | 8.31 | 13.20 | |vcube 208 | 7.3GiB | 0.08 | 0.80 | 2.38 | | (a) | |H48 h8 k2 | 7.1GiB | 0.08 | 0.60 | 2.48 | | | |H48 h7 k2 | 3.6GiB | 0.11 | 0.81 | 3.91 | | | @@ -167,11 +167,11 @@ Time per cube adjusted for tables size (in seconds \* GiB, lower is better). | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |:---------|:-------|-------:|-------:|-------:|-------:|--------:| -|H48 h11 k2|56.1GiB | 1.12 | 5.61 | 24.12 | 139.13 | 1474.87 | +|H48 h11 k2|56.1GiB | 1.12 | 5.61 | 24.12 | 139.13 | 318.09 | |vcube 404 |31.8GiB | 1.08 | 5.09 | 21.31 | 202.25 | (a) | -|H48 h10 k2|28.1GiB | 0.84 | 4.50 | 20.79 | 124.48 | | +|H48 h10 k2|28.1GiB | 0.84 | 4.50 | 20.79 | 124.48 | 247.56 | |vcube 308 |21.2GiB | 0.85 | 4.66 | 18.87 | 202.04 | (a) | -|H48 h9 k2 |14.1GiB | 0.56 | 3.67 | 16.64 | 117.17 | | +|H48 h9 k2 |14.1GiB | 0.56 | 3.67 | 16.64 | 117.17 | 186.12 | |vcube 208 | 7.3GiB | 0.58 | 5.84 | 17.37 | | (a) | |H48 h8 k2 | 7.1GiB | 0.57 | 4.26 | 17.60 | | | |H48 h7 k2 | 3.6GiB | 0.40 | 2.92 | 14.07 | | | @@ -196,25 +196,25 @@ Average time for finding all optimal solutions. Time per cube (in seconds, lower is better). -| Solver | Size |17 moves|18 moves|19 moves|20 moves| -|:---------|:-------|-------:|-------:|-------:|-------:| -|H48 h11 k2|56.1GiB | 0.05 | 0.50 | 4.24 | 19.75 | -|H48 h10 k2|28.1GiB | 0.08 | 0.88 | 6.94 | | -|H48 h9 k2 |14.1GiB | 0.13 | 1.39 | 13.50 | | -|H48 h8 k2 | 7.1GiB | 0.25 | 2.85 | | | -|H48 h7 k2 | 3.6GiB | 0.36 | 4.24 | | | -|H48 h6 k2 | 1.8GiB | 0.69 | 8.20 | | | +| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| +|:---------|:-------|-------:|-------:|-------:|-------:|--------:| +|H48 h11 k2|56.1GiB | 0.05 | 0.50 | 4.24 | 19.75 | 52.99 | +|H48 h10 k2|28.1GiB | 0.08 | 0.88 | 6.94 | | | +|H48 h9 k2 |14.1GiB | 0.13 | 1.39 | 13.50 | | | +|H48 h8 k2 | 7.1GiB | 0.25 | 2.85 | | | | +|H48 h7 k2 | 3.6GiB | 0.36 | 4.24 | | | | +|H48 h6 k2 | 1.8GiB | 0.69 | 8.20 | | | | Time per cube adjusted for tables size (in seconds \* GiB, lower is better). -| Solver | Size |17 moves|18 moves|19 moves|20 moves| -|:---------|:-------|-------:|-------:|-------:|-------:| -|H48 h11 k2|56.1GiB | 2.81 | 28.05 | 237.86 |1107.98 | -|H48 h10 k2|28.1GiB | 2.25 | 24.73 | 195.01 | | -|H48 h9 k2 |14.1GiB | 1.83 | 19.60 | 190.35 | | -|H48 h8 k2 | 7.1GiB | 1.77 | 20.24 | | | -|H48 h7 k2 | 3.6GiB | 1.30 | 15.26 | | | -|H48 h6 k2 | 1.8GiB | 1.24 | 14.76 | | | +| Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| +|:---------|:-------|-------:|-------:|-------:|-------:|--------:| +|H48 h11 k2|56.1GiB | 2.81 | 28.05 | 237.86 |1107.98 | 2972.74 | +|H48 h10 k2|28.1GiB | 2.25 | 24.73 | 195.01 | | | +|H48 h9 k2 |14.1GiB | 1.83 | 19.60 | 190.35 | | | +|H48 h8 k2 | 7.1GiB | 1.77 | 20.24 | | | | +|H48 h7 k2 | 3.6GiB | 1.30 | 15.26 | | | | +|H48 h6 k2 | 1.8GiB | 1.24 | 14.76 | | | | ## Comments on the results diff --git a/src/solvers/coord/multisolve.h b/src/solvers/coord/multisolve.h @@ -9,6 +9,7 @@ typedef struct { uint8_t target_depth; solution_moves_t *solution_moves; solution_settings_t *solution_settings; + uint64_t tmask; solution_list_t *solution_list; multicoord_t *mcoord; const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS]; @@ -87,7 +88,7 @@ solve_multicoord_dfs(dfsarg_solve_multicoord_t arg[static 1]) /* All coordinates are solved */ if (!multicoord_solution_admissible(arg)) return 0; - return appendsolution(arg->solution_moves, + return appendsolution(arg->solution_moves, 1, &arg->tmask, arg->solution_settings, arg->solution_list); solve_multicoord_dfs_notsolved: @@ -208,7 +209,6 @@ solve_multicoord( solution_moves_reset(&solution_moves); solution_settings = (solution_settings_t) { - .tmask = TM_SINGLE(inverse_trans(trans)), .unniss = false, .maxmoves = maxmoves, .maxsolutions = maxsolutions, @@ -222,6 +222,7 @@ solve_multicoord( .mcoord = mcoord, .solution_moves = &solution_moves, .solution_settings = &solution_settings, + .tmask = TM_SINGLE(inverse_trans(trans)), .solution_list = &solution_list, }; @@ -258,8 +259,8 @@ solve_multicoord( } /* All coordinates are solved */ - if (minmoves == 0 && !appendsolution(&solution_moves, - &solution_settings, &solution_list)) + if (minmoves == 0 && !appendsolution(&solution_moves, 1, + &arg.tmask, &solution_settings, &solution_list)) goto solve_multicoord_error_buffer; goto solve_multicoord_done; diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h @@ -3,6 +3,7 @@ typedef struct { cube_t inverse; uint8_t target_depth; solution_moves_t *solution_moves; + uint64_t tmask; solution_settings_t *solution_settings; solution_list_t *solution_list; uint8_t nissflag; @@ -163,7 +164,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) if (coord_is_solved(arg->coord, coord, arg->coord_data)) { if (!coord_solution_admissible(arg)) return 0; - return appendsolution(arg->solution_moves, + return appendsolution(arg->solution_moves, 1, &arg->tmask, arg->solution_settings, arg->solution_list); } @@ -339,7 +340,6 @@ solve_coord( solution_moves_reset(&solution_moves); solution_settings = (solution_settings_t) { - .tmask = TM_SINGLE(inverse_trans(trans)), .unniss = false, .maxmoves = maxmoves, .maxsolutions = maxsolutions, @@ -355,14 +355,15 @@ solve_coord( .ptable = ptable, .solution_moves = &solution_moves, .solution_settings = &solution_settings, + .tmask = TM_SINGLE(inverse_trans(trans)), .solution_list = &solution_list, .nissflag = nissflag, }; i = coord->coord(c, coord_data); if (coord_is_solved(coord, i, coord_data)) { - if (minmoves == 0 && !appendsolution(&solution_moves, - &solution_settings, &solution_list)) + if (minmoves == 0 && !appendsolution(&solution_moves, 1, + &arg.tmask, &solution_settings, &solution_list)) goto solve_coord_error_buffer; goto solve_coord_done; } diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h @@ -13,6 +13,7 @@ typedef struct { cube_t cube; uint8_t moves[H48_STARTING_MOVES]; int64_t rank; + uint64_t tmask[H48_STARTING_MOVES]; } solve_h48_task_t; typedef struct { @@ -22,6 +23,7 @@ typedef struct { int8_t target_depth; solution_moves_t *solution_moves; solution_settings_t *solution_settings; + const uint64_t *tmask; solution_list_t *solution_list; int8_t lb_normal; int8_t lb_inverse; @@ -55,6 +57,7 @@ typedef struct { int8_t minmoves; int8_t maxmoves; int8_t *shortest_sol; + uint64_t tmask[H48_STARTING_MOVES]; } dfsarg_solve_h48_maketasks_t; STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, @@ -69,7 +72,7 @@ STATIC void *solve_h48_runthread(void *); STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]); STATIC void solve_h48_log_solutions(solution_list_t [static 1], size_t); STATIC int solve_h48_compare_tasks(const void *, const void *); -STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint8_t, uint8_t, +STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, const unsigned char *, size_t, char *, long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); @@ -208,8 +211,8 @@ solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) if (arg->target_depth != nm) return 0; wrapthread_mutex_lock(arg->solutions_mutex); - ret = appendsolution(arg->solution_moves, - arg->solution_settings, arg->solution_list); + ret = appendsolution(arg->solution_moves, H48_STARTING_MOVES, + arg->tmask, arg->solution_settings, arg->solution_list); wrapthread_mutex_unlock(arg->solutions_mutex); return ret; } @@ -313,6 +316,7 @@ solve_h48_runthread(void *arg) dfsarg->use_lb_inverse = false; dfsarg->movemask_normal = MM18_ALLMOVES; dfsarg->movemask_inverse = MM18_ALLMOVES; + dfsarg->tmask = dfsarg->tasks[i].tmask; solve_h48_dfs(dfsarg); @@ -341,7 +345,7 @@ solve_h48_runthread_end: STATIC int64_t solve_h48_maketasks( dfsarg_solve_h48_t solve_arg[static 1], - dfsarg_solve_h48_maketasks_t maketasks_arg[static 1], + dfsarg_solve_h48_maketasks_t mtarg[static 1], solve_h48_task_t tasks[static H48_STARTING_CUBES], int ntasks[static 1] ) @@ -353,59 +357,60 @@ solve_h48_maketasks( cube_t backup_cube; solution_moves_t moves; - if (equal(maketasks_arg->cube, SOLVED_CUBE)) { - if (maketasks_arg->nmoves > maketasks_arg->maxmoves || - maketasks_arg->nmoves < maketasks_arg->minmoves || + if (equal(mtarg->cube, SOLVED_CUBE)) { + if (mtarg->nmoves > mtarg->maxmoves || + mtarg->nmoves < mtarg->minmoves || solutions_done(solve_arg->solution_list, - solve_arg->solution_settings, maketasks_arg->nmoves)) + solve_arg->solution_settings, mtarg->nmoves)) return NISSY_OK; solution_moves_reset(&moves); - moves.nmoves = maketasks_arg->nmoves; - memcpy(moves.moves, - maketasks_arg->moves, maketasks_arg->nmoves); + moves.nmoves = mtarg->nmoves; + memcpy(moves.moves, mtarg->moves, mtarg->nmoves); - appret = appendsolution(&moves, solve_arg->solution_settings, - solve_arg->solution_list); + appret = appendsolution(&moves, mtarg->nmoves, mtarg->tmask, + solve_arg->solution_settings, solve_arg->solution_list); return appret < 0 ? appret : NISSY_OK; } - if (maketasks_arg->nmoves == H48_STARTING_MOVES) { - tasks[*ntasks].cube = maketasks_arg->cube; - memcpy(tasks[*ntasks].moves, - maketasks_arg->moves, H48_STARTING_MOVES); + if (mtarg->nmoves == H48_STARTING_MOVES) { + tasks[*ntasks].cube = mtarg->cube; + memcpy(tasks[*ntasks].moves, mtarg->moves, + H48_STARTING_MOVES * sizeof(uint8_t)); + memcpy(tasks[*ntasks].tmask, mtarg->tmask, + H48_STARTING_MOVES * sizeof(uint64_t)); (*ntasks)++; return NISSY_OK; } - if (maketasks_arg->nmoves == 0) { + if (mtarg->nmoves == 0) { mm = MM18_ALLMOVES; } else { - m = maketasks_arg->moves[maketasks_arg->nmoves-1]; + m = mtarg->moves[mtarg->nmoves-1]; mm = allowedmask[movebase(m)]; } - maketasks_arg->nmoves++; - backup_cube = maketasks_arg->cube; + mtarg->tmask[mtarg->nmoves] = symmetry_mask(mtarg->cube); + + mtarg->nmoves++; + backup_cube = mtarg->cube; for (m = 0; m < 18; m++) { if (!(mm & MM_SINGLE(m))) continue; - maketasks_arg->moves[maketasks_arg->nmoves-1] = m; - maketasks_arg->cube = move(backup_cube, m); - r = solve_h48_maketasks( - solve_arg, maketasks_arg, tasks, ntasks); + + mtarg->moves[mtarg->nmoves-1] = m; + mtarg->cube = move(backup_cube, m); + r = solve_h48_maketasks(solve_arg, mtarg, tasks, ntasks); if (r < 0) return r; /* Avoid symmetry-equivalent moves from the starting cube */ - if (maketasks_arg->nmoves == 1) - for (t = 0; t < NTRANS; t++) - if (solve_arg->solution_settings->tmask & - TM_SINGLE(t)) - mm &= ~MM_SINGLE(transform_move(m, t)); + for (t = 0; t < NTRANS; t++) + if (mtarg->tmask[mtarg->nmoves-1] & TM_SINGLE(t)) + mm &= ~MM_SINGLE(transform_move(m, t)); } - maketasks_arg->nmoves--; - maketasks_arg->cube = backup_cube; + mtarg->nmoves--; + mtarg->cube = backup_cube; return NISSY_OK; } @@ -441,7 +446,7 @@ solve_h48( oriented_cube_t oc, uint8_t minmoves, uint8_t maxmoves, - uint8_t maxsolutions, + uint64_t maxsolutions, uint8_t optimal, uint8_t threads, uint64_t data_size, @@ -460,7 +465,7 @@ solve_h48( int8_t d; dfsarg_solve_h48_t arg[THREADS]; solve_h48_task_t tasks[H48_STARTING_CUBES]; - dfsarg_solve_h48_maketasks_t maketasks_arg; + dfsarg_solve_h48_maketasks_t mtarg; long double fallback_rate, lookups_per_node; uint64_t offset; uint64_t nodes_visited, table_lookups, table_fallbacks; @@ -508,7 +513,6 @@ solve_h48( fallback2 = h48data + offset; settings = (solution_settings_t) { - .tmask = symmetry_mask(oc.cube), .unniss = true, .maxmoves = maxmoves, .maxsolutions = maxsolutions, @@ -543,14 +547,14 @@ solve_h48( wrapthread_mutex_init(&solutions_mutex, NULL); - maketasks_arg = (dfsarg_solve_h48_maketasks_t) { + mtarg = (dfsarg_solve_h48_maketasks_t) { .cube = oc.cube, .nmoves = 0, .minmoves = minmoves, .maxmoves = maxmoves, }; ntasks = 0; - solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks); + solve_h48_maketasks(&arg[0], &mtarg, tasks, &ntasks); if (ntasks < 0) goto solve_h48_error_solutions_buffer; if (solutions_done(&sollist, &settings, diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h @@ -1,17 +1,23 @@ STATIC void solution_moves_reset(solution_moves_t [static 1]); -STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t); +STATIC void solution_moves_transform(solution_moves_t [static 1], size_t, + uint8_t); STATIC void solution_moves_reorient(solution_moves_t [static 1], uint8_t); STATIC bool solution_list_init(solution_list_t [static 1], size_t, char *); STATIC bool solution_moves_equal( const solution_moves_t [static 1], const solution_moves_t [static 1]); -STATIC bool solution_moves_is_duplicate(size_t, const solution_moves_t *); +STATIC bool last_solution_is_duplicate(const solution_list_t [static 1]); STATIC bool appendchar(solution_list_t [static 1], char); STATIC bool appendnormal( const solution_moves_t [static 1], solution_list_t [static 1]); STATIC bool appendinverse( const solution_moves_t [static 1], solution_list_t [static 1]); +STATIC void appendsolution_dfs(const solution_moves_t [static 1], size_t, + const uint64_t *, size_t, uint8_t *, const solution_settings_t [static 1], + solution_list_t [static 1], + solution_moves_t [static NTRANS * SOLUTION_MAXLEN], int64_t [static 1]); STATIC int64_t appendsolution(const solution_moves_t [static 1], - const solution_settings_t [static 1], solution_list_t [static 1]); + size_t, const uint64_t *, const solution_settings_t [static 1], + solution_list_t [static 1]); STATIC bool solutions_done(const solution_list_t [static 1], const solution_settings_t [static 1], int8_t depth); @@ -23,11 +29,11 @@ solution_moves_reset(solution_moves_t sol[static 1]) } STATIC void -solution_moves_transform(solution_moves_t moves[static 1], uint8_t t) +solution_moves_transform(solution_moves_t moves[static 1], size_t z, uint8_t t) { uint8_t i; - for (i = 0; i < moves->nmoves; i++) + for (i = z; i < moves->nmoves; i++) moves->moves[i] = transform_move(moves->moves[i], t); for (i = 0; i < moves->npremoves; i++) @@ -87,13 +93,27 @@ solution_moves_equal( } STATIC bool -solution_moves_is_duplicate(size_t n, const solution_moves_t *s) +last_solution_is_duplicate(const solution_list_t l[static 1]) { - size_t i; + size_t i, j; + + if (l->nsols == 1) + return false; - for (i = 0; i < n; i++) - if (solution_moves_equal(&s[i], &s[n])) - return true; + /* We assume the list is newline-terminated */ + j = l->used-2; + while (true) { + for ( ; l->buf[j] != '\n'; j--) + if (j == 0) return false; + j--; + for (i = l->used-2; l->buf[i] == l->buf[j]; i--, j--) { + if (l->buf[i-1] == '\n') { + if (l->buf[j-1] == '\n' || j == 0) + return true; + else break; + } + } + } return false; } @@ -150,97 +170,157 @@ appendinverse( return appendchar(list, ')'); } -STATIC int64_t -appendsolution( +STATIC void +appendsolution_dfs( const solution_moves_t moves[static 1], + size_t ntmask, + const uint64_t *tmask, + size_t itm, + uint8_t *tt, const solution_settings_t settings[static 1], - solution_list_t list[static 1] + solution_list_t list[static 1], + solution_moves_t tsol[static NTRANS * SOLUTION_MAXLEN], + int64_t r[static 1] ) { - int64_t r; - int i; + /* + The logic here is quit complex because we have to address H48 + solutions that may be reduced by symmetry in the first few moves. + */ + + size_t i, last_start; uint8_t t; - solution_moves_t tsol[NTRANS]; + solution_moves_t moves_copy; - if (moves->nmoves + moves->npremoves > SOLUTION_MAXLEN) - goto appendsolution_error_solution_length; + if (list->nsols >= settings->maxsolutions) + return; - for ( - t = 0, r = 0; - t < NTRANS && list->nsols < settings->maxsolutions; - t++ - ) { - if (!(settings->tmask & TM_SINGLE(t))) - continue; - - tsol[r] = *moves; - if (settings->unniss) { - tsol[r].nmoves += moves->npremoves; - tsol[r].npremoves = 0; - for (i = moves->npremoves-1; i >= 0; i--) - tsol[r].moves[tsol[r].nmoves - i - 1] = - inverse_move(moves->premoves[i]); - - /* - This is a bit ugly: we have to sort now and then again - later, because the allowedmoves check would fail with - improperly sorted parallel moves, but then transforming - could swap the pairs the wrong way around. - */ - sortparallel_moves(tsol[r].nmoves, tsol[r].moves); - - /* Check if unnissed premoves cancel with normal. */ - if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) - continue; - } - solution_moves_transform(&tsol[r], t); - solution_moves_reorient(&tsol[r], settings->orientation); - sortparallel_moves(tsol[r].nmoves, tsol[r].moves); - sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); + if (ntmask == itm) { + tsol[*r] = *moves; + + for (i = ntmask; i > 0; i--) + solution_moves_transform(&tsol[*r], i-1, tt[i-1]); + + solution_moves_reorient(&tsol[*r], settings->orientation); + sortparallel_moves(tsol[*r].nmoves, tsol[*r].moves); + sortparallel_moves(tsol[*r].npremoves, tsol[*r].premoves); - /* Skip duplicates that may appear after transforming */ - if (solution_moves_is_duplicate(r, tsol)) - continue; + last_start = list->used; /* Append first the moves on the side that has more */ /* E.g. write (U L F) B instead of B (U L F) */ - if (tsol[r].nmoves >= tsol[r].npremoves) { - if (!appendnormal(&tsol[r], list)) - goto appendsolution_error_buffer; + if (tsol[*r].nmoves >= tsol[*r].npremoves) { + if (!appendnormal(&tsol[*r], list)) + goto appendsolution_dfs_error_buffer; - if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) + if (tsol[*r].nmoves > 0 && tsol[*r].npremoves > 0) if (!appendchar(list, ' ')) - return false; + goto appendsolution_dfs_error_buffer; - if (!appendinverse(&tsol[r], list)) - goto appendsolution_error_buffer; + if (!appendinverse(&tsol[*r], list)) + goto appendsolution_dfs_error_buffer; } else { - if (!appendinverse(&tsol[r], list)) - goto appendsolution_error_buffer; + if (!appendinverse(&tsol[*r], list)) + goto appendsolution_dfs_error_buffer; - if (tsol[r].nmoves > 0 && tsol[r].npremoves > 0) + if (tsol[*r].nmoves > 0 && tsol[*r].npremoves > 0) if (!appendchar(list, ' ')) - return false; + goto appendsolution_dfs_error_buffer; - if (!appendnormal(&tsol[r], list)) - goto appendsolution_error_buffer; + if (!appendnormal(&tsol[*r], list)) + goto appendsolution_dfs_error_buffer; } if (!appendchar(list, '\n')) - goto appendsolution_error_buffer; - + goto appendsolution_dfs_error_buffer; ++list->nsols; + + /* + Normaly, it would be enough to check for duplicates in the + current "pack" of transformation-equivalent solutions. + However, in rare cases, the H48 solver may produce equivalent + "packs" of solutions. It would be more elegant to filter out + the corresponding tasks in solve_h48_maketasks(), but doing so + is not trivial. In the end, duplicate solutions are never + desirable, so we might as well do this clean up here. + */ + if (last_solution_is_duplicate(list)) { + --list->nsols; + list->used = last_start; + return; + } + list->shortest_sol = MIN( - list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); - r++; + list->shortest_sol, tsol[*r].nmoves + tsol[*r].npremoves); + (*r)++; + } else { + for (t = 0; t < NTRANS; t++) { + if (!(tmask[itm] & TM_SINGLE(t))) + continue; + moves_copy = *moves; + tt[itm] = t; + appendsolution_dfs(&moves_copy, ntmask, tmask, + itm+1, tt, settings, list, tsol, r); + if (*r < 0) + return; + } } - list->buf[list->used] = '\0'; - return r; + return; -appendsolution_error_buffer: +appendsolution_dfs_error_buffer: list->buf[0] = '\0'; - return NISSY_ERROR_BUFFER_SIZE; + *r = NISSY_ERROR_BUFFER_SIZE; + return; +} + +STATIC int64_t +appendsolution( + const solution_moves_t moves[static 1], + size_t ntmask, + const uint64_t *tmask, + const solution_settings_t settings[static 1], + solution_list_t list[static 1] +) +{ + int64_t r; + int i; + uint8_t tt[SOLUTION_MAXLEN]; + solution_moves_t moves_copy, tsol[NTRANS * SOLUTION_MAXLEN]; + + if (moves->nmoves + moves->npremoves > SOLUTION_MAXLEN) + goto appendsolution_error_solution_length; + + moves_copy = *moves; + if (settings->unniss) { + moves_copy.nmoves += moves->npremoves; + moves_copy.npremoves = 0; + for (i = moves->npremoves-1; i >= 0; i--) + moves_copy.moves[moves_copy.nmoves - i - 1] = + inverse_move(moves->premoves[i]); + + /* + This is a bit ugly: we have to sort now and then again + later, because the allowedmoves check would fail with + improperly sorted parallel moves, but then transforming + could swap the pairs the wrong way around. + */ + sortparallel_moves(moves_copy.nmoves, moves_copy.moves); + + /* Check if unnissed premoves cancel with normal. */ + if (!allowedmoves(moves_copy.nmoves, moves_copy.moves)) + return 0; + } + + r = 0; + memset(tt, TRANS_UFr, SOLUTION_MAXLEN); + appendsolution_dfs( + &moves_copy, ntmask, tmask, 0, tt, settings, list, tsol, &r); + if (r < 0) + return r; + + list->buf[list->used] = '\0'; + return r; appendsolution_error_solution_length: list->buf[0] = '\0'; diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h @@ -8,7 +8,6 @@ typedef struct { } solution_moves_t; typedef struct { - uint64_t tmask; bool unniss; uint8_t maxmoves; uint64_t maxsolutions; diff --git a/test/140_appendsolution/00_empty.in b/test/140_appendsolution/00_empty.in @@ -1,5 +1,6 @@ 0 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/01_simple_onlynormal_nounniss.in b/test/140_appendsolution/01_simple_onlynormal_nounniss.in @@ -1,5 +1,6 @@ U F R D2 B' 0 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/02_simple_onlynormal_nounnis_multitrans.in b/test/140_appendsolution/02_simple_onlynormal_nounnis_multitrans.in @@ -1,5 +1,6 @@ U F R 0 +1 4 rotation UF mirrored UR diff --git a/test/140_appendsolution/03_simple_unniss.in b/test/140_appendsolution/03_simple_unniss.in @@ -1,5 +1,6 @@ U F B2 (R' F D) 1 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/04_niss_nounniss.in b/test/140_appendsolution/04_niss_nounniss.in @@ -1,5 +1,6 @@ U F B2 (R' F D) 0 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/05_sort_parallel.in b/test/140_appendsolution/05_sort_parallel.in @@ -1,5 +1,6 @@ L R' B2 F 0 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/06_unniss_trans_sort.in b/test/140_appendsolution/06_unniss_trans_sort.in @@ -1,5 +1,6 @@ B (R2 F2) 1 1 +1 rotation UR 0 diff --git a/test/140_appendsolution/07_unniss_cancel_nosol.in b/test/140_appendsolution/07_unniss_cancel_nosol.in @@ -1,5 +1,6 @@ B' F (R2 B2) 1 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/08_unniss_cancel_nosol_v2.in b/test/140_appendsolution/08_unniss_cancel_nosol_v2.in @@ -1,5 +1,6 @@ F' B (R2 F2) 1 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/09_fullinverse_niss.in b/test/140_appendsolution/09_fullinverse_niss.in @@ -1,5 +1,6 @@ (F) 0 1 +1 rotation UF 0 diff --git a/test/140_appendsolution/10_rotated.in b/test/140_appendsolution/10_rotated.in @@ -1,5 +1,6 @@ U2 F B L' 1 1 +1 rotation UF 7 diff --git a/test/140_appendsolution/11_multisym.in b/test/140_appendsolution/11_multisym.in @@ -0,0 +1,10 @@ +L U F +0 +2 +2 +rotation UF +rotation UB +2 +rotation UF +rotation DR +0 diff --git a/test/140_appendsolution/11_multisym.out b/test/140_appendsolution/11_multisym.out @@ -0,0 +1,7 @@ +L U F +L D R +R U B +R D L +Number of solutions: 4 +Shortest solution length: 3 +Used bytes: 24 diff --git a/test/140_appendsolution/appendsolution_tests.c b/test/140_appendsolution/appendsolution_tests.c @@ -3,8 +3,10 @@ Input format for appendsolution tests: moves on normal (with NISS notation) unniss flag (0=false, 1=true) -number of transformations -transformations, one per line +n = maximum number of moves for transformations + 1 (at most 20) +n times the following: + number of transformations + transformations, one per line the orientation of the cube, as a number from 0 to 23 See below for the output format. @@ -18,11 +20,13 @@ int64_t readmoves(const char *, size_t n, size_t m, void solution_moves_reset(solution_moves_t [static 1]); bool solution_list_init(solution_list_t [static 1], size_t n, char [n]); int64_t appendsolution(const solution_moves_t [static 1], - const solution_settings_t [static 1], solution_list_t [static 1]); + size_t, const uint64_t *, const solution_settings_t [static 1], + solution_list_t [static 1]); void run(void) { - int i, ntrans; + int i, j, nnt, ntrans; int64_t tot; + uint64_t tmask[20]; size_t nm, np; char str[STRLENMAX], buf[STRLENMAX]; solution_moves_t moves; @@ -32,7 +36,6 @@ void run(void) { solution_moves_reset(&moves); solution_list_init(&list, STRLENMAX, buf); settings = (solution_settings_t) { - .tmask = UINT64_C(0), .unniss = false, .maxmoves = 20, .maxsolutions = 100, @@ -49,16 +52,21 @@ void run(void) { moves.npremoves = np; fgets(str, STRLENMAX, stdin); settings.unniss = (bool)atoi(str); + fgets(str, STRLENMAX, stdin); - ntrans = atoi(str); - for (i = 0; i < ntrans; i++) { + nnt = atoi(str); + for (j = 0; j < nnt; j++) { fgets(str, STRLENMAX, stdin); - settings.tmask |= UINT64_C(1) << (uint64_t)readtrans(str); + ntrans = atoi(str); + for (i = 0; i < ntrans; i++) { + fgets(str, STRLENMAX, stdin); + tmask[j] |= UINT64_C(1) << (uint64_t)readtrans(str); + } } fgets(str, STRLENMAX, stdin); settings.orientation = atoi(str); - appendsolution(&moves, &settings, &list); + appendsolution(&moves, nnt, tmask, &settings, &list); printf("%s", list.buf); printf("Number of solutions: %" PRIu64 "\n", list.nsols); diff --git a/tools/301_solve_file/solve_file.c b/tools/301_solve_file/solve_file.c @@ -1,6 +1,6 @@ #include "../tool.h" -#define SOL_BUFFER_LEN 100000 +#define SOL_BUFFER_LEN 1000000 #define MAX_SCR 10000 #define MAX_SCR_LEN 250 diff --git a/tools/420_solvetest_h48_symmetric/scrambles.h b/tools/420_solvetest_h48_symmetric/scrambles.h @@ -0,0 +1,18 @@ +struct { + char *scramble; + char *solutions; +} s[] = { +[0] = { + .scramble = "M2 E2 S2", + .solutions = + "U2 D2 F2 B2 R2 L2\n" + "U2 D2 R2 L2 F2 B2\n" + "R2 L2 U2 D2 F2 B2\n" + "R2 L2 F2 B2 U2 D2\n" + "F2 B2 U2 D2 R2 L2\n" + "F2 B2 R2 L2 U2 D2\n" +}, +{ + .scramble = "", /* End-of-list signal */ +} +}; diff --git a/tools/420_solvetest_h48_symmetric/solvetest.c b/tools/420_solvetest_h48_symmetric/solvetest.c @@ -0,0 +1,9 @@ +#define SOLVER "h48h3k2" +#define NISSFLAG NISSY_NISSFLAG_NORMAL +#define MINMOVES 0 +#define MAXMOVES 20 +#define MAXSOLUTIONS 500 +#define OPTIMAL 0 + +#include "scrambles.h" +#include "../solvetest.h"