From 18c9a8b8905304cf5f8fc15825769046a3144866 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 18 Aug 2024 14:26:45 +0200 Subject: Reorganized folder structure --- src/solvers/h48/solve.h | 242 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 242 insertions(+) create mode 100644 src/solvers/h48/solve.h (limited to 'src/solvers/h48/solve.h') diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h new file mode 100644 index 0000000..8531a40 --- /dev/null +++ b/src/solvers/h48/solve.h @@ -0,0 +1,242 @@ +typedef struct { + cube_t cube; + cube_t inverse; + int8_t nmoves; + int8_t depth; + uint8_t moves[MAXLEN]; + int64_t *nsols; + int64_t maxsolutions; + uint8_t h; + uint32_t *cocsepdata; + uint32_t *h48data; + char **nextsol; +} dfsarg_solveh48_t; + +typedef struct { + cube_t cube; + int8_t nmoves; + int8_t depth; + uint8_t moves[MAXLEN]; + uint32_t *cocsepdata; + uint32_t *h48data; + char *s; +} dfsarg_solveh48stats_t; + +_static void solve_h48_appendsolution(dfsarg_solveh48_t *); +_static_inline bool solve_h48_stop(dfsarg_solveh48_t *); +_static int64_t solve_h48_dfs(dfsarg_solveh48_t *); +_static int64_t solve_h48( + cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *); + +_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); +_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); + +_static void +solve_h48_appendsolution(dfsarg_solveh48_t *arg) +{ + int strl; + + strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); + LOG("Solution found: %s\n", *arg->nextsol); + *arg->nextsol += strl; + **arg->nextsol = '\n'; + (*arg->nextsol)++; + (*arg->nsols)++; +} + +_static_inline bool +solve_h48_stop(dfsarg_solveh48_t *arg) +{ + uint32_t data, data_inv; + int8_t bound; + + bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); + if (bound + arg->nmoves > arg->depth) + return true; + + bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv); + if (bound + arg->nmoves > arg->depth) + return true; + +/* + bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data); +LOG("Using pval %" PRId8 "\n", bound); + if (bound + arg->nmoves > arg->depth) + return true; + + bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data); + if (bound + arg->nmoves > arg->depth) + return true; +*/ + + return false; +} + +_static int64_t +solve_h48_dfs(dfsarg_solveh48_t *arg) +{ + dfsarg_solveh48_t nextarg; + int64_t ret; + uint8_t m; + + if (*arg->nsols == arg->maxsolutions) + return 0; + + if (solve_h48_stop(arg)) + return 0; + + if (issolved(arg->cube)) { + if (arg->nmoves != arg->depth) + return 0; + solve_h48_appendsolution(arg); + return 1; + } + + /* TODO: avoid copy, change arg and undo changes after recursion */ + nextarg = *arg; + nextarg.nmoves = arg->nmoves + 1; + ret = 0; + for (m = 0; m < 18; m++) { + nextarg.moves[arg->nmoves] = m; + if (!allowednextmove(nextarg.moves, nextarg.nmoves)) { + /* If a move is not allowed, neither are its 180 + * and 270 degree variations */ + m += 2; + continue; + } + nextarg.cube = move(arg->cube, m); + nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */ + ret += solve_h48_dfs(&nextarg); + } + + return ret; +} + +_static int64_t +solve_h48( + cube_t cube, + int8_t minmoves, + int8_t maxmoves, + int8_t maxsolutions, + uint8_t h, + const void *data, + char *solutions +) +{ + int64_t nsols; + dfsarg_solveh48_t arg; + + arg = (dfsarg_solveh48_t) { + .cube = cube, + .inverse = inverse(cube), + .nsols = &nsols, + .maxsolutions = maxsolutions, + .h = h, + .cocsepdata = (uint32_t *)data, + .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4, + .nextsol = &solutions + }; + + nsols = 0; + for (arg.depth = minmoves; + arg.depth <= maxmoves && nsols < maxsolutions; + arg.depth++) + { + LOG("Found %" PRId64 " solutions, searching at depth %" + PRId8 "\n", nsols, arg.depth); + arg.nmoves = 0; + solve_h48_dfs(&arg); + } + + return nsols; +} + +/* +The h48stats solver computes how many moves it takes to solve to +each of the 12 h48 coordinates, one for each value of h from 0 to 11. +The solutions array is filled with the length of the solutions. The +solution array is therefore not a printable string. +*/ +_static int64_t +solve_h48stats_dfs(dfsarg_solveh48stats_t *arg) +{ + const int64_t limit = 11; + + int8_t bound, u; + uint8_t m; + uint32_t d; + int64_t coord, h; + dfsarg_solveh48stats_t nextarg; + + /* Check cocsep lower bound (corners only) */ + bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d); + if (bound + arg->nmoves > arg->depth) + return 0; + + /* Check h48 lower bound for h=0 (esep, but no eo) */ + coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0); + bound = get_esep_pval(arg->h48data, coord); + if (bound + arg->nmoves > arg->depth) + return 0; + + /* Update all other values, if solved */ + coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11); + for (h = 0; h <= limit; h++) { + u = coord >> (11-h) == 0 && arg->s[h] == 99; + arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h]; + } + + if (arg->s[limit] != 99) + return 0; + + nextarg = *arg; + nextarg.nmoves = arg->nmoves + 1; + for (m = 0; m < 18; m++) { + nextarg.moves[arg->nmoves] = m; + if (!allowednextmove(nextarg.moves, nextarg.nmoves)) { + /* If a move is not allowed, neither are its 180 + * and 270 degree variations */ + m += 2; + continue; + } + nextarg.cube = move(arg->cube, m); + solve_h48stats_dfs(&nextarg); + } + + return 0; +} + +_static int64_t +solve_h48stats( + cube_t cube, + int8_t maxmoves, + const void *data, + char solutions[static 12] +) +{ + int i; + size_t cocsepsize; + dfsarg_solveh48stats_t arg; + + cocsepsize = gendata_cocsep(NULL, NULL, NULL); + + arg = (dfsarg_solveh48stats_t) { + .cube = cube, + .cocsepdata = (uint32_t *)data, + .h48data = ((uint32_t *)data) + (cocsepsize/4), + .s = solutions + }; + + for (i = 0; i < 12; i++) + solutions[i] = (char)99; + + for (arg.depth = 0; + arg.depth <= maxmoves && solutions[11] == 99; + arg.depth++) + { + arg.nmoves = 0; + solve_h48stats_dfs(&arg); + } + + return 0; +} -- cgit v1.3