From 78ec0d22d927bc4287aa090469d5ba5f84e8780b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 25 Sep 2025 22:17:31 +0200 Subject: Recovered comment that appeared only in removed file --- web/storage.cpp | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) diff --git a/web/storage.cpp b/web/storage.cpp index d540a5c..780926e 100644 --- a/web/storage.cpp +++ b/web/storage.cpp @@ -43,7 +43,12 @@ EM_ASYNC_JS(int, download_and_store, (const char *key, const char *url), { self instanceof WorkerGlobalScope; console.assert(inBrowser || inWorker, "Non-browsers not supported"); - // See comment in callback.js about this workaround + // This is a workaround related to usign WASM64 + // JavaScript's UTF8ToString expects a pointer argument, which for JS is + // of type "number", but WASM64 is passing a BigInt. See also: + // https://github.com/emscripten-core/emscripten/issues/21541 + // (but I could not make the suggested solution work in this case). + // TODO: check if there is a better workaround. const non64_url = Number(url); const non64_key = Number(key); url = UTF8ToString(non64_url); -- cgit v1.3 From 147b0c3c4615c32478a4923242909b8ae5a30d03 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 23 Nov 2025 16:16:31 +0100 Subject: 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. --- .gitignore | 1 + benchmarks/benchmarks.md | 64 +++--- src/solvers/coord/multisolve.h | 9 +- src/solvers/coord/solve.h | 9 +- src/solvers/h48/solve.h | 78 +++---- src/solvers/solutions.h | 228 ++++++++++++++------- src/solvers/solutions_types_macros.h | 1 - test/140_appendsolution/00_empty.in | 1 + .../01_simple_onlynormal_nounniss.in | 1 + .../02_simple_onlynormal_nounnis_multitrans.in | 1 + test/140_appendsolution/03_simple_unniss.in | 1 + test/140_appendsolution/04_niss_nounniss.in | 1 + test/140_appendsolution/05_sort_parallel.in | 1 + test/140_appendsolution/06_unniss_trans_sort.in | 1 + test/140_appendsolution/07_unniss_cancel_nosol.in | 1 + .../08_unniss_cancel_nosol_v2.in | 1 + test/140_appendsolution/09_fullinverse_niss.in | 1 + test/140_appendsolution/10_rotated.in | 1 + test/140_appendsolution/11_multisym.in | 10 + test/140_appendsolution/11_multisym.out | 7 + test/140_appendsolution/appendsolution_tests.c | 26 ++- tools/301_solve_file/solve_file.c | 2 +- tools/420_solvetest_h48_symmetric/scrambles.h | 18 ++ tools/420_solvetest_h48_symmetric/solvetest.c | 9 + 24 files changed, 311 insertions(+), 162 deletions(-) create mode 100644 test/140_appendsolution/11_multisym.in create mode 100644 test/140_appendsolution/11_multisym.out create mode 100644 tools/420_solvetest_h48_symmetric/scrambles.h create mode 100644 tools/420_solvetest_h48_symmetric/solvetest.c diff --git a/.gitignore b/.gitignore index de7c8b6..3918e43 100644 --- 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 index f84ddb3..33e8288 100644 --- 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 index f3589e8..a45bd6a 100644 --- 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 index 54309b1..9ea6d1a 100644 --- 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 index bf10723..ad66fd4 100644 --- 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 index 9f209d1..d92d5ad 100644 --- 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 index c8efc0b..4727e5a 100644 --- 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 index 1100b95..00546ef 100644 --- 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 index fb1eaed..84d16c0 100644 --- 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 index db5f074..15ff39e 100644 --- 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 index 2c5a331..ac6fe72 100644 --- 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 index b07f970..cae1328 100644 --- 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 index bc1cf0f..85351b5 100644 --- 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 index 2ffab93..e6b7897 100644 --- 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 index 6883d05..4faed6b 100644 --- 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 index 3d461f0..741687a 100644 --- 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 index bb2b640..e2e5f7b 100644 --- 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 index 5210cd5..947696f 100644 --- 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 new file mode 100644 index 0000000..947127f --- /dev/null +++ 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 new file mode 100644 index 0000000..9f1a312 --- /dev/null +++ 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 index d4c2a1f..f9620ab 100644 --- 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 index a8f0925..ef9bf2c 100644 --- 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 new file mode 100644 index 0000000..33f1643 --- /dev/null +++ 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 new file mode 100644 index 0000000..245b7fe --- /dev/null +++ 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" -- cgit v1.3