From 3e7bb9b87ef9b47d8f643dbcae19a64ddbc81dbb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 5 Aug 2025 09:04:00 +0200 Subject: Added DRFIN solver --- src/solvers/coord/multisolve.h | 298 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 298 insertions(+) create mode 100644 src/solvers/coord/multisolve.h (limited to 'src/solvers/coord/multisolve.h') diff --git a/src/solvers/coord/multisolve.h b/src/solvers/coord/multisolve.h new file mode 100644 index 0000000..f3589e8 --- /dev/null +++ b/src/solvers/coord/multisolve.h @@ -0,0 +1,298 @@ +/* +For now the only multicoordinate is DRFIN, and this solver reflects this. +For example, NISS is not available. +*/ + +typedef struct { + cube_t cube; + cube_t inverse; + uint8_t target_depth; + solution_moves_t *solution_moves; + solution_settings_t *solution_settings; + solution_list_t *solution_list; + multicoord_t *mcoord; + const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS]; + const unsigned char *ptable[MAX_MULTICOORD_NCOORDS]; +} dfsarg_solve_multicoord_t; + +STATIC int64_t solve_multicoord(oriented_cube_t, multicoord_t [static 1], + uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, + const unsigned char *, size_t, char *, int (*)(void *), void *); +STATIC long long solve_multicoord_dispatch(oriented_cube_t, const char *, + unsigned, unsigned, unsigned, unsigned, unsigned, unsigned, + unsigned long long, const unsigned char *, unsigned, char *, + long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); +STATIC bool multicoord_solution_admissible( + const dfsarg_solve_multicoord_t [static 1]); +STATIC bool multicoord_dfs_stop(const dfsarg_solve_multicoord_t [static 1]); +STATIC int64_t solve_multicoord_dfs(dfsarg_solve_multicoord_t [static 1]); + +STATIC bool +multicoord_solution_admissible(const dfsarg_solve_multicoord_t arg[static 1]) +{ + uint8_t n, i; + const coord_t *c; + + n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; + if (arg->target_depth != n) + return false; + + for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) { + c = arg->mcoord->coordinates[i]; + if (c->is_admissible != NULL && + !c->is_admissible(arg->solution_moves)) + return false; + } + + return true; +} + +STATIC bool +multicoord_dfs_stop(const dfsarg_solve_multicoord_t arg[static 1]) +{ + uint8_t pval, i; + uint64_t cval; + const coord_t *c; + + for (i = 0, pval = 0; arg->mcoord->coordinates[i] != NULL; i++) { + c = arg->mcoord->coordinates[i]; + + cval = c->coord(arg->cube, arg->coord_data[i]); + pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval)); + + cval = c->coord(arg->inverse, arg->coord_data[i]); + pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval)); + } + + return arg->solution_moves->nmoves + pval > arg->target_depth; +} + +STATIC int64_t +solve_multicoord_dfs(dfsarg_solve_multicoord_t arg[static 1]) +{ + uint8_t m, l, i; + uint32_t mm; + uint64_t coord; + int64_t n, ret; + const coord_t *c; + cube_t backup_cube, backup_inverse; + + for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) { + c = arg->mcoord->coordinates[i]; + coord = c->coord(arg->cube, arg->coord_data[i]); + if (!coord_is_solved(c, coord, arg->coord_data[i])) + goto solve_multicoord_dfs_notsolved; + } + + /* All coordinates are solved */ + if (!multicoord_solution_admissible(arg)) + return 0; + return appendsolution(arg->solution_moves, + arg->solution_settings, arg->solution_list); + +solve_multicoord_dfs_notsolved: + if (multicoord_dfs_stop(arg)) + return 0; + + backup_cube = arg->cube; + backup_inverse = arg->inverse; + ret = 0; + + l = arg->solution_moves->nmoves; + mm = arg->mcoord->moves_mask; + if (l != 0) { + m = arg->solution_moves->moves[l-1]; + mm &= allowedmask[movebase(m)]; + } + arg->solution_moves->nmoves++; + + for (m = 0; m < NMOVES; m++) { + if (!(mm & (UINT32_C(1) << (uint32_t)m))) + continue; + + arg->solution_moves->moves[l] = m; + arg->cube = move(backup_cube, m); + arg->inverse = premove(backup_inverse, m); + n = solve_multicoord_dfs(arg); + if (n < 0) + return n; + ret += n; + } + + arg->solution_moves->nmoves--; + arg->cube = backup_cube; + arg->inverse = backup_inverse; + + return ret; +} + +STATIC long long +solve_multicoord_dispatch( + oriented_cube_t oc, + const char *coord_and_trans, + unsigned nissflag, + unsigned minmoves, + unsigned maxmoves, + unsigned maxsolutions, + unsigned optimal, + unsigned threads, + unsigned long long data_size, + const unsigned char *data, + unsigned solutions_size, + char *sols, + long long stats[static NISSY_SIZE_SOLVE_STATS], + int (*poll_status)(void *), + void *poll_status_data +) +{ + multicoord_t *mcoord; + uint8_t trans; + + parse_coord_and_trans(coord_and_trans, NULL, &mcoord, &trans); + + if (mcoord == NULL) { + LOG("Error: could not parse coordinate from '%s'\n", + coord_and_trans); + return NISSY_ERROR_INVALID_SOLVER; + } + + if (trans == UINT8_ERROR) { + LOG("Error: could not parse transformation from '%s'\n", + coord_and_trans); + return NISSY_ERROR_INVALID_SOLVER; + } + + return solve_multicoord(oc, mcoord, trans, minmoves, + maxmoves, maxsolutions, optimal, threads, data_size, data, + solutions_size, sols, poll_status, poll_status_data); +} + +STATIC int64_t +solve_multicoord( + oriented_cube_t oc, + multicoord_t mcoord [static 1], + uint8_t trans, + uint8_t minmoves, + uint8_t maxmoves, + uint64_t maxsolutions, + uint8_t optimal, + uint8_t threads, + uint64_t data_size, + const unsigned char *data, + size_t solutions_size, + char *sols, + int (*poll_status)(void *), + void *poll_status_data +) +{ + int8_t d; + size_t j, of; + uint64_t i; + int64_t err; + cube_t c; + const coord_t *coord; + dfsarg_solve_multicoord_t arg; + tableinfo_t info; + solution_moves_t solution_moves; + solution_settings_t solution_settings; + solution_list_t solution_list; + + c = transform(oc.cube, trans); + + if (!mcoord->is_solvable(c)) + goto solve_multicoord_error_unsolvable; + + if (!solution_list_init(&solution_list, solutions_size, sols)) + goto solve_multicoord_error_buffer; + + solution_moves_reset(&solution_moves); + + solution_settings = (solution_settings_t) { + .tmask = TM_SINGLE(inverse_trans(trans)), + .unniss = false, + .maxmoves = maxmoves, + .maxsolutions = maxsolutions, + .optimal = optimal, + .orientation = oc.orientation, + }; + + arg = (dfsarg_solve_multicoord_t) { + .cube = c, + .inverse = inverse(c), + .mcoord = mcoord, + .solution_moves = &solution_moves, + .solution_settings = &solution_settings, + .solution_list = &solution_list, + }; + + for (j = 0, of = INFOSIZE; mcoord->coordinates[j] != NULL; j++) { + if (readtableinfo(data_size-of, data+of, &info) != NISSY_OK) + goto solve_multicoord_error_data; + + if (info.type == TABLETYPE_PRUNING) { + /* Only the pruning table */ + arg.coord_data[j] = NULL; + arg.ptable[j] = data + of + INFOSIZE; + of += info.fullsize; + } else { + /* Coordinate has extra data */ + arg.coord_data[j] = data + of + INFOSIZE; + arg.ptable[j] = data + of + info.next + INFOSIZE; + of += info.fullsize; + if (readtableinfo(data_size-of, data+of, &info) + != NISSY_OK) + goto solve_multicoord_error_data; + of += info.fullsize; + } + + /* Skip padding */ + while (of % 8 != 0) + of++; + } + + for (j = 0; mcoord->coordinates[j] != NULL; j++) { + coord = mcoord->coordinates[j]; + i = coord->coord(c, arg.coord_data[j]); + if (!coord_is_solved(coord, i, arg.coord_data[j])) + goto solve_multicoord_notsolved; + } + + /* All coordinates are solved */ + if (minmoves == 0 && !appendsolution(&solution_moves, + &solution_settings, &solution_list)) + goto solve_multicoord_error_buffer; + goto solve_multicoord_done; + +solve_multicoord_notsolved: + for ( + d = MAX(minmoves, 1); + !solutions_done(&solution_list, &solution_settings, d); + d++ + ) { + if (d >= 12) + LOG("[%s solve] Found %" PRIu64 " solutions, " + "searching at depth %" PRId8 "\n", + mcoord->name, solution_list.nsols, d); + + arg.target_depth = d; + solution_moves_reset(arg.solution_moves); + if ((err = solve_multicoord_dfs(&arg)) < 0) + return err; + } + +solve_multicoord_done: + return (int64_t)solution_list.nsols; + +solve_multicoord_error_data: + LOG("[%s solve] Error reading table\n", mcoord->name); + return NISSY_ERROR_DATA; + +solve_multicoord_error_buffer: + LOG("[%s solve] Error appending solution to buffer: size too small\n", + mcoord->name); + return NISSY_ERROR_BUFFER_SIZE; + +solve_multicoord_error_unsolvable: + LOG("[%s solve] Error: cube not ready\n", mcoord->name); + return NISSY_ERROR_UNSOLVABLE_CUBE; +} -- cgit v1.3