From 6cf7cd87a90a1314332aace1d25b9c0f230dc227 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 29 Jul 2025 16:57:21 +0200 Subject: added drslice coordinate --- src/solvers/coord/common.h | 19 ++++++- src/solvers/coord/coord.h | 1 + src/solvers/coord/dr.h | 5 +- src/solvers/coord/dreo.h | 5 +- src/solvers/coord/drfinnoe.h | 42 +++------------ src/solvers/coord/drslice.h | 113 +++++++++++++++++++++++++++++++++++++++ src/solvers/coord/eo.h | 7 ++- src/solvers/coord/gendata.h | 38 ++++++++++--- src/solvers/coord/list.h | 1 + src/solvers/coord/solve.h | 12 +++-- src/solvers/coord/types_macros.h | 6 ++- 11 files changed, 197 insertions(+), 52 deletions(-) create mode 100644 src/solvers/coord/drslice.h (limited to 'src/solvers/coord') diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h index d38b7d3..901b8bd 100644 --- a/src/solvers/coord/common.h +++ b/src/solvers/coord/common.h @@ -10,6 +10,8 @@ STATIC void append_coord_name(const coord_t [static 1], char *); STATIC bool solution_lastqt_cw(const solution_moves_t [static 1]); STATIC bool coord_can_switch(const coord_t [static 1], const unsigned char *, size_t, const uint8_t *); +STATIC bool coord_is_solved( + const coord_t [static 1], uint64_t, const unsigned char *); STATIC uint64_t coord_coord_generic( @@ -182,8 +184,11 @@ coord_can_switch( uint64_t i; - if (n == 0) - return true; + DBG_ASSERT(n > 0, "Error: cannot check if coordinate solver " + "can use NISS after 0 moves"); + + if (!coord->allow_niss) + return false; i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data); if (i == 0) @@ -195,3 +200,13 @@ coord_can_switch( i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data); return i != 0; } + +STATIC bool +coord_is_solved( + const coord_t coord[static 1], + uint64_t i, + const unsigned char *data +) +{ + return coord->is_solved == NULL ? i == 0 : coord->is_solved(i, data); +} diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h index e487964..3b42e31 100644 --- a/src/solvers/coord/coord.h +++ b/src/solvers/coord/coord.h @@ -4,6 +4,7 @@ #include "dr.h" #include "dreo.h" #include "drfinnoe.h" +#include "drslice.h" #include "list.h" #include "utils.h" #include "gendata.h" diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h index 7f7af4f..487e79c 100644 --- a/src/solvers/coord/dr.h +++ b/src/solvers/coord/dr.h @@ -20,7 +20,8 @@ STATIC coord_t coordinate_dr = { .gendata = coordinate_dr_gendata, .max = DREOESEP_CLASSES * POW_3_7, .trans_mask = TM_UDFIX, - .moves_mask = MM18_ALLMOVES, + .moves_mask_gendata = MM18_ALLMOVES, + .moves_mask_solve = MM18_ALLMOVES, .axistrans = { [AXIS_UD] = TRANS_UFr, [AXIS_RL] = TRANS_RFr, @@ -28,6 +29,8 @@ STATIC coord_t coordinate_dr = { }, .is_admissible = &solution_lastqt_cw, .is_solvable = &is_eoco_solvable, + .is_solved = NULL, + .allow_niss = true, .pruning_distribution = { [0] = 1, [1] = 1, diff --git a/src/solvers/coord/dreo.h b/src/solvers/coord/dreo.h index 31f7008..8780807 100644 --- a/src/solvers/coord/dreo.h +++ b/src/solvers/coord/dreo.h @@ -19,7 +19,8 @@ STATIC coord_t coordinate_dreo = { .gendata = coordinate_dreo_gendata, .max = DRESEP_CLASSES * POW_3_7, .trans_mask = TM_UDRLFIX, - .moves_mask = MM18_EO, + .moves_mask_gendata = MM18_EO, + .moves_mask_solve = MM18_EO, .axistrans = { [AXIS_UD] = TRANS_UFr, [AXIS_RL] = TRANS_RFr, @@ -27,6 +28,8 @@ STATIC coord_t coordinate_dreo = { }, .is_admissible = &solution_lastqt_cw, .is_solvable = &is_dreo_solvable, + .is_solved = NULL, + .allow_niss = true, .pruning_distribution = { [0] = 1, [1] = 1, diff --git a/src/solvers/coord/drfinnoe.h b/src/solvers/coord/drfinnoe.h index 984b10a..c088ac4 100644 --- a/src/solvers/coord/drfinnoe.h +++ b/src/solvers/coord/drfinnoe.h @@ -13,12 +13,7 @@ In the worst case, it is a bug to be fixed, but I find it unlikely. #define CLASSES_CP_16 2768 -STATIC uint64_t coordinate_cp_coord(cube_t); -STATIC cube_t coordinate_cp_cube(uint64_t); -STATIC uint64_t coordinate_epud_coord(cube_t); -STATIC cube_t coordinate_epud_cube(uint64_t); STATIC cube_t coordinate_drfinnoe_merge(cube_t, cube_t); - STATIC uint64_t coordinate_drfinnoe_coord(cube_t, const unsigned char *); STATIC cube_t coordinate_drfinnoe_cube(uint64_t, const unsigned char *); STATIC bool coordinate_drfinnoe_isnasty(uint64_t, const unsigned char *); @@ -34,7 +29,8 @@ STATIC coord_t coordinate_drfinnoe = { .gendata = coordinate_drfinnoe_gendata, .max = CLASSES_CP_16 * FACT_8, .trans_mask = TM_UDFIX, - .moves_mask = MM18_DR, + .moves_mask_gendata = MM18_DR, + .moves_mask_solve = MM18_DR, .axistrans = { [AXIS_UD] = TRANS_UFr, [AXIS_RL] = TRANS_RFr, @@ -42,6 +38,8 @@ STATIC coord_t coordinate_drfinnoe = { }, .is_admissible = &solution_always_valid, .is_solvable = &is_drfinnoe_solvable, + .is_solved = NULL, + .allow_niss = false, .pruning_distribution = { [0] = 1, [1] = 3, @@ -64,39 +62,15 @@ STATIC coord_t coordinate_drfinnoe = { .sym = { .classes = CLASSES_CP_16, .max = FACT_8, - .coord = &coordinate_cp_coord, - .cube = &coordinate_cp_cube, + .coord = &coord_cp, + .cube = &invcoord_cp, .max2 = FACT_8, - .coord2 = &coordinate_epud_coord, - .cube2 = &coordinate_epud_cube, + .coord2 = &coord_epud, + .cube2 = &invcoord_epud, .merge = &coordinate_drfinnoe_merge, }, }; -STATIC uint64_t -coordinate_cp_coord(cube_t c) -{ - return coord_cp(c); -} - -STATIC cube_t -coordinate_cp_cube(uint64_t i) -{ - return invcoord_cp(i); -} - -STATIC uint64_t -coordinate_epud_coord(cube_t c) -{ - return coord_epud(c); -} - -STATIC cube_t -coordinate_epud_cube(uint64_t i) -{ - return invcoord_epud(i); -} - STATIC cube_t coordinate_drfinnoe_merge(cube_t c1, cube_t c2) { diff --git a/src/solvers/coord/drslice.h b/src/solvers/coord/drslice.h new file mode 100644 index 0000000..4299b30 --- /dev/null +++ b/src/solvers/coord/drslice.h @@ -0,0 +1,113 @@ +/* +The DRSLICE coordinate is almost identical to DRFINNOE, but it allows for +the centers of the E layer to be off by a rotation. For this reason we reuse +much of the code of DRFINNOE. We could make the pruning table 4x smaller +if we reduced the coordinate by rotations. TODO. +*/ + +STATIC cube_t coordinate_drslice_merge(cube_t, cube_t); +STATIC uint64_t coordinate_drslice_coord(cube_t, const unsigned char *); +STATIC cube_t coordinate_drslice_cube(uint64_t, const unsigned char *); +STATIC bool coordinate_drslice_isnasty(uint64_t, const unsigned char *); +STATIC size_t coordinate_drslice_gendata(unsigned char *); +STATIC bool is_drslice_solvable(cube_t); +STATIC bool is_drslice_solved(uint64_t, const unsigned char *); + +STATIC coord_t coordinate_drslice = { + .name = "DRSLICE", + .coord = &coordinate_drslice_coord, + .cube = &coordinate_drslice_cube, + .isnasty = &coordinate_drslice_isnasty, + .gendata = coordinate_drslice_gendata, + .max = CLASSES_CP_16 * FACT_8, + .trans_mask = TM_UDFIX, + .moves_mask_gendata = MM18_DR, + .moves_mask_solve = MM18_DR_NOD, + .axistrans = { + [AXIS_UD] = TRANS_UFr, + [AXIS_RL] = TRANS_RFr, + [AXIS_FB] = TRANS_FDr, + }, + .is_admissible = &solution_always_valid, + .is_solvable = &is_drslice_solvable, + .is_solved = &is_drslice_solved, + .allow_niss = false, + .pruning_distribution = { + [0] = 3, + [1] = 7, + [2] = 18, + [3] = 111, + [4] = 433, + [5] = 1618, + [6] = 6718, + [7] = 29182, + [8] = 119873, + [9] = 476999, + [10] = 1858350, + [11] = 6531166, + [12] = 18338522, + [13] = 32839235, + [14] = 34118824, + [15] = 17284701 + }, + .pruning_max = 15, + .sym = { + .classes = CLASSES_CP_16, + .max = FACT_8, + .coord = &coord_cp, + .cube = &invcoord_cp, + .max2 = FACT_8, + .coord2 = &coord_epud, + .cube2 = &invcoord_epud, + .merge = &coordinate_drslice_merge, + }, +}; + +STATIC cube_t +coordinate_drslice_merge(cube_t c1, cube_t c2) +{ + cube_t merged; + + merged = c1; + copy_edges(&merged, c2); + + return merged; +} + +STATIC uint64_t +coordinate_drslice_coord(cube_t cube, const unsigned char *data) +{ + return coord_coord_generic(&coordinate_drslice, cube, data); +} + +STATIC cube_t +coordinate_drslice_cube(uint64_t i, const unsigned char *data) +{ + return coord_cube_generic(&coordinate_drslice, i, data); +} + +STATIC size_t +coordinate_drslice_gendata(unsigned char *data) +{ + return coord_gendata_generic(&coordinate_drslice, data); +} + +STATIC bool +coordinate_drslice_isnasty(uint64_t i, const unsigned char *data) +{ + return coord_isnasty_generic(&coordinate_drslice, i, data); +} + +STATIC bool +is_drslice_solvable(cube_t cube) { + return coord_eo(cube) == 0 && + coord_eo(transform_edges(cube, TRANS_URr)) == 0 && + coord_co(cube) == 0; +} + +STATIC bool +is_drslice_solved(uint64_t i, const unsigned char *data) +{ + /* Pre-computed coordinates of U D' (= U' D up to trans) and U2 D2 */ + return i == 0 || i == 109779816 || i == 68468527; +} diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h index b963832..86e09e9 100644 --- a/src/solvers/coord/eo.h +++ b/src/solvers/coord/eo.h @@ -12,7 +12,8 @@ STATIC coord_t coordinate_eo = { .gendata = coordinate_eo_gendata, .max = POW_2_11, .trans_mask = TM_SINGLE(TRANS_UFr), - .moves_mask = MM18_ALLMOVES, + .moves_mask_gendata = MM18_ALLMOVES, + .moves_mask_solve = MM18_ALLMOVES, .axistrans = { [AXIS_UD] = TRANS_FDr, [AXIS_RL] = TRANS_URr, @@ -20,6 +21,8 @@ STATIC coord_t coordinate_eo = { }, .is_admissible = &solution_lastqt_cw, .is_solvable = &is_eo_even, + .is_solved = NULL, + .allow_niss = true, .pruning_distribution = { [0] = 1, [1] = 2, @@ -37,7 +40,7 @@ STATIC coord_t coordinate_eo = { STATIC uint64_t coordinate_eo_coord(cube_t c, const unsigned char *data) { - return (uint64_t)coord_eo(c); + return coord_eo(c); } STATIC cube_t diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h index 678bfd7..75c57e4 100644 --- a/src/solvers/coord/gendata.h +++ b/src/solvers/coord/gendata.h @@ -3,6 +3,8 @@ STATIC long long gendata_coord_dispatch(const char *, unsigned long long, unsigned char *); STATIC tableinfo_t genptable_coord( const coord_t [static 1], const unsigned char *, unsigned char *); +STATIC uint64_t genptable_coord_init_solved( + const coord_t [static 1], const unsigned char *, unsigned char *); STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t); STATIC uint64_t genptable_coord_fillneighbors(const coord_t [static 1], const unsigned char *, uint64_t, uint8_t, unsigned char *); @@ -118,11 +120,10 @@ genptable_coord( memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); append_coord_name(coord, info.solver); - nm = popcount_u32(coord->moves_mask); - i = coord->coord(SOLVED_CUBE, data); - set_coord_pval(coord, table, i, 0); - info.distribution[0] = 1; - for (d = 1, tot = 1; tot < coord->max && d < 15; d++) { + tot = info.distribution[0] = + genptable_coord_init_solved(coord, data, table); + nm = popcount_u32(coord->moves_mask_gendata); + for (d = 1; tot < coord->max && d < 15; d++) { t = 0; if (switch_to_fromnew(tot, coord->max, nm)) { for (i = 0; i < coord->max; i++) @@ -153,6 +154,27 @@ genptable_coord( return info; } +STATIC uint64_t +genptable_coord_init_solved( + const coord_t coord[static 1], + const unsigned char *coord_data, + unsigned char *table +) +{ + uint64_t i, max_solved, ret; + + max_solved = coord->is_solved == NULL ? 1 : coord->max; + + for (i = 0, ret = 0; i < max_solved; i++) { + if (coord_is_solved(coord, i, coord_data)) { + set_coord_pval(coord, table, i, 0); + ret++; + } + } + + return ret; +} + STATIC bool switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm) { @@ -183,7 +205,8 @@ genptable_coord_fillneighbors( c = coord->cube(i, data); tot = 0; for (m = 0; m < NMOVES; m++) { - if (!((UINT32_C(1) << (uint32_t)m) & coord->moves_mask)) + if (!((UINT32_C(1) << (uint32_t)m) & + coord->moves_mask_gendata)) continue; moved = move(c, m); ii = coord->coord(moved, data); @@ -234,7 +257,8 @@ genptable_coord_fillfromnew( for (j = 0, found = false; j < nsim && !found; j++) { c = coord->cube(sim[j], data); for (m = 0; m < NMOVES; m++) { - if (!((UINT32_C(1) << (uint32_t)m) & coord->moves_mask)) + if (!((UINT32_C(1) << (uint32_t)m) & + coord->moves_mask_gendata)) continue; ii = coord->coord(move(c, m), data); if (get_coord_pval(coord, table, ii) < d) { diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h index a3d3206..929e0fd 100644 --- a/src/solvers/coord/list.h +++ b/src/solvers/coord/list.h @@ -3,5 +3,6 @@ coord_t *all_coordinates[] = { &coordinate_dr, &coordinate_dreo, &coordinate_drfinnoe, + &coordinate_drslice, NULL }; diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index 75ec200..280ca36 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -76,6 +76,7 @@ coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1]) if (nn + ni == 0) return f & (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_MIXED); + /* TODO logic here can probably be simplified */ if (arg->lastisnormal) return (f & NISSY_NISSFLAG_NORMAL) || ((f & NISSY_NISSFLAG_MIXED) && (ni > 0 || nn <= th)); @@ -98,6 +99,7 @@ coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1]) if (nn + ni == 0) return f & (NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED); + /* TODO logic here can probably be simplified */ if (!arg->lastisnormal) return (f & NISSY_NISSFLAG_INVERSE) || ((f & NISSY_NISSFLAG_MIXED) && (nn > 0 || ni < th)); @@ -118,7 +120,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) cube_t backup_cube, backup_inverse; coord = arg->coord->coord(arg->cube, arg->coord_data); - if (coord == 0) { + if (coord_is_solved(arg->coord, coord, arg->coord_data)) { if (!coord_solution_admissible(arg)) return 0; return appendsolution(arg->solution_moves, @@ -137,7 +139,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) ret = 0; if (coord_continue_onnormal(arg)) { l = arg->solution_moves->nmoves; - mm = arg->coord->moves_mask; + mm = arg->coord->moves_mask_solve; if (l != 0) { m = arg->solution_moves->moves[l-1]; mm &= allowedmask[movebase(m)]; @@ -166,7 +168,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) if (coord_continue_oninverse(arg)) { l = arg->solution_moves->npremoves; - mm = arg->coord->moves_mask; + mm = arg->coord->moves_mask_solve; if (l != 0) { m = arg->solution_moves->premoves[l-1]; mm &= allowedmask[movebase(m)]; @@ -260,6 +262,7 @@ solve_coord( int8_t d; uint8_t t; int64_t ndepth; + uint64_t i; cube_t c; const unsigned char *coord_data; const unsigned char *ptable; @@ -314,7 +317,8 @@ solve_coord( .nissflag = nissflag, }; - if (coord->coord(c, coord_data) == 0) { + i = coord->coord(c, coord_data); + if (coord_is_solved(coord, i, coord_data)) { if (minmoves == 0 && !appendsolution(&solution_moves, &solution_settings, &solution_list)) goto solve_coord_error_buffer; diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h index 0c7a3a2..2acf146 100644 --- a/src/solvers/coord/types_macros.h +++ b/src/solvers/coord/types_macros.h @@ -21,13 +21,17 @@ typedef struct { bool (*isnasty)(uint64_t, const unsigned char *); size_t (*gendata)(unsigned char *); uint64_t max; - uint64_t moves_mask; + /* moves_mask_gendata must be invariant under trans_mask */ + uint64_t moves_mask_gendata; + uint64_t moves_mask_solve; uint64_t trans_mask; uint8_t axistrans[3]; bool (*is_admissible)(const solution_moves_t[static 1]); bool (*is_solvable)(cube_t); + bool (*is_solved)(uint64_t, const unsigned char *); uint64_t pruning_distribution[INFO_DISTRIBUTION_LEN]; uint8_t pruning_max; + bool allow_niss; struct { size_t classes; uint64_t max; -- cgit v1.3