commit c5a6ff0443fc9e5e890fe72cb13ea78d4fe2bbcb
parent 82e0a6bf454f5684b44bb0a24db619e9ba0567a0
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 2 Apr 2025 14:33:21 +0200
Added dreo coordinate solver
Diffstat:
17 files changed, 253 insertions(+), 17 deletions(-)
diff --git a/src/nissy.c b/src/nissy.c
@@ -566,6 +566,7 @@ nissy_solve(
}
if (!issolvable(c)) {
+/* TODO: this is step-dependent */
LOG("solve: cube is not solvable\n");
return NISSY_ERROR_UNSOLVABLE_CUBE;
}
diff --git a/src/nissy.h b/src/nissy.h
@@ -363,8 +363,11 @@ different from what specified, or simply ill-formed.
#define NISSY_ERROR_INVALID_CUBE -10LL
/*
-The value NISSY_ERROR_UNSOLVABLE_CUBE means that the provided cube is
-in an unsolvable state.
+The value NISSY_ERROR_UNSOLVABLE_CUBE means that the provided cube is in
+an unsolvable state for the given solver. This could mean either that the
+cube is not solvable at all (for example in case it has a single twisted
+corner), or that it is not ready for the given step (for example if the
+caller wants to solve a DR finish without the cube being in DR state).
*/
#define NISSY_ERROR_UNSOLVABLE_CUBE -11LL
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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;
diff --git a/src/utils/constants.h b/src/utils/constants.h
@@ -116,6 +116,10 @@ STATIC int64_t binomial[12][12] = {
#define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF)
#define TM_SINGLE(t) (UINT64_C(1) << (uint64_t)(t))
+#define TM_UDRLFIX (\
+ TM_SINGLE(TRANS_UFr) | TM_SINGLE(TRANS_UBr) | TM_SINGLE(TRANS_UFm) | \
+ TM_SINGLE(TRANS_UBm) | TM_SINGLE(TRANS_DFr) | TM_SINGLE(TRANS_DBr) | \
+ TM_SINGLE(TRANS_DFm) | TM_SINGLE(TRANS_DBm))
#define TM_UDFIX (\
TM_SINGLE(TRANS_UFr) | TM_SINGLE(TRANS_UBr) | TM_SINGLE(TRANS_URr) | \
TM_SINGLE(TRANS_ULr) | TM_SINGLE(TRANS_UFm) | TM_SINGLE(TRANS_UBm) | \
diff --git a/test/121_coorddata_dr/coorddata_dr.c b/test/121_coorddata_dr/coorddata_dr.c
@@ -22,7 +22,6 @@ void run(void) {
data = malloc(size);
coordinate_dr_gendata(data);
- /* Test all possible values for CO coordinate */
for (coord = 0; coord < BOUND; coord++) {
cube = coordinate_dr_cube(coord, data);
diff --git a/test/122_coorddata_dreo/00_all.in b/test/122_coorddata_dreo/00_all.in
diff --git a/test/122_coorddata_dreo/00_all.out b/test/122_coorddata_dreo/00_all.out
@@ -0,0 +1 @@
+All good
diff --git a/test/122_coorddata_dreo/coorddata_dreo.c b/test/122_coorddata_dreo/coorddata_dreo.c
@@ -0,0 +1,58 @@
+#include "../test.h"
+
+#define POW_3_7 2187
+#define BOUND 45 * POW_3_7
+#define TGROUP UINT64_C(4278190335)
+
+cube_t transform(cube_t, uint8_t);
+uint64_t coordinate_dreo_coord(cube_t, const void *);
+cube_t coordinate_dreo_cube(uint64_t, const void *);
+uint64_t coordinate_dreo_gendata(void *);
+
+void run(void) {
+ bool found;
+ uint64_t t;
+ char str[STRLENMAX];
+ void *data;
+ size_t size;
+ cube_t cube;
+ uint64_t coord, coord2;
+
+ size = coordinate_dreo_gendata(NULL);
+ data = malloc(size);
+ coordinate_dreo_gendata(data);
+
+ for (coord = 0; coord < BOUND; coord++) {
+ cube = coordinate_dreo_cube(coord, data);
+
+ if (!isconsistent(cube)) {
+ printf("Error: invcoord of %" PRId64
+ " is not consistent\n", coord);
+ goto cleanup;
+ }
+
+ for (t = 0, found = false; t < 48; t++) {
+ if (!((UINT64_C(1) << t) & TGROUP))
+ continue;
+
+ coord2 = coordinate_dreo_coord(transform(cube, t), data);
+ if (coord == coord2) {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found) {
+ printf("Error: invcoord of %" PRId64 " returns %"
+ PRId64 " with cube:\n", coord, coord2);
+ writecube("H48", cube, STRLENMAX, str);
+ printf("%s\n", str);
+ goto cleanup;
+ }
+ }
+
+ printf("All good\n");
+
+cleanup:
+ free(data);
+}
diff --git a/tools/expected_distributions.h b/tools/expected_distributions.h
@@ -152,6 +152,20 @@ uint64_t expected_dr[21] = {
[12] = 129,
};
+uint64_t expected_dreo[21] = {
+ [0] = 1,
+ [1] = 1,
+ [2] = 4,
+ [3] = 22,
+ [4] = 160,
+ [5] = 1286,
+ [6] = 8550,
+ [7] = 42512,
+ [8] = 90748,
+ [9] = 33466,
+ [10] = 757,
+};
+
static bool
distribution_equal(const uint64_t *expected, const uint64_t *actual, int n)
{
@@ -236,6 +250,8 @@ check_distribution(const char *solver, size_t data_size, const void *data)
return check_table(expected_eo, &info);
} else if (!strcmp(str, "DR")) {
return check_table(expected_dr, &info);
+ } else if (!strcmp(str, "DREO")) {
+ return check_table(expected_dreo, &info);
} else {
goto check_distribution_unknown;
}
