From c5a6ff0443fc9e5e890fe72cb13ea78d4fe2bbcb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Wed, 2 Apr 2025 14:33:21 +0200 Subject: Added dreo coordinate solver --- src/solvers/coord/common.h | 2 +- src/solvers/coord/coord.h | 1 + src/solvers/coord/dr.h | 22 ++++++++- src/solvers/coord/dreo.h | 102 +++++++++++++++++++++++++++++++++++++++ src/solvers/coord/eo.h | 15 ++++++ src/solvers/coord/gendata.h | 11 +++++ src/solvers/coord/list.h | 1 + src/solvers/coord/solve.h | 27 ++++++----- src/solvers/coord/types_macros.h | 1 + 9 files changed, 168 insertions(+), 14 deletions(-) create mode 100644 src/solvers/coord/dreo.h (limited to 'src/solvers/coord') diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h index 95c0e6c..2eb5ad0 100644 --- a/src/solvers/coord/common.h +++ b/src/solvers/coord/common.h @@ -125,7 +125,7 @@ coord_gendata_generic( writetableinfo(&info, coord_datasize, data); - DBG_ASSERT(n == coord->sym.classes, 0, + DBG_ASSERT(n == coord->sym.classes, SIZE_MAX, "%s coordinate data: computed %" PRIu64 " classes, " "expected %" PRIu64 "\n", coord->name, n, coord->sym.classes); diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h index 11d41bc..2f24035 100644 --- a/src/solvers/coord/coord.h +++ b/src/solvers/coord/coord.h @@ -2,6 +2,7 @@ #include "common.h" #include "eo.h" #include "dr.h" +#include "dreo.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 314d4f1..3bc4c6d 100644 --- a/src/solvers/coord/dr.h +++ b/src/solvers/coord/dr.h @@ -1,5 +1,5 @@ -#define DREOESEP_CLASSES UINT64_C(64430) -#define DREOESEP_MAX (POW_2_11 * COMB_12_4) +#define DREOESEP_CLASSES UINT64_C(64430) +#define DREOESEP_MAX (POW_2_11 * COMB_12_4) STATIC uint64_t coord_dreoesep_nosym(cube_t); STATIC cube_t invcoord_dreoesep_nosym(uint64_t); @@ -10,6 +10,8 @@ STATIC cube_t coordinate_dr_cube(uint64_t, const void *); STATIC bool coordinate_dr_isnasty(uint64_t, const void *); STATIC size_t coordinate_dr_gendata(void *); +STATIC bool is_eoco_solvable(cube_t); + /* TODO: remove the following two when all coordinates are converted to unsigned */ STATIC uint64_t coord_co_u(cube_t c) { return (uint64_t)coord_co(c); } STATIC cube_t invcoord_co_u(uint64_t i) { return invcoord_co((int64_t)i); } @@ -29,6 +31,7 @@ STATIC coord_t coordinate_dr = { [AXIS_FB] = TRANS_FDr, }, .is_admissible = &solution_lastqt_cw, + .is_solvable = &is_eoco_solvable, .sym = { .classes = DREOESEP_CLASSES, .max = DREOESEP_MAX, @@ -100,3 +103,18 @@ coordinate_dr_gendata(void *data) { return coord_gendata_generic(&coordinate_dr, data); } + +STATIC bool +is_eoco_solvable(cube_t cube) { + uint8_t c[8], e[12], i, cocount, eocount; + + pieces(&cube, c, e); + + for (i = 0, cocount = 0; i < 8; i++) + cocount += (c[i] & COBITS_2) >> COSHIFT; + + for (i = 0, eocount = 0; i < 12; i++) + eocount += (e[i] & EOBIT) >> EOSHIFT; + + return cocount % 3 == 0 && eocount % 2 == 0; +} diff --git a/src/solvers/coord/dreo.h b/src/solvers/coord/dreo.h new file mode 100644 index 0000000..37de0d3 --- /dev/null +++ b/src/solvers/coord/dreo.h @@ -0,0 +1,102 @@ +#define DRESEP_CLASSES 81 + +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 void *); +STATIC cube_t coordinate_dreo_cube(uint64_t, const void *); +STATIC bool coordinate_dreo_isnasty(uint64_t, const void *); +STATIC size_t coordinate_dreo_gendata(void *); + +STATIC bool is_dreo_solvable(cube_t); + +STATIC coord_t coordinate_dreo = { + .name = "DREO", + .coord = &coordinate_dreo_coord, + .cube = &coordinate_dreo_cube, + .isnasty = &coordinate_dreo_isnasty, + .gendata = coordinate_dreo_gendata, + .max = DRESEP_CLASSES * POW_3_7, + .trans_mask = TM_UDRLFIX, + .moves_mask = MM_EO, + .axistrans = { + [AXIS_UD] = TRANS_UFr, + [AXIS_RL] = TRANS_RFr, + [AXIS_FB] = TRANS_FDr, + }, + .is_admissible = &solution_lastqt_cw, + .is_solvable = &is_dreo_solvable, + .sym = { + .classes = DRESEP_CLASSES, + .max = COMB_12_4, + .coord = &coord_dresep_nosym, + .cube = &invcoord_dresep_nosym, + .max2 = POW_3_7, + .coord2 = &coord_co_u, + .cube2 = &invcoord_co_u, + .merge = &coordinate_dreo_merge, + }, +}; + +STATIC uint64_t +coord_dresep_nosym(cube_t cube) +{ + return (uint64_t)coord_esep(cube) / COMB_8_4; +} + +STATIC cube_t +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 void *data) +{ + return coord_coord_generic(&coordinate_dreo, cube, data); +} + +STATIC cube_t +coordinate_dreo_cube(uint64_t i, const void *data) +{ + return coord_cube_generic(&coordinate_dreo, i, data); +} + +STATIC bool +coordinate_dreo_isnasty(uint64_t i, const void *data) +{ + return coord_isnasty_generic(&coordinate_dreo, i, data); +} + +STATIC size_t +coordinate_dreo_gendata(void *data) +{ + return coord_gendata_generic(&coordinate_dreo, data); +} + +STATIC bool +is_dreo_solvable(cube_t cube) { + uint8_t c[8], e[12], i, cocount; + + if (coord_eo(cube) != 0) + return false; + + pieces(&cube, c, e); + + for (i = 0, cocount = 0; i < 8; i++) + cocount += (c[i] & COBITS_2) >> COSHIFT; + + return cocount % 3 == 0; +} diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h index b83be01..a0685c4 100644 --- a/src/solvers/coord/eo.h +++ b/src/solvers/coord/eo.h @@ -2,6 +2,7 @@ STATIC uint64_t coordinate_eo_coord(cube_t, const void *); STATIC cube_t coordinate_eo_cube(uint64_t, const void *); STATIC bool coordinate_eo_isnasty(uint64_t, const void *); STATIC size_t coordinate_eo_gendata(void *); +STATIC bool is_eo_even(cube_t); STATIC coord_t coordinate_eo = { .name = "EO", @@ -18,6 +19,7 @@ STATIC coord_t coordinate_eo = { [AXIS_FB] = TRANS_UFr, }, .is_admissible = &solution_lastqt_cw, + .is_solvable = &is_eo_even, .sym = {0}, }; @@ -46,3 +48,16 @@ coordinate_eo_gendata(void *data) { return 0; } + +STATIC bool +is_eo_even(cube_t cube) +{ + uint8_t c[8], e[12], i, count; + + pieces(&cube, c, e); + + for (i = 0, count = 0; i < 12; i++) + count += (e[i] & EOBIT) >> EOSHIFT; + + return count % 2 == 0; +} diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h index 423dad1..63e1631 100644 --- a/src/solvers/coord/gendata.h +++ b/src/solvers/coord/gendata.h @@ -39,6 +39,9 @@ gendata_coord(const coord_t coord[static 1], void *buf) coord_data = buf == NULL ? NULL : ((uint8_t *)buf) + INFOSIZE; coord_dsize = coord->gendata(coord_data); + if (coord_dsize == SIZE_MAX) + goto gendata_coord_error; + ninfo = coord_dsize == 0 ? 1 : 2; tablesize = DIV_ROUND_UP(coord->max, 2); @@ -77,6 +80,10 @@ gendata_coord(const coord_t coord[static 1], void *buf) gendata_coord_return_size: return ninfo * INFOSIZE + coord_dsize + tablesize; + +gendata_coord_error: + LOG("An unexpected error occurred when generating the data.\n"); + return 0; } STATIC tableinfo_t @@ -167,6 +174,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)) + continue; moved = move(c, m); ii = coord->coord(moved, data); isnasty = coord->isnasty(ii, data); @@ -216,6 +225,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)) + continue; ii = coord->coord(move(c, m), data); if (get_coord_pval(coord, table, ii) < d) { found = true; diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h index 7d43d45..9409bb6 100644 --- a/src/solvers/coord/list.h +++ b/src/solvers/coord/list.h @@ -1,5 +1,6 @@ coord_t *all_coordinates[] = { &coordinate_eo, &coordinate_dr, + &coordinate_dreo, NULL }; diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index fa4134a..8806d17 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -135,11 +135,10 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) ret = 0; if (coord_continue_onnormal(arg)) { l = arg->solution_moves->nmoves; - if (l == 0) { - mm = MM_ALLMOVES; - } else { + mm = arg->coord->moves_mask; + if (l != 0) { m = arg->solution_moves->moves[l-1]; - mm = allowedmask[movebase(m)]; + mm &= allowedmask[movebase(m)]; } arg->solution_moves->nmoves++; arg->lastisnormal = true; @@ -165,11 +164,10 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) if (coord_continue_oninverse(arg)) { l = arg->solution_moves->npremoves; - if (l == 0) { - mm = MM_ALLMOVES; - } else { + mm = arg->coord->moves_mask; + if (l != 0) { m = arg->solution_moves->premoves[l-1]; - mm = allowedmask[movebase(m)]; + mm &= allowedmask[movebase(m)]; } arg->solution_moves->npremoves++; arg->lastisnormal = false; @@ -264,6 +262,12 @@ solve_coord( solution_settings_t solution_settings; solution_list_t solution_list; + t = coord->axistrans[axis]; + c = transform(cube, t); + + if (!coord->is_solvable(c)) + goto solve_coord_error_unsolvable; + if (!solution_list_init(&solution_list, solutions_size, sols)) goto solve_coord_error_buffer; @@ -280,9 +284,6 @@ solve_coord( ptable = (uint8_t *)data + info.next + INFOSIZE; } - t = coord->axistrans[axis]; - c = transform(cube, t); - solution_moves_reset(&solution_moves); solution_settings = (solution_settings_t) { @@ -351,4 +352,8 @@ solve_coord_error_data: solve_coord_error_buffer: LOG("Could not append solution to buffer: size too small\n"); return NISSY_ERROR_BUFFER_SIZE; + +solve_coord_error_unsolvable: + LOG("Cube not ready for solving %s\n", coord->name); + return NISSY_ERROR_UNSOLVABLE_CUBE; } diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h index a2eaefe..84ed8eb 100644 --- a/src/solvers/coord/types_macros.h +++ b/src/solvers/coord/types_macros.h @@ -25,6 +25,7 @@ typedef struct { uint64_t trans_mask; uint8_t axistrans[3]; bool (*is_admissible)(const solution_moves_t[static 1]); + bool (*is_solvable)(cube_t); struct { size_t classes; uint64_t max; -- cgit v1.3