commit 4d0b1a53f04f1c5bc95de20fb92b2bd9cf16a895 parent 3ca4814562f6c756e9a110dab7d54cda30267fb1 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue, 25 Nov 2025 18:03:50 +0100 Merge branch 'master' of tronto.net:nissy-core 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"