From 57a7520545134ab95f7bb0397dcbe991c906a3e9 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 6 Aug 2025 16:34:21 +0200 Subject: Added HTR solver --- src/solvers/coord/common.h | 24 +++++++- src/solvers/coord/coord.h | 1 + src/solvers/coord/cpepe.h | 15 +---- src/solvers/coord/dr.h | 15 +---- src/solvers/coord/dreo.h | 15 +---- src/solvers/coord/drfinnoe.h | 15 +---- src/solvers/coord/drslice.h | 15 +---- src/solvers/coord/eo.h | 1 + src/solvers/coord/htr.h | 125 +++++++++++++++++++++++++++++++++++++++ src/solvers/coord/list.h | 1 + src/solvers/coord/solve.h | 4 ++ src/solvers/coord/types_macros.h | 1 + 12 files changed, 164 insertions(+), 68 deletions(-) create mode 100644 src/solvers/coord/htr.h (limited to 'src/solvers/coord') diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h index 5b5f57b..5f2435d 100644 --- a/src/solvers/coord/common.h +++ b/src/solvers/coord/common.h @@ -12,6 +12,9 @@ STATIC bool coord_can_switch(const coord_t [static 1], const unsigned char *, STATIC bool coord_is_solved( const coord_t [static 1], uint64_t, const unsigned char *); +STATIC cube_t coordinate_merge_ce(cube_t, cube_t); +STATIC cube_t coordinate_merge_ec(cube_t, cube_t); + STATIC uint64_t coord_coord_generic( const coord_t coord[static 1], @@ -19,13 +22,11 @@ coord_coord_generic( const unsigned char *data ) { - const unsigned char *datanoinfo; const uint32_t *data32; uint32_t d; cube_t tr; - datanoinfo = data + INFOSIZE; - data32 = (const uint32_t *)datanoinfo; + data32 = (const uint32_t *)(data + INFOSIZE); d = data32[coord->sym.coord(c)]; tr = transform(c, COORD_TTREP(d)); @@ -197,3 +198,20 @@ coord_is_solved( { return coord->is_solved == NULL ? i == 0 : coord->is_solved(i, data); } + +STATIC cube_t +coordinate_merge_ce(cube_t corners, cube_t edges) +{ + cube_t merged; + + merged = corners; + copy_edges(&merged, edges); + + return merged; +} + +STATIC cube_t +coordinate_merge_ec(cube_t edges, cube_t corners) +{ + return coordinate_merge_ce(corners, edges); +} diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h index beb1b6a..db40239 100644 --- a/src/solvers/coord/coord.h +++ b/src/solvers/coord/coord.h @@ -7,6 +7,7 @@ #include "drslice.h" #include "cpepe.h" #include "drfin.h" +#include "htr.h" #include "list.h" #include "utils.h" #include "gendata.h" diff --git a/src/solvers/coord/cpepe.h b/src/solvers/coord/cpepe.h index 9c9bffc..7035400 100644 --- a/src/solvers/coord/cpepe.h +++ b/src/solvers/coord/cpepe.h @@ -1,4 +1,3 @@ -STATIC cube_t coordinate_cpepe_merge(const cube_t, const cube_t); STATIC uint64_t coordinate_cpepe_coord(const cube_t, const unsigned char *); STATIC cube_t coordinate_cpepe_cube(uint64_t, const unsigned char *); STATIC bool coordinate_cpepe_isnasty(uint64_t, const unsigned char *); @@ -15,6 +14,7 @@ STATIC coord_t coordinate_cpepe = { .moves_mask_gendata = MM18_DR, .moves_mask_solve = MM18_DR, .is_admissible = &solution_always_valid, + .solution_prune = NULL, .is_solvable = &is_drfinnoe_solvable, .is_solved = NULL, .allow_niss = false, @@ -44,21 +44,10 @@ STATIC coord_t coordinate_cpepe = { .max2 = FACT_4, .coord2 = &coord_epe, .cube2 = &invcoord_epe, - .merge = &coordinate_cpepe_merge, + .merge = &coordinate_merge_ce, }, }; -STATIC cube_t -coordinate_cpepe_merge(const cube_t c1, const cube_t c2) -{ - cube_t merged; - - merged = c1; - copy_edges(&merged, c2); - - return merged; -} - STATIC uint64_t coordinate_cpepe_coord(const cube_t cube, const unsigned char *data) { diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h index 03473df..8100910 100644 --- a/src/solvers/coord/dr.h +++ b/src/solvers/coord/dr.h @@ -3,7 +3,6 @@ STATIC uint64_t coord_dreoesep_nosym(cube_t); STATIC cube_t invcoord_dreoesep_nosym(uint64_t); -STATIC cube_t coordinate_dr_merge(cube_t, cube_t); STATIC uint64_t coordinate_dr_coord(cube_t, const unsigned char *); STATIC cube_t coordinate_dr_cube(uint64_t, const unsigned char *); @@ -23,6 +22,7 @@ STATIC coord_t coordinate_dr = { .moves_mask_gendata = MM18_ALLMOVES, .moves_mask_solve = MM18_ALLMOVES, .is_admissible = &solution_lastqt_cw, + .solution_prune = NULL, .is_solvable = &is_eoco_solvable, .is_solved = NULL, .allow_niss = true, @@ -50,7 +50,7 @@ STATIC coord_t coordinate_dr = { .max2 = POW_3_7, .coord2 = &coord_co, .cube2 = &invcoord_co, - .merge = &coordinate_dr_merge, + .merge = &coordinate_merge_ec, }, }; @@ -79,17 +79,6 @@ invcoord_dreoesep_nosym(uint64_t coord) return cube; } -STATIC cube_t -coordinate_dr_merge(cube_t c1, cube_t c2) -{ - cube_t merged; - - merged = c1; - copy_corners(&merged, c2); - - return merged; -} - STATIC uint64_t coordinate_dr_coord(cube_t cube, const unsigned char *data) { diff --git a/src/solvers/coord/dreo.h b/src/solvers/coord/dreo.h index f563129..c5cacac 100644 --- a/src/solvers/coord/dreo.h +++ b/src/solvers/coord/dreo.h @@ -2,7 +2,6 @@ STATIC uint64_t coord_dresep_nosym(cube_t); STATIC cube_t invcoord_dresep_nosym(uint64_t); -STATIC cube_t coordinate_dreo_merge(cube_t, cube_t); STATIC uint64_t coordinate_dreo_coord(cube_t, const unsigned char *); STATIC cube_t coordinate_dreo_cube(uint64_t, const unsigned char *); @@ -22,6 +21,7 @@ STATIC coord_t coordinate_dreo = { .moves_mask_gendata = MM18_EO, .moves_mask_solve = MM18_EO, .is_admissible = &solution_lastqt_cw, + .solution_prune = NULL, .is_solvable = &is_dreo_solvable, .is_solved = NULL, .allow_niss = true, @@ -47,7 +47,7 @@ STATIC coord_t coordinate_dreo = { .max2 = POW_3_7, .coord2 = &coord_co, .cube2 = &invcoord_co, - .merge = &coordinate_dreo_merge, + .merge = &coordinate_merge_ec, }, }; @@ -63,17 +63,6 @@ invcoord_dresep_nosym(uint64_t coord) return invcoord_esep(coord * COMB_8_4); } -STATIC cube_t -coordinate_dreo_merge(cube_t c1, cube_t c2) -{ - cube_t merged; - - merged = c1; - copy_corners(&merged, c2); - - return merged; -} - STATIC uint64_t coordinate_dreo_coord(cube_t cube, const unsigned char *data) { diff --git a/src/solvers/coord/drfinnoe.h b/src/solvers/coord/drfinnoe.h index 4370779..63f4edf 100644 --- a/src/solvers/coord/drfinnoe.h +++ b/src/solvers/coord/drfinnoe.h @@ -13,7 +13,6 @@ In the worst case, it is a bug to be fixed, but I find it unlikely. #define CLASSES_CP_16 2768 -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 *); @@ -32,6 +31,7 @@ STATIC coord_t coordinate_drfinnoe = { .moves_mask_gendata = MM18_DR, .moves_mask_solve = MM18_DR, .is_admissible = &solution_always_valid, + .solution_prune = NULL, .is_solvable = &is_drfinnoe_solvable, .is_solved = NULL, .allow_niss = false, @@ -62,21 +62,10 @@ STATIC coord_t coordinate_drfinnoe = { .max2 = FACT_8, .coord2 = &coord_epud, .cube2 = &invcoord_epud, - .merge = &coordinate_drfinnoe_merge, + .merge = &coordinate_merge_ce, }, }; -STATIC cube_t -coordinate_drfinnoe_merge(cube_t c1, cube_t c2) -{ - cube_t merged; - - merged = c1; - copy_edges(&merged, c2); - - return merged; -} - STATIC uint64_t coordinate_drfinnoe_coord(cube_t cube, const unsigned char *data) { diff --git a/src/solvers/coord/drslice.h b/src/solvers/coord/drslice.h index c9403f8..42699f8 100644 --- a/src/solvers/coord/drslice.h +++ b/src/solvers/coord/drslice.h @@ -5,7 +5,6 @@ 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 *); @@ -24,6 +23,7 @@ STATIC coord_t coordinate_drslice = { .moves_mask_gendata = MM18_DR, .moves_mask_solve = MM18_DR_NOD, .is_admissible = &solution_always_valid, + .solution_prune = NULL, .is_solvable = &is_drslice_solvable, .is_solved = &is_drslice_solved, .allow_niss = false, @@ -54,21 +54,10 @@ STATIC coord_t coordinate_drslice = { .max2 = FACT_8, .coord2 = &coord_epud, .cube2 = &invcoord_epud, - .merge = &coordinate_drslice_merge, + .merge = &coordinate_merge_ce, }, }; -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) { diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h index 5c823a1..42196af 100644 --- a/src/solvers/coord/eo.h +++ b/src/solvers/coord/eo.h @@ -14,6 +14,7 @@ STATIC coord_t coordinate_eo = { .moves_mask_gendata = MM18_ALLMOVES, .moves_mask_solve = MM18_ALLMOVES, .is_admissible = &solution_lastqt_cw, + .solution_prune = NULL, .is_solvable = &is_eo_even, .is_solved = NULL, .allow_niss = true, diff --git a/src/solvers/coord/htr.h b/src/solvers/coord/htr.h new file mode 100644 index 0000000..cfd451b --- /dev/null +++ b/src/solvers/coord/htr.h @@ -0,0 +1,125 @@ +STATIC uint64_t coordinate_htr_coord(cube_t, const unsigned char *); +STATIC cube_t coordinate_htr_cube(uint64_t, const unsigned char *); +STATIC bool coordinate_htr_isnasty(uint64_t, const unsigned char *); +STATIC size_t coordinate_htr_gendata(unsigned char *); + +STATIC bool htr_checkmoves(bool *, uint8_t, const uint8_t *); +STATIC bool htr_solution_prune(const solution_moves_t [static 1]); +STATIC bool is_cp_htr(uint64_t, const unsigned char *); + +STATIC coord_t coordinate_htr = { + .name = "HTR", + .coord = &coordinate_htr_coord, + .cube = &coordinate_htr_cube, + .isnasty = &coordinate_htr_isnasty, + .gendata = coordinate_htr_gendata, + .max = CLASSES_CP_16 * COMB_8_4, + .trans_mask = TM_UDFIX, + .moves_mask_gendata = MM18_DR, + .moves_mask_solve = MM18_DRHTR, + .is_admissible = &solution_lastqt_cw, + .solution_prune = &htr_solution_prune, + .is_solvable = &is_drfinnoe_solvable, + .is_solved = &is_cp_htr, + .allow_niss = true, + .pruning_distribution = { + [0] = 22, + [1] = 18, + [2] = 86, + [3] = 268, + [4] = 920, + [5] = 4042, + [6] = 12716, + [7] = 24852, + [8] = 33116, + [9] = 45032, + [10] = 47144, + [11] = 21676, + [12] = 3692, + [13] = 176 + }, + .pruning_max = 13, + .sym = { + .classes = CLASSES_CP_16, + .max = FACT_8, + .coord = &coord_cp, + .cube = &invcoord_cp, + .max2 = COMB_8_4, + .coord2 = &coord_epudsep, + .cube2 = &invcoord_epudsep, + .merge = &coordinate_merge_ce, + }, +}; + +STATIC uint64_t +coordinate_htr_coord(cube_t cube, const unsigned char *data) +{ + return coord_coord_generic(&coordinate_htr, cube, data); +} + +STATIC cube_t +coordinate_htr_cube(uint64_t i, const unsigned char *data) +{ + return coord_cube_generic(&coordinate_htr, i, data); +} + +STATIC bool +coordinate_htr_isnasty(uint64_t i, const unsigned char *data) +{ + return coord_isnasty_generic(&coordinate_htr, i, data); +} + +STATIC size_t +coordinate_htr_gendata(unsigned char *data) +{ + return coord_gendata_generic(&coordinate_htr, data); +} + +STATIC bool +htr_checkmoves(bool *f, uint8_t n, const uint8_t *moves) +{ + uint8_t i; + bool is_d, is_u; + + for (i = 0; i < n; i++) { + is_d = moves[i] == MOVE_D || moves[i] == MOVE_D3; + is_u = moves[i] == MOVE_U || moves[i] == MOVE_U3; + if (is_d && *f) + return true; + *f = *f || is_d || is_u; + + if (i < n-1 && moveaxis(moves[i]) == 0 && + parallel(moves[i], moves[i+1])) + return true; + } + + return false; +} + +STATIC bool +htr_solution_prune(const solution_moves_t s[static 1]) +{ + bool f; + + f = false; + + return htr_checkmoves(&f, s->nmoves, s->moves) || + htr_checkmoves(&f, s->npremoves, s->premoves); +} + +STATIC bool +is_cp_htr(uint64_t i, const unsigned char *data) +{ + static uint8_t is_cp16_htr_table[DIV_ROUND_UP(CLASSES_CP_16, 8)] = { + [0] = 81, [7] = 144, [8] = 16, [25] = 130, [26] = 34, + [37] = 64, [38] = 48, [39] = 8, [212] = 20, [226] = 32, + [227] = 2, [298] = 160, [300] = 128, [301] = 1 + }; + + uint64_t e, c; + + e = i % COMB_8_4; + c = i / COMB_8_4; + + return e == 0 && is_cp16_htr_table[c / 8] & (UINT8_C(1) << (c % 8)); +} diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h index 7bc8041..9b59969 100644 --- a/src/solvers/coord/list.h +++ b/src/solvers/coord/list.h @@ -5,6 +5,7 @@ coord_t *all_coordinates[] = { &coordinate_drfinnoe, &coordinate_drslice, &coordinate_cpepe, + &coordinate_htr, NULL }; diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index 72bc064..54309b1 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -155,6 +155,10 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) int64_t n, ret; cube_t backup_cube, backup_inverse; + if (arg->coord->solution_prune != NULL && + arg->coord->solution_prune(arg->solution_moves)) + return 0; + coord = arg->coord->coord(arg->cube, arg->coord_data); if (coord_is_solved(arg->coord, coord, arg->coord_data)) { if (!coord_solution_admissible(arg)) diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h index 73484ba..98f9822 100644 --- a/src/solvers/coord/types_macros.h +++ b/src/solvers/coord/types_macros.h @@ -28,6 +28,7 @@ typedef struct { uint64_t moves_mask_solve; uint64_t trans_mask; bool (*is_admissible)(const solution_moves_t[static 1]); + bool (*solution_prune)(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]; -- cgit v1.3