commit 4d8465a3a791ebcf4bc74bdcc21eff7341ebc30f
parent 7defd8041e6050a9adf7927b43fd249d75d6389f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 7 Mar 2025 17:08:28 +0100
More progress on coordinate solver
Diffstat:
8 files changed, 274 insertions(+), 9 deletions(-)
diff --git a/TODO_COORDINATES b/TODO_COORDINATES
@@ -1,6 +1,6 @@
-- solver
- - include NISS
+- solver (from TODOs in appending solution)
- test solver for EO
+- add NISS (and add tests for NISS EO)
- make solve parallelized
- other coordinates
- gendata must handle symmetry
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
@@ -6,6 +6,8 @@ coord_t *all_coordinates[] = {
};
STATIC void append_coord_name(const coord_t *, char *);
+STATIC coord_t *parse_coord(const char *, int);
+STATIC uint8_t parse_axis(const char *, int);
STATIC void
append_coord_name(const coord_t *coord, char *str)
@@ -18,3 +20,29 @@ append_coord_name(const coord_t *coord, char *str)
str[j] = '\0';
}
+
+STATIC coord_t *
+parse_coord(const char *coord, int n)
+{
+ int i;
+
+ for (i = 0; all_coordinates[i] != NULL; i++)
+ if (!strncmp(all_coordinates[i]->name, coord, n))
+ return all_coordinates[i];
+
+ return NULL;
+}
+
+STATIC uint8_t
+parse_axis(const char *axis, int n)
+{
+ if (!strncmp(axis, "UD", n) || !strncmp(axis, "DU", n)) {
+ return AXIS_UD;
+ } else if (!strncmp(axis, "RL", n) || !strncmp(axis, "LR", n)) {
+ return AXIS_RL;
+ } else if (!strncmp(axis, "FB", n) || !strncmp(axis, "BF", n)) {
+ return AXIS_FB;
+ }
+
+ return UINT8_ERROR;
+}
diff --git a/src/solvers/coord/coord_solve.h b/src/solvers/coord/coord_solve.h
@@ -1,3 +1,228 @@
#include "coord_types_macros.h"
#include "common.h"
#include "gendata_coord.h"
+
+#define MAXLEN_COORDSOL 20
+
+typedef struct {
+ cube_t cube;
+ uint8_t depth;
+ uint8_t nmoves;
+ uint8_t moves[MAXLEN_COORDSOL];
+ coord_t *coord;
+ const void *coord_data;
+ const uint8_t *ptable;
+ uint8_t trans;
+ int64_t *nsols;
+ int64_t maxsolutions;
+ int optimal;
+ uint8_t *shortest_sol;
+ uint64_t solutions_size;
+ uint64_t *solutions_used;
+ char **solutions;
+} dfsarg_solve_coord_t;
+
+STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t,
+ uint8_t, uint64_t, int, int, uint64_t, const void, uint64_t, char);
+STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t,
+ uint8_t, uint64_t, int, int, uint64_t, const void, uint64_t, char);
+STATIC bool solve_coord_appendchar(char *, uint64_t, uint64_t *, char);
+STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *);
+STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *);
+
+STATIC int64_t
+solve_coord_appendsolution(dfsarg_solve_coord_t *arg)
+{
+ uint8_t i, t, tmoves[MAXLEN_COORDSOL];
+
+ if (*arg->nsols >= arg->maxsolutions ||
+ arg->nmoves > *arg->shortest_sol + arg->optimal)
+ return 0;
+
+ sortparallel(arg->moves, arg->nmoves);
+
+ t = inverse_trans(arg->trans);
+ for (i = 0; i < arg->nmoves; i++)
+ tmoves[i] = transform_move(arg->moves[i], t);
+
+ /* TODO append tmoves[] */
+
+ return 1;
+}
+
+STATIC bool
+solve_coord_appendchar(char *s, uint64_t s_size, uint64_t *s_used, char c)
+{
+ if (s_size == *s_used)
+ return false;
+
+ s[*s_used] = c;
+ (*s_used)++;
+
+ return true;
+}
+
+STATIC int64_t
+solve_coord_dfs(dfsarg_solve_coord_t *arg)
+{
+ uint64_t coord;
+ uint8_t pval;
+
+ coord = arg->coord->coord(arg->cube, arg->coord_data);
+
+ if (coord == 0) {
+ if (arg->nmoves != arg->depth)
+ return 0;
+ return solve_coord_appendsolution(arg);
+ }
+
+ pval = get_coord_pval(arg->coord, arg->ptable, coord);
+ if (arg->nmoves + pval > arg->depth)
+ return 0;
+
+ /* TODO recursive call */
+ /* Is allowednextmove available here? */
+
+ return 0;
+}
+
+STATIC int64_t
+solve_coord_dispatch(
+ cube_t cube,
+ const char *coord_axis,
+ uint8_t nissflag,
+ uint8_t minmoves,
+ uint8_t maxmoves,
+ uint64_t maxsolutions,
+ int optimal,
+ int threads,
+ uint64_t data_size,
+ const void *data,
+ uint64_t sols_size,
+ char *sols
+)
+{
+ int i, n;
+ coord_t *coord;
+ uint8_t axis;
+
+ n = strlen(coord_axis);
+ for (i = 0; coord_axis[i] != ' ' && coord_axis[i] != '\0'; i++) ;
+
+ coord = parse_coord(coord_axis, i);
+ axis = parse_axis(coord_axis + i + 1, n - i - 1);
+
+ if (coord == NULL) {
+ LOG("Could not parse coordinate '%s'\n", coord_axis);
+ return NISSY_ERROR_INVALID_SOLVER;
+ }
+
+ if (axis == UINT8_ERROR) {
+ LOG("Could not parse axis from '%s'\n", coord_axis);
+ return NISSY_ERROR_INVALID_SOLVER;
+ }
+
+ return solve_coord(cube, coord, axis, nissflag, minmoves, maxmoves,
+ maxsolutions, optimal, threads, data_size, data, sols_size, sols);
+}
+
+STATIC int64_t
+solve_coord(
+ cube_t cube,
+ coord_t *coord,
+ uint8_t axis,
+ uint8_t nissflag,
+ uint8_t minmoves,
+ uint8_t maxmoves,
+ uint64_t maxsolutions,
+ int optimal,
+ int threads,
+ uint64_t data_size,
+ const void data,
+ uint64_t sols_size,
+ char *sols
+)
+{
+ int8_t d;
+ uint8_t t, shortest_sol;
+ int64_t nsols;
+ uint64_t sols_used;
+ cube_t c;
+ const void *coord_data;
+ const uint8_t *ptable;
+ dfsarg_solve_coord_t arg;
+ tableinfo_t info;
+
+ if (readtableinfo(data_size, data, &info) != NISSY_OK)
+ goto solve_coord_error_data;
+
+ if (info.type == TABLETYPE_PRUNING) {
+ /* Only the pruning table */
+ coord_data = NULL;
+ ptable = (uint8_t *)data + INFOSIZE;
+ } else {
+ /* Coordinate has extra data */
+ coord_data = data + INFOSIZE;
+ ptable = (uint8_t *)data + info.next + INFOSIZE;
+ }
+
+ nsols = 0;
+ sols_used = 0;
+ shortest_sol = MAXLEN_COORDSOL + 1;
+ c = transform(cube, t);
+ t = coord->axistrans[axis];
+
+ arg = (dfsarg_solve_coord_t) {
+ .cube = c,
+ .coord = coord,
+ .coord_data = coord_data,
+ .ptable = ptable,
+ .trans = t,
+ .nsols = &nsols,
+ .maxsolutions = (int64_t)maxsolutions,
+ .optimal = optimal,
+ .shortest_sol = &shortest_sol,
+ .solutions_size = sols_size,
+ .solutions_used = &sols_used,
+ .solutions = &sols,
+ };
+
+ if (coord->coord(c, coord_data) == 0) {
+ if (minmoves == 0) {
+ nsols = 1;
+ if (!solve_coord_appendchar(
+ sols, sols_size, &sols_used, '\n'))
+ goto solve_coord_error_buffer;
+ }
+ goto solve_coord_done;
+ }
+
+ for (
+ d = MAX(minmoves, 1);
+ d <= maxmoves && nsols < (int64_t)maxsolutions
+ && !(nsols != 0 && d > shortest_sol + optimal);
+ d++
+ ) {
+ if (d >= 10)
+ LOG("Found %" PRId64 " solutions, searching at depth %"
+ PRId8 "\n", nsols, d);
+
+ arg.depth = d;
+ arg.nmoves = 0;
+ nsols += solve_coord_dfs(&arg);
+ }
+
+solve_coord_done:
+ if (!solve_coord_appendchar(sols, sols_size, &sols_used, '\0'))
+ goto solve_coord_error_buffer;
+
+ return nsols;
+
+solve_coord_error_data:
+ LOG("solve_coord: error reading table\n");
+ return NISSY_ERROR_DATA;
+
+solve_coord_error_buffer:
+ LOG("Could not append solution to buffer: size too small\n");
+ return NISSY_ERROR_BUFFER_SIZE;
+}
diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/coord_types_macros.h
@@ -10,4 +10,5 @@ typedef struct {
uint64_t max;
uint32_t moves_mask;
uint64_t trans_mask;
+ uint8_t axistrans[3];
} coord_t;
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
@@ -10,6 +10,11 @@ STATIC coord_t coordinate_eo = {
.max = POW_2_11,
.trans_mask = TM_ALLTRANS,
.moves_mask = MM_ALLMOVES,
+ .axistrans = {
+ [AXIS_UD] = TRANS_FDr,
+ [AXIS_RL] = TRANS_URr,
+ [AXIS_FB] = TRANS_UFr,
+ },
};
STATIC uint64_t
diff --git a/src/solvers/coord/gendata_coord.h b/src/solvers/coord/gendata_coord.h
@@ -7,14 +7,16 @@ STATIC void set_coord_pval(const coord_t *, uint8_t *, uint64_t, uint8_t);
STATIC size_t
gendata_coordinate_name(const char *name, void *buf)
{
- int i;
+ coord_t *coord;
- for (i = 0; all_coordinates[i] != NULL; i++)
- if (strcmp(all_coordinates[i]->name, name) == 0)
- return gendata_coordinate(all_coordinates[i], buf);
+ coord = parse_coord(name, strlen(name));
+ if (coord == NULL) {
+ LOG("Cannot generate data for coordinate '%s': not found\n",
+ name);
+ return 0;
+ }
- LOG("Cannot generate data for coordinate '%s': not found\n", name);
- return 0;
+ return gendata_coordinate(coord, buf);
}
STATIC size_t
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
@@ -457,7 +457,7 @@ solve_h48(
pthread_t thread[THREADS];
pthread_mutex_t solutions_mutex;
- if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
+ if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
goto solve_h48_error_data;
cocsepdata = (uint32_t *)((char *)data + INFOSIZE);
diff --git a/src/utils/constants.h b/src/utils/constants.h
@@ -93,6 +93,10 @@ STATIC int64_t binomial[12][12] = {
#define TRANS_BDm UINT8_C(46)
#define TRANS_BLm UINT8_C(47)
+#define AXIS_UD UINT8_C(0)
+#define AXIS_RL UINT8_C(1)
+#define AXIS_FB UINT8_C(2)
+
#define NMOVES (1+MOVE_B3)
#define NTRANS (1+TRANS_BLm)
