nissy-nx

A Rubik's cube optimal solver
git clone https://git.tronto.net/nissy-nx
Download | Log | Files | Refs | README | LICENSE

commit 1a5bfe9b08707b0aef748d7921a419ba4a046fba
parent 87a15e960e31365698df7e06cd3e6b851e17c1a5
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sun,  5 Mar 2023 15:17:07 +0100

Some fixes

Diffstat:
Msrc/solve.c | 3+++
Msrc/solve.h | 3++-
Msrc/solver_step.c | 26++++++++++++++++++--------
Msrc/threader_eager.c | 7++++---
4 files changed, 27 insertions(+), 12 deletions(-)

diff --git a/src/solve.c b/src/solve.c @@ -115,5 +115,8 @@ solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader) (opts->optimal != -1 && d >= opts->optimal + optimal); } +/* TODO: some cleanup (free cubedata) */ +/* TODO: actually, preparation should be done somewhere else */ + return sols; } diff --git a/src/solve.h b/src/solve.h @@ -36,12 +36,13 @@ struct solver { void * param; /* TODO: the following should be part of a generic cube description */ /* TODO: remove alloc? */ +/* TODO: revisit apply_move, maybe apply_alg? or both? */ void * (*alloc_cubedata)(void *); void (*copy_cubedata)(void *, void *, void *); void (*free_cubedata)(void *, void *); void (*invert_cube)(void *, void *); bool (*is_solved)(void *, void *); - void (*apply_alg)(void *, void *, Alg *); + void (*apply_move)(void *, void *, Move); /* TODO: remove dependence on Cube, preparation should be done before */ void * (*prepare_cube)(void *, Cube *); }; diff --git a/src/solver_step.c b/src/solver_step.c @@ -6,7 +6,7 @@ typedef struct { Trans * t; } CubeData; -static void apply_alg_cubedata(void *, void *, Alg *); +static void apply_move_cubedata(void *, void *, Move); static void init_indexes(Step *, CubeData *); static void * prepare_cube(void *, Cube *); static bool move_check_stop_eager(void *, DfsArg *, Threader *); @@ -22,13 +22,17 @@ static bool niss_makes_sense(void *, void *, Alg *); static Solver * new_stepsolver_nocheckstop(Step *step); static void -apply_alg_cubedata(void *param, void *cubedata, Alg *alg) +apply_move_cubedata(void *param, void *cubedata, Move m) { Step *s = (Step *)param; CubeData *data = (CubeData *)cubedata; - apply_alg(alg, data->cube); - init_indexes(s, data); + Trans tt; + for (int i = 0; i < s->n_coord; i++) { + Move mm = transform_move(data->t[i], m); + data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); + data->t[i] = transform_trans(tt, data->t[i]); + } } static void @@ -101,6 +105,8 @@ move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader) return move_check_stop_nonsol(param, arg, threader); } +/* TODO: split in 2 (nissable / non-nissable) and only move cube + when nissable */ static bool move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) { @@ -113,6 +119,7 @@ move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) s = (Step *)param; data = (CubeData *)arg->cubedata; + bound = 0; goal = arg->d - arg->current_alg->len; /* TODO: check if len is 0 */ @@ -130,6 +137,8 @@ move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) return true; } } + if (arg->opts->can_niss && !arg->niss) + apply_move(lastmove, data->cube); return false; } @@ -184,8 +193,9 @@ copy_cubedata(void *param, void *src, void *dst) olddata = (CubeData *)src; newdata = (CubeData *)dst; - /* Copy reference: we never move the cube */ - newdata->cube = olddata->cube; +/* TODO: do not copy if not nissable */ + newdata->cube = malloc(sizeof(Cube)); + copy_cube(olddata->cube, newdata->cube); for (i = 0; i < s->n_coord; i++) { newdata->val[i] = olddata->val[i]; newdata->t[i] = olddata->t[i]; @@ -201,7 +211,7 @@ free_cubedata(void *param, void *cubedata) free(data->t); free(data->val); - /* We do not free the cube */ + free(data->cube); free(data); } @@ -254,7 +264,7 @@ new_stepsolver_nocheckstop(Step *step) solver->moveset = step->moveset; solver->param = step; - solver->apply_alg = apply_alg_cubedata; + solver->apply_move = apply_move_cubedata; solver->prepare_cube = prepare_cube; solver->is_solved = is_solved_step; solver->validate_solution = validate_solution; diff --git a/src/threader_eager.c b/src/threader_eager.c @@ -43,7 +43,7 @@ possible_starts(DfsArg *arg, Solver *solver) AlgList *ret = new_alglist(); if (solver->is_solved(solver->param, arg->cubedata)) { - if (arg->opts->min_moves == 0) + if (arg->opts->min_moves == 0 && arg->d == 0) append_sol(new_alg(""), arg->threaddata); return ret; } @@ -82,15 +82,16 @@ instance_thread(void *arg) *(tid->node) = (*(tid->node))->next; pthread_mutex_unlock(tid->start_mutex); +/* TODO: adjust for longer (arbitrarily long?) starting sequences */ void *data = tid->solver->alloc_cubedata(tid->solver->param); tid->solver->copy_cubedata( tid->solver->param, tid->arg->cubedata, data); - tid->solver->apply_alg( - tid->solver->param, data, node->alg); bool inv = node->alg->inv[node->alg->len-1]; if (inv) tid->solver->invert_cube( tid->solver->param, data); + tid->solver->apply_move( + tid->solver->param, data, node->alg->move[0]); DfsArg newarg; newarg.cubedata = data;