nissy-nx

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

commit 87a15e960e31365698df7e06cd3e6b851e17c1a5
parent 3bfd0bb403d62bd942d1912d085ea59b156062fd
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sun,  5 Mar 2023 10:13:01 +0100

I made a mess, but it works. Still need to implement new optimal solver.
After that, a big redesign is due.

Diffstat:
MTODO/2.1.md | 96+++++++++++++++++--------------------------------------------------------------
MTODO/new-feature-ideas.md | 2++
MTODO/refactoring.md | 2--
Aold/solve_old.c | 447+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aold/solve_old.h | 9+++++++++
Msrc/alg.c | 127+++++++++++++++++++++++--------------------------------------------------------
Msrc/alg.h | 76+++-------------------------------------------------------------------------
Msrc/commands.c | 18+++++++++++++++++-
Msrc/commands.h | 9+++++++--
Msrc/cubetypes.h | 36++++++++++++++++++++++++++++--------
Asrc/movesets.c | 194+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/movesets.h | 15+++++++++++++++
Msrc/pruning.h | 1+
Msrc/solve.c | 519++++++++++++-------------------------------------------------------------------
Msrc/solve.h | 50++++++++++++++++++++++++++++++++++++++++++++++----
Asrc/solver_step.c | 296+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/solver_step.h | 12++++++++++++
Msrc/steps.c | 14++++++++++++--
Msrc/steps.h | 5+++--
Asrc/threader_eager.c | 162+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Asrc/threader_eager.h | 8++++++++
Asrc/threader_single.c | 35+++++++++++++++++++++++++++++++++++
Asrc/threader_single.h | 8++++++++
Mtests/alg_tests.h | 1+
24 files changed, 1439 insertions(+), 703 deletions(-)

diff --git a/TODO/2.1.md b/TODO/2.1.md @@ -1,89 +1,33 @@ # TODO-list for version 2.1 (or is it 3.0 at this point?) -## Alg and moveset changes (prerequisite for solve.h) - -### moveset.h -* split off from alg.h - -### alg.h -* There is a (future) bug in the way the solver checks if a move can -be appended (allowed_next and similar): the last two moves are not enough. -* Example: using QTM we have last 3 moves U U D. Considering only last 2, -U could be appended, but it cannot (cancel to U'). -* Solution: the per-moveset bool allowed_next() should take an alg as -parameter. There are going to be basically two versions, one for QTM and -one for HTM (but more may be added). -* Alg should be extended to remember the list of moves on inverse / normal -separately (without looping over moves). -* Maybe another parameter to know if it can assume there has not been -any double switching, i.e. if the last moves are the only ones to -be checked and there is no need to go back further (e.g. if alg is -U (... stuff on inverse ...) D I don't want to have to check back -to the U, but in practice we can often assume this does not happen). -* Then we can remove last and lastinv from dfsdata. -* move also can_niss to alg.h -* the check for the order of the moves (to avoid counting L R and R L as -different) can be made separately. Maybe add a "compare" function for moves, -such that non-commuting moves are not comparable (return -1 0 1). - ## Rework solver -* The architecture is the following: solve.h contains a solve() public -function that takes as parameters a set of solver methods (see below) -and a thread manager (basically, multithreaded or single threaded). -It also has a dfs() public function with the same parameters. -* The solve() function, looping over the allowed depths, calls -the dispatcher provided by the thread manager, which takes care of -instantiating the threads. Each thread calls back to dfs(). The -thread manager then takes case of re-assembling the solutions, and -finally returns a list of solutions for the given depth. -* The specifics of how dfs() works are implemented in a specific solver -module. +### 1. Implement minimum viable + +* Implement nxopt31 with fst_cube. Remember that the function + move_check_solved() should do one axis at the time, so that we don't move + everything before checking. +* test? -### solve.h +### 2. Rework achitecture and file dependencies -* Interface: define solve(), dfs() and the types dfsdata, solvermethods and -threadmanager. solve.h is included by specific thread managers and solvers. -* DfsData: remove Cube *, Movable, Step and extra. Add Void * (containing -either cube, indexes or whatnot) and a moveset (extracted from step, -necessary). Maybe cleanup solveoptions too (e.g. threads not necessary). -* solve.h depends only on moves (dependency on step and trans is removed). -* preparation step should be reworked, maybe removed or delegated to the -specific implementations. -* All dfs stuff in the same function. Maybe remove also solvestop. -* Move two-step solve to a different module +* solve.h depends only on moves(alg?) (dependency on step and trans is removed). +* Other modules have changed dependencies, might as well rework all. +* Make files smaller, do not include definition in .h, separate +data from abstract operations. +* remove cubetypes.h +* Create a module for multi-step (maybe wait?) +* Possible changes: in step solver, copy cube only if niss; add cleanup function +in solver (called by solve()) to free cube and perhaps pruning tables. +* see various TODO's in files -### Specific thread managers +### 4. More threading options -* Single thread. Useful in low-resources environments or when solving multiple -scrambles at the same time, or simply when asked to solve with one thread. * Lazy multithread: threads are as independent as possible and only merged at the end. Ideal when all solutions of a certain length are requested. -* Eager multithread: current implementation, branches communicate the number -and list of solutions to stop as soon as possible. Good when only one solution -of a certain depth is required. - -### Solver methods - -* bool move_check_stop(DfsArg *, Move): applies the given move (possibly -recovered from DfsData, but we avoid checking for niss by passing it -directly) and at the same time checks if the branch should be pruned. Not -elegant, but it is much more efficient to do the two things at the same time -(e.g. when moving a fst_cube we can move one "orientation" at the time, check -the pruning table and stop if possible). -* void add_solution(DfsArg *, ThreadManager): add the solution to the list. -Also checks if the solution is valid / acceptable (e.g. EO does not finish -with F' instead of F and such) and cleans it up (rotation, cleanup, unniss). -* void copy(void * src, void * dst): copy the cube-part of dfs_data. To be -called by copy_dfsdata, which remains in solve.h (but merged into dfs). -* void * invert_cube(void *): in preparation for niss. -* bool niss_makes_sense(DfsArg *): maybe can be done generically in solve.h? - -## New optimal solver (use fst) - -* Implement nxopt31 with fst_cube. Remember that the function - move_check_solved() should do one axis at the time, so that we don't move - everything before checking. +* (Done) Eager multithread: current implementation, branches communicate the +number and list of solutions to stop as soon as possible. Good when only one +solution of a certain depth is required. ## Simplify steps diff --git a/TODO/new-feature-ideas.md b/TODO/new-feature-ideas.md @@ -22,9 +22,11 @@ get its own file and more details. * Optimal solver: when asking only for one solution, scan for upper bound in parallel using a non-optimal (but fast) solver (e.g. twophase). * Optimal solver: up to a small bound, try with a small pruning table. +* Optimal solver: start at different depths in parallel * Multi-step solver: make more general ## New features +* Allow user to specify moveset manually (see issue \#5 on github) * EO analysis (and also DR and HTR analysis): group similar EOs (Jay) * HTR "maze" analysis? diff --git a/TODO/refactoring.md b/TODO/refactoring.md @@ -25,6 +25,4 @@ * Sort function implementations alphabetically, ignore static vs non static. * Rename functions and variable to have a consistent naming scheme. * Functions that copy data: swap src and dest, follow memcpy standard. -* The way coord uses define guards to organize the .h file is good, apply it - to other modules too - including tests. * Read style(9) and decide what to implement. diff --git a/old/solve_old.c b/old/solve_old.c @@ -0,0 +1,447 @@ +#define SOLVE_C + +#include "solve.h" + +/* Local functions ***********************************************************/ + +static void copy_dfsarg(DfsArg *src, DfsArg *dst); +static void dfs(DfsArg *arg); +static void dfs_add_sol(DfsArg *arg); +static void dfs_niss(DfsArg *arg); +static bool dfs_move_checkstop(DfsArg *arg); +static void * instance_thread(void *arg); +static void multidfs(DfsArg *arg); +static bool niss_makes_sense(DfsArg *arg); +static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); + +/* Local functions ***********************************************************/ + +static void +copy_dfsarg(DfsArg *src, DfsArg *dst) +{ + int i; + + dst->cube = src->cube; + dst->t = src->t; + dst->s = src->s; + dst->opts = src->opts; + dst->d = src->d; + dst->bound = src->bound; /* In theory not needed */ + dst->niss = src->niss; + dst->sols = src->sols; + dst->sols_mutex = src->sols_mutex; + dst->current_alg = src->current_alg; + + for (i = 0; i < src->s->n_coord; i++) { + dst->ind[i].val = src->ind[i].val; + dst->ind[i].t = src->ind[i].t; + } + + src->s->copy_extra(src, dst); +} + +static void +dfs(DfsArg *arg) +{ + int i; + Move m, l0, l1; + DfsArg newarg; + + if (dfs_move_checkstop(arg)) + return; + + if (arg->bound == 0) { + if (arg->current_alg->len == arg->d) + dfs_add_sol(arg); + return; + } + + for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { + m = arg->s->moveset->sorted_moves[i]; + if (arg->s->moveset->can_append(arg->current_alg, m, arg->niss) + && compare_last(arg->current_alg, m, arg->niss) >= 0) { + copy_dfsarg(arg, &newarg); + append_move(arg->current_alg, m, newarg.niss); + dfs(&newarg); + remove_last_move(arg->current_alg); + } + } + + if (niss_makes_sense(arg)) + dfs_niss(arg); +} + +static void +dfs_add_sol(DfsArg *arg) +{ + bool valid, accepted, nisscanc; + + valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); + accepted = valid || arg->opts->all; + nisscanc = arg->s->final && + arg->s->moveset->cancel_niss(arg->current_alg); + + if (accepted && !nisscanc) { + pthread_mutex_lock(arg->sols_mutex); + + if (arg->sols->len < arg->opts->max_solutions) { + append_alg(arg->sols, arg->current_alg); + transform_alg( + inverse_trans(arg->t), arg->sols->last->alg); + if (arg->opts->verbose) + print_alg(arg->sols->last->alg, false); + } + + pthread_mutex_unlock(arg->sols_mutex); + } +} + +static void +dfs_niss(DfsArg *arg) +{ + DfsArg newarg; + Alg *inv; + Cube *c; + + copy_dfsarg(arg, &newarg); + + /* Invert current alg and scramble */ + newarg.cube = malloc(sizeof(Cube)); + inv = inverse_alg(arg->current_alg); + c = malloc(sizeof(Cube)); + make_solved(newarg.cube); + apply_alg(inv, newarg.cube); + copy_cube(arg->cube, c); + invert_cube(c); + compose(c, newarg.cube); + + /* New indexes */ + compute_ind(newarg.s, newarg.cube, newarg.ind); + + newarg.niss = !(arg->niss); + + dfs(&newarg); + + free_alg(inv); + free(c); + free(newarg.cube); +} + +static bool +dfs_move_checkstop(DfsArg *arg) +{ + int i, goal, nsols; + Move mm; + Trans tt = uf; /* Avoid uninitialized warning */ + + /* Moving and computing bound */ + arg->bound = 0; + goal = arg->d - arg->current_alg->len; + for (i = 0; i < arg->s->n_coord; i++) { + if (arg->last[0] != NULLMOVE) { + mm = transform_move(arg->ind[i].t, arg->last[0]); + arg->ind[i].val = move_coord(arg->s->coord[i], + mm, arg->ind[i].val, &tt); + arg->ind[i].t = transform_trans(tt, arg->ind[i].t); + } + + arg->bound = + MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val)); + if (arg->opts->can_niss && !arg->niss) + arg->bound = MIN(1, arg->bound); + + if (arg->bound > goal) + return true; + } + + pthread_mutex_lock(arg->sols_mutex); + nsols = arg->sols->len; + pthread_mutex_unlock(arg->sols_mutex); + + return nsols >= arg->opts->max_solutions; +} + +static void * +instance_thread(void *arg) +{ + bool b, inv; + Cube c; + Move m; + ThreadDataSolve *td; + AlgListNode *node; + DfsArg darg; + + td = (ThreadDataSolve *)arg; + + while (1) { + b = false; + + pthread_mutex_lock(td->start_mutex); + if ((node = *(td->node)) == NULL) + b = true; + else + *(td->node) = (*(td->node))->next; + pthread_mutex_unlock(td->start_mutex); + + if (b) + break; + + inv = node->alg->inv[0]; + m = node->alg->move[0]; + + copy_cube(td->arg.cube, &c); + if (inv) + invert_cube(&c); + + copy_dfsarg(&td->arg, &darg); + compute_ind(td->arg.s, &c, darg.ind); + darg.cube = &c; + + darg.niss = inv; + darg.current_alg = new_alg(""); + append_move(darg.current_alg, m, inv); + + dfs(&darg); + + free_alg(darg.current_alg); + } + + return NULL; +} + +static void +multidfs(DfsArg *arg) +{ + int i; + Cube local_cube; + Alg *alg; + AlgList *start; + AlgListNode **node; + pthread_t t[arg->opts->nthreads]; + ThreadDataSolve td[arg->opts->nthreads]; + pthread_mutex_t *start_mutex, *sols_mutex; + + node = malloc(sizeof(AlgListNode *)); + start_mutex = malloc(sizeof(pthread_mutex_t)); + sols_mutex = malloc(sizeof(pthread_mutex_t)); + + start = new_alglist(); + pthread_mutex_init(start_mutex, NULL); + pthread_mutex_init(sols_mutex, NULL); + + for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { + alg = new_alg(""); + append_move(alg, arg->s->moveset->sorted_moves[i], false); + append_alg(start, alg); + if (arg->opts->can_niss && !arg->s->final) { + alg->inv[0] = true; + append_alg(start, alg); + } + free_alg(alg); + } + *node = start->first; + + copy_cube(arg->cube, &local_cube); + + for (i = 0; i < arg->opts->nthreads; i++) { + copy_dfsarg(arg, &(td[i].arg)); + td[i].arg.cube = &local_cube; + td[i].arg.sols_mutex = sols_mutex; + + td[i].thid = i; + td[i].start = start; + td[i].node = node; + td[i].start_mutex = start_mutex; + + pthread_create(&t[i], NULL, instance_thread, &td[i]); + } + + for (i = 0; i < arg->opts->nthreads; i++) + pthread_join(t[i], NULL); + + free_alglist(start); + free(node); + free(start_mutex); + free(sols_mutex); +} + +static bool +niss_makes_sense(DfsArg *arg) +{ + Move m, mm; + uint64_t u; + int i; + + if (arg->s->final || arg->niss || !arg->opts->can_niss) + return false; + + if (arg->current_alg->len_normal == 0) + return true; + + m = inverse_move(arg->last[0]); + for (i = 0; i < arg->s->n_coord; i++) { + mm = transform_move(arg->ind[i].t, m); + u = move_coord(arg->s->coord[i], mm, 0, NULL); + if (ptableval(arg->s->pd[i], u) > 0) + return true; + } + + return false; +} + +static bool +solvestop(int d, int op, SolveOptions *opts, AlgList *sols) +{ + bool opt_done, max_moves_exceeded, max_sols_exceeded; + + opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op; + max_moves_exceeded = d > opts->max_moves; + max_sols_exceeded = sols->len >= opts->max_solutions; + + return opt_done || max_moves_exceeded || max_sols_exceeded; +} + +/* Public functions **********************************************************/ + +AlgList * +solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) +{ + int i, j, d, op, est; + bool ready[99], one_ready, zerosol; + Movable ind[99][10]; + AlgList *s; + Cube *c[99]; + DfsArg arg[99]; + + prepare_cs(cs, opts); + s = new_alglist(); + + for (i = 0, one_ready = false; cs->step[i] != NULL; i++) { + c[i] = malloc(sizeof(Cube)); + copy_cube(cube, c[i]); + apply_trans(cs->t[i], c[i]); + + arg[i].cube = c[i]; + arg[i].t = cs->t[i]; + arg[i].s = cs->step[i]; + arg[i].opts = opts; + arg[i].sols = s; + + if ((ready[i] = cs->step[i]->ready(c[i]))) { + one_ready = true; + /* Only for local use for 0 moves solutions */ + compute_ind(cs->step[i], c[i], ind[i]); + } + } + if (!one_ready) { + fprintf(stderr, "Cube not ready for solving step: "); + fprintf(stderr, "%s\n", cs->ready_msg); + return s; + } + + /* If the empty moves sequence is a solution for one of the + * alternatives, all longer solutions will be discarded, so we may + * just set its ready[] value to false. If the solution is accepted + * we append it and start searching from d = 1. */ + for (i = 0, zerosol = false; cs->step[i] != NULL; i++) { + if (ready[i]) { + est = 0; + for (j = 0; j < cs->step[i]->n_coord; j++) + est = MAX(est, ptableval(cs->step[i]->pd[j], + ind[i][j].val)); + if (est == 0) { + ready[i] = false; + zerosol = true; + } + } + } + if (zerosol && opts->min_moves == 0) { + append_alg(s, new_alg("")); + opts->min_moves = 1; + if (opts->verbose) + printf("Step is already solved" + "(empty alg is a solution)\n"); + } + + for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { + if (opts->verbose) + fprintf(stderr, "Searching depth %d\n", d); + + for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { + if (!ready[i]) + continue; + + arg[i].d = d; + multidfs(&arg[i]); + + if (s->len > 0 && op == -1) + op = d; + } + } + + for (i = 0; cs->step[i] != NULL; i++) + free(c[i]); + + return s; +} + +/* TODO: make more general! */ +Alg * +solve_2phase(Cube *cube, int nthreads) +{ + int bestlen, newb; + Alg *bestalg, *ret; + AlgList *sols1, *sols2; + AlgListNode *i; + Cube c; + SolveOptions opts1, opts2; + + opts1.min_moves = 0; + opts1.max_moves = 13; + opts1.max_solutions = 20; + opts1.nthreads = nthreads; + opts1.optimal = 3; + opts1.can_niss = false; + opts1.verbose = false; + opts1.all = true; + + opts2.min_moves = 0; + opts2.max_moves = 19; + opts2.max_solutions = 1; + opts2.nthreads = nthreads; + opts2.can_niss = false; + opts2.verbose = false; + + /* We skip step1 if it is solved on U/D */ + if (check_drud(cube)) { + sols1 = new_alglist(); + append_alg(sols1, new_alg("")); + } else { + sols1 = solve(cube, &drud_HTM, &opts1); + } + bestalg = new_alg(""); + bestlen = 999; + for (i = sols1->first; i != NULL; i = i->next) { + copy_cube(cube, &c); + apply_alg(i->alg, &c); + sols2 = solve(&c, &dranyfin_DR, &opts2); + + if (sols2->len > 0) { + newb = i->alg->len + sols2->first->alg->len; + if (newb < bestlen) { + bestlen = newb; + copy_alg(i->alg, bestalg); + compose_alg(bestalg, sols2->first->alg); + } + } + + free_alglist(sols2); + } + + free_alglist(sols1); + + ret = cleanup(bestalg); + free_alg(bestalg); + + return ret; +} diff --git a/old/solve_old.h b/old/solve_old.h @@ -0,0 +1,9 @@ +#ifndef SOLVE_H +#define SOLVE_H + +#include "movesets.h" + +AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts); +Alg * solve_2phase(Cube *cube, int nthreads); + +#endif diff --git a/src/alg.c b/src/alg.c @@ -6,57 +6,6 @@ static int axis(Move m); static void free_alglistnode(AlgListNode *aln); static void realloc_alg(Alg *alg, int n); -bool -allowed_HTM(Move m) -{ - return m >= U && m <= B3; -} - -bool -allowed_URF(Move m) -{ - Move b = base_move(m); - - return b == U || b == R || b == F; -} - -bool -allowed_eofb(Move m) -{ - Move b = base_move(m); - - return b == U || b == D || b == R || b == L || - ((b == F || b == B) && m == b+1); -} - -bool -allowed_drud(Move m) -{ - Move b = base_move(m); - - return b == U || b == D || - ((b == R || b == L || b == F || b == B) && m == b + 1); -} - -bool -allowed_htr(Move m) -{ - Move b = base_move(m); - - return moveset_HTM.allowed(m) && m == b + 1; -} - -bool -allowed_next_all(Move l2, Move l1, Move m) -{ - bool p, q; - - p = l1 != NULLMOVE && base_move(l1) == base_move(m); - q = l2 != NULLMOVE && base_move(l2) == base_move(m); - - return !(p || (commute(l1, l2) && q)); -} - void append_alg(AlgList *l, Alg *alg) { @@ -137,6 +86,32 @@ commute(Move m1, Move m2) return axis(m1) == axis(m2); } +int +compare(Move m1, Move m2) +{ + if (!commute(m1, m2)) + return 0; + + return m1 < m2 ? 1 : -1; +} + +int +compare_last(Alg *alg, Move m, bool inverse) +{ + Move last; + int n; + + if (inverse) { + n = alg->len_inverse; + last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; + } else { + n = alg->len_normal; + last = n > 0 ? alg->move_normal[n-1] : NULLMOVE; + } + + return compare(last, m); +} + void compose_alg(Alg *alg1, Alg *alg2) { @@ -355,19 +330,6 @@ on_inverse(Alg *alg) return ret; } -bool -possible_next(Move m, Moveset *ms, Move l0, Move l1) -{ - bool allowed, order; - uint64_t mbit; - - mbit = ((uint64_t)1) << m; - allowed = mbit & ms->mask[l1][l0]; - order = !commute(l0, m) || l0 < m; - - return allowed && order; -} - void print_alg(Alg *alg, bool l) { @@ -431,6 +393,17 @@ realloc_alg(Alg *alg, int n) } void +remove_last_move(Alg *a) +{ + a->len--; + + if (a->inv[a->len]) + a->len_inverse--; + else + a->len_normal--; +} + +void swapmove(Move *m1, Move *m2) { Move aux; @@ -484,29 +457,3 @@ unniss(Alg *alg) return ret; } - -void -init_moveset(Moveset *ms) -{ - int j; - uint64_t l, one; - Move m, l2, l1; - - one = 1; - - for (j = 0, m = U; m < NMOVES; m++) - if (ms->allowed(m)) - ms->sorted_moves[j++] = m; - ms->sorted_moves[j] = NULLMOVE; - - for (l1 = 0; l1 < NMOVES; l1++) { - for (l2 = 0; l2 < NMOVES; l2++) { - ms->mask[l2][l1] = 0; - for (l = 0; ms->sorted_moves[l] != NULLMOVE; l++) { - m = ms->sorted_moves[l]; - if (ms->allowed_next(l2, l1, m)) - ms->mask[l2][l1] |= (one<<m); - } - } - } -} diff --git a/src/alg.h b/src/alg.h @@ -8,21 +8,11 @@ #include "cubetypes.h" #include "utils.h" -bool allowed_all(Move m); -bool allowed_HTM(Move m); -bool allowed_URF(Move m); -bool allowed_eofb(Move m); -bool allowed_drud(Move m); -bool allowed_htr(Move m); -bool allowed_next_all(Move l2, Move l1, Move m); - -void moveset_to_list(Moveset ms, Move *lst); -void init_moveset(Moveset *ms); -bool possible_next(Move m, Moveset *ms, Move l0, Move l1); - void append_alg(AlgList *l, Alg *alg); void append_move(Alg *alg, Move m, bool inverse); Move base_move(Move m); +int compare(Move m1, Move m2); /* Return 1 (m1<m2), 0 or -1 (m1>m2) */ +int compare_last(Alg *alg, Move m, bool inverse); void compose_alg(Alg *alg1, Alg *alg2); bool commute(Move m1, Move m2); void copy_alg(Alg *src, Alg *dst); @@ -36,70 +26,10 @@ AlgList * new_alglist(); Alg * on_inverse(Alg *alg); void print_alg(Alg *alg, bool l); void print_alglist(AlgList *al, bool l); +void remove_last_move(Alg *alg); void swapmove(Move *m1, Move *m2); char * trans_string(Trans t); /* Here because similar to move_string, move? */ Alg * unniss(Alg *alg); -/* Movesets ******************************************************************/ - -#ifndef ALG_C - -extern Moveset moveset_HTM; -extern Moveset moveset_URF; -extern Moveset moveset_eofb; -extern Moveset moveset_drud; -extern Moveset moveset_htr; - -extern Moveset * all_ms[]; - -#else - -Moveset -moveset_HTM = { - .name = "HTM", - .allowed = allowed_HTM, - .allowed_next = allowed_next_all, -}; - -Moveset -moveset_URF = { - .name = "URF", - .allowed = allowed_URF, - .allowed_next = allowed_next_all, -}; - -Moveset -moveset_eofb = { - .name = "eofb", - .allowed = allowed_eofb, - .allowed_next = allowed_next_all, -}; - -Moveset -moveset_drud = { - .name = "drud", - .allowed = allowed_drud, - .allowed_next = allowed_next_all, -}; - -Moveset -moveset_htr = { - .name = "htr", - .allowed = allowed_htr, - .allowed_next = allowed_next_all, -}; - -Moveset * -all_ms[] = { - &moveset_HTM, - &moveset_URF, - &moveset_eofb, - &moveset_drud, - &moveset_htr, - NULL -}; - -#endif - #endif diff --git a/src/commands.c b/src/commands.c @@ -215,10 +215,21 @@ solve_exec(CommandArgs *args) { Cube c; AlgList *sols; + Solver *solver[99]; + Threader *threader; make_solved(&c); apply_alg(args->scramble, &c); - sols = solve(&c, args->cs, args->opts); +/* TODO: adjust */ +/* threader = &threader_single;*/ + threader = &threader_eager; + +/* TODO: adjust */ + int i; + for (i = 0; args->cs->step[i] != NULL; i++) + solver[i] = new_stepsolver_lazy(args->cs->step[i]); + solver[i] = NULL; + sols = solve(&c, args->opts, solver, threader); if (args->opts->count_only) printf("%d\n", sols->len); @@ -285,7 +296,10 @@ scramble_exec(CommandArgs *args) } /* TODO: can be optimized for htr and dr using htrfin, drfin */ + /* + TODO: solve_2phase was removed scr = solve_2phase(&cube, 1); + */ if (!strcmp(args->scrtype, "fmc")) { aux = new_alg(""); @@ -383,6 +397,7 @@ print_exec(CommandArgs *args) print_cube(&c); } +/* void twophase_exec(CommandArgs *args) { @@ -396,6 +411,7 @@ twophase_exec(CommandArgs *args) print_alg(sol, false); free_alg(sol); } +*/ void help_exec(CommandArgs *args) diff --git a/src/commands.h b/src/commands.h @@ -5,6 +5,9 @@ #include "solve.h" #include "steps.h" +#include "solver_step.h" +#include "threader_single.h" +#include "threader_eager.h" void free_args(CommandArgs *args); CommandArgs * new_args(); @@ -29,7 +32,7 @@ void steps_exec(CommandArgs *args); void commands_exec(CommandArgs *args); void freemem_exec(CommandArgs *args); void print_exec(CommandArgs *args); -void twophase_exec(CommandArgs *args); +/*void twophase_exec(CommandArgs *args);*/ void help_exec(CommandArgs *args); void quit_exec(CommandArgs *args); void unniss_exec(CommandArgs *args); @@ -138,6 +141,7 @@ help_cmd = { .exec = help_exec, }; +/* Command twophase_cmd = { .name = "twophase", @@ -146,6 +150,7 @@ twophase_cmd = { .parse_args = parse_only_scramble, .exec = twophase_exec, }; +*/ Command quit_cmd = { @@ -194,7 +199,7 @@ Command *commands[] = { &solve_cmd, &scramble_cmd, &steps_cmd, - &twophase_cmd, +/* &twophase_cmd,*/ &cleanup_cmd, &unniss_cmd, &version_cmd, diff --git a/src/cubetypes.h b/src/cubetypes.h @@ -89,7 +89,7 @@ typedef struct command Command; typedef struct commandargs CommandArgs; typedef struct coordinate Coordinate; typedef struct cube Cube; -typedef struct dfsarg DfsArg; +/*typedef struct dfsarg DfsArg;*/ typedef struct fstcube FstCube; typedef struct indexer Indexer; typedef struct movable Movable; @@ -104,9 +104,9 @@ typedef struct transgroup TransGroup; typedef bool (*Checker) (Cube *); typedef bool (*CubeTester) (Cube *, Alg *); -typedef bool (*DfsMover) (DfsArg *); +/*typedef bool (*DfsMover) (DfsArg *);*/ typedef void (*DfsExtraCopier) (void *, void *); -typedef bool (*Validator) (Alg *); +typedef Alg * (*Validator) (Alg *); typedef void (*Exec) (CommandArgs *); typedef CommandArgs * (*ArgParser) (int, char **); typedef bool (*Tester) (void); @@ -206,13 +206,16 @@ cube int xp[6]; }; +/* struct movable { uint64_t val; Trans t; }; +*/ +/* struct dfsarg { @@ -224,13 +227,28 @@ dfsarg int d; int bound; bool niss; - Move last[2]; - Move lastinv[2]; AlgList * sols; pthread_mutex_t * sols_mutex; Alg * current_alg; void * extra; }; +*/ + +/* +struct +dfsarg +{ + void * cube_data; + SolveOptions * opts; + int d; + int bound; + bool niss; + AlgList * sols; + Alg * current_alg; + Solver * solver; + Threader * threader; +}; +*/ struct fstcube @@ -260,9 +278,9 @@ moveset { char * name; bool (*allowed)(Move); - bool (*allowed_next)(Move, Move, Move); + bool (*can_append)(Alg *, Move, bool); + bool (*cancel_niss)(Alg *); Move sorted_moves[NMOVES+1]; - uint64_t mask[NMOVES][NMOVES]; }; struct @@ -304,10 +322,11 @@ step PruneData * pd[MAX_N_COORD]; bool pd_compact[MAX_N_COORD]; Validator is_valid; - DfsMover custom_move_checkstop; + /*DfsMover custom_move_checkstop;*/ DfsExtraCopier copy_extra; }; +/* struct threaddatasolve { @@ -317,6 +336,7 @@ threaddatasolve AlgListNode ** node; pthread_mutex_t * start_mutex; }; +*/ struct threaddatagenpt diff --git a/src/movesets.c b/src/movesets.c @@ -0,0 +1,194 @@ +#define MOVESETS_C + +#include "movesets.h" + +static bool allowed_HTM(Move m); +static bool allowed_URF(Move m); +static bool allowed_eofb(Move m); +static bool allowed_drud(Move m); +static bool allowed_htr(Move m); +static bool can_append_HTM(Move l2, Move l1, Move m); +static bool can_append_HTM_cached(Alg *alg, Move m, bool inverse); +static bool cancel_niss_HTM_cached(Alg *alg); +static void init_can_append_HTM(); + +Moveset +moveset_HTM = { + .name = "HTM", + .allowed = allowed_HTM, + .can_append = can_append_HTM_cached, + .cancel_niss = cancel_niss_HTM_cached, +}; + +Moveset +moveset_URF = { + .name = "URF", + .allowed = allowed_URF, + .can_append = can_append_HTM_cached, + .cancel_niss = cancel_niss_HTM_cached, +}; + +Moveset +moveset_eofb = { + .name = "eofb", + .allowed = allowed_eofb, + .can_append = can_append_HTM_cached, + .cancel_niss = cancel_niss_HTM_cached, +}; + +Moveset +moveset_drud = { + .name = "drud", + .allowed = allowed_drud, + .can_append = can_append_HTM_cached, + .cancel_niss = cancel_niss_HTM_cached, +}; + +Moveset +moveset_htr = { + .name = "htr", + .allowed = allowed_htr, + .can_append = can_append_HTM_cached, + .cancel_niss = cancel_niss_HTM_cached, +}; + +Moveset * +all_movesets[] = { + &moveset_HTM, + &moveset_URF, + &moveset_eofb, + &moveset_drud, + &moveset_htr, + NULL +}; + +static uint64_t can_append_HTM_mask[NMOVES][NMOVES]; + +static bool +allowed_HTM(Move m) +{ + return m >= U && m <= B3; +} + +static bool +allowed_URF(Move m) +{ + Move b = base_move(m); + + return b == U || b == R || b == F; +} + +static bool +allowed_eofb(Move m) +{ + Move b = base_move(m); + + return b == U || b == D || b == R || b == L || + ((b == F || b == B) && m == b+1); +} + +static bool +allowed_drud(Move m) +{ + Move b = base_move(m); + + return b == U || b == D || + ((b == R || b == L || b == F || b == B) && m == b + 1); +} + +static bool +allowed_htr(Move m) +{ + Move b = base_move(m); + + return moveset_HTM.allowed(m) && m == b + 1; +} + +static bool +can_append_HTM(Move l2, Move l1, Move m) +{ + bool cancel, cancel_last, cancel_swap; + + cancel_last = l1 != NULLMOVE && base_move(l1) == base_move(m); + cancel_swap = l2 != NULLMOVE && base_move(l2) == base_move(m); + cancel = cancel_last || (commute(l1, l2) && cancel_swap); + + return !cancel; +} + +static bool +can_append_HTM_cached(Alg *alg, Move m, bool inverse) +{ + Move *moves, l1, l2; + uint64_t mbit; + int n; + + if (inverse) { + moves = alg->move_inverse; + n = alg->len_inverse; + } else { + moves = alg->move_normal; + n = alg->len_normal; + } + + l1 = n > 0 ? moves[n-1] : NULLMOVE; + l2 = n > 1 ? moves[n-2] : NULLMOVE; + + mbit = ((uint64_t)1) << m; + + return can_append_HTM_mask[l2][l1] & mbit; +} + +static bool +cancel_niss_HTM_cached(Alg *alg) +{ + Move i1, i2; + int n; + bool can_first, can_swap; + + n = alg->len_inverse; + i1 = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; + i2 = n > 1 ? alg->move_inverse[n-2] : NULLMOVE; + + can_first = can_append_HTM_cached(alg, inverse_move(i1), false); + can_swap = can_append_HTM_cached(alg, inverse_move(i2), false); + + return can_first && (!commute(i1, i2) || can_swap); +} + +static void +init_can_append_HTM() +{ + Move l2, l1, m; + + for (l1 = 0; l1 < NMOVES; l1++) + for (l2 = 0; l2 < NMOVES; l2++) + for (m = 0; m < NMOVES; m++) + if (can_append_HTM(l2, l1, m)) + can_append_HTM_mask[l2][l1] + |= (((uint64_t)1) << m); +} + +void +init_moveset(Moveset *ms) +{ + int j; + Move m; + + for (j = 0, m = U; m < NMOVES; m++) + if (ms->allowed(m)) + ms->sorted_moves[j++] = m; + ms->sorted_moves[j] = NULLMOVE; + +/* TODO: should be here? maybe just init all movesets together anyway... */ + init_can_append_HTM(); +} + +void +init_movesets() +{ + int i; + + for (i = 0; all_movesets[i] != NULL; i++) + init_moveset(all_movesets[i]); +} diff --git a/src/movesets.h b/src/movesets.h @@ -0,0 +1,15 @@ +#ifndef MOVESETS_H +#define MOVESETS_H + +#include "alg.h" + +void init_moveset(Moveset *); +void init_movesets(); + +extern Moveset moveset_HTM; +extern Moveset moveset_URF; +extern Moveset moveset_eofb; +extern Moveset moveset_drud; +extern Moveset moveset_htr; + +#endif diff --git a/src/pruning.h b/src/pruning.h @@ -2,6 +2,7 @@ #define PRUNING_H #include "coord.h" +#include "movesets.h" void free_pd(PruneData *pd); PruneData * genptable(PruneData *data, int nthreads); diff --git a/src/solve.c b/src/solve.c @@ -2,485 +2,118 @@ #include "solve.h" -/* Local functions ***********************************************************/ - -static bool cancel_niss(DfsArg *arg); -static void copy_dfsarg(DfsArg *src, DfsArg *dst); -static void dfs(DfsArg *arg); -static void dfs_add_sol(DfsArg *arg); -static void dfs_niss(DfsArg *arg); -static bool dfs_move_checkstop(DfsArg *arg); -static void * instance_thread(void *arg); -static void multidfs(DfsArg *arg); -static bool niss_makes_sense(DfsArg *arg); -static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols); - -/* Local functions ***********************************************************/ - -static bool -cancel_niss(DfsArg *arg) -{ - Moveset *ms; - Move i1, i2; - bool p, p1, p2, q, q1, q2; - - if (arg->lastinv[0] == NULLMOVE) - return false; - - ms = arg->s->moveset; - i1 = inverse_move(arg->lastinv[0]); - i2 = inverse_move(arg->lastinv[1]); - - p1 = !ms->allowed_next(arg->last[1], arg->last[0], i1); - p2 = !ms->allowed_next(arg->last[1], i1, arg->last[0]); - p = p1 || (commute(i1, arg->last[0]) && p2); - - q1 = !ms->allowed_next(arg->last[1], arg->last[0], i2); - q2 = !ms->allowed_next(arg->last[1], i2, arg->last[0]); - q = q1 || (commute(i2, arg->last[0]) && q2); - - return p || (commute(i1, i2) && q); -} - -static void -copy_dfsarg(DfsArg *src, DfsArg *dst) -{ - int i; - - dst->cube = src->cube; - dst->t = src->t; - dst->s = src->s; - dst->opts = src->opts; - dst->d = src->d; - dst->bound = src->bound; /* In theory not needed */ - dst->niss = src->niss; - dst->sols = src->sols; - dst->sols_mutex = src->sols_mutex; - dst->current_alg = src->current_alg; - - for (i = 0; i < 2; i++) { - dst->last[i] = src->last[i]; - dst->lastinv[i] = src->lastinv[i]; - } - - for (i = 0; i < src->s->n_coord; i++) { - dst->ind[i].val = src->ind[i].val; - dst->ind[i].t = src->ind[i].t; - } - - src->s->copy_extra(src, dst); -} - -static void -dfs(DfsArg *arg) +void +dfs(DfsArg *arg, Solver *solver, Threader *threader) { int i; - Move m, l0, l1; DfsArg newarg; + Alg *sol; + Move m; - if (dfs_move_checkstop(arg)) - return; - - if (arg->bound == 0) { - if (arg->current_alg->len == arg->d) - dfs_add_sol(arg); + if (arg->current_alg->len > arg->d) return; - } - - for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { - m = arg->s->moveset->sorted_moves[i]; - l0 = arg->last[0]; - l1 = arg->last[1]; - if (possible_next(m, arg->s->moveset, l0, l1)) { - copy_dfsarg(arg, &newarg); - newarg.last[1] = l0; - newarg.last[0] = m; - append_move(arg->current_alg, m, newarg.niss); - dfs(&newarg); - arg->current_alg->len--; - } - } - - if (niss_makes_sense(arg)) - dfs_niss(arg); -} -static void -dfs_add_sol(DfsArg *arg) -{ - bool valid, accepted, nisscanc; - - valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); - accepted = valid || arg->opts->all; - nisscanc = arg->s->final && cancel_niss(arg); + if (solver->is_solved(solver->param, arg->cubedata)) { +/* TODO: the "all" option should be re-implemented as setting +validate to null */ - if (accepted && !nisscanc) { - pthread_mutex_lock(arg->sols_mutex); +/* TODO: we also have to check if cancel with NISS; +we can't because we have no access to the s->final field +this should be done by the step's validator? */ + sol = solver->validate_solution(solver->param,arg->current_alg); + bool accepted = sol != NULL; + bool too_short = arg->current_alg->len != arg->d; - if (arg->sols->len < arg->opts->max_solutions) { - append_alg(arg->sols, arg->current_alg); - transform_alg( - inverse_trans(arg->t), arg->sols->last->alg); + if (accepted && !too_short) { +/* TODO: arg->t got lost in refactoring */ +/* transform_alg(inverse_trans(arg->t), sol);*/ if (arg->opts->verbose) - print_alg(arg->sols->last->alg, false); - } - - pthread_mutex_unlock(arg->sols_mutex); - } -} - -static void -dfs_niss(DfsArg *arg) -{ - DfsArg newarg; - Alg *inv; - Cube *c; - - copy_dfsarg(arg, &newarg); - - /* Invert current alg and scramble */ - newarg.cube = malloc(sizeof(Cube)); - inv = inverse_alg(arg->current_alg); - c = malloc(sizeof(Cube)); - make_solved(newarg.cube); - apply_alg(inv, newarg.cube); - copy_cube(arg->cube, c); - invert_cube(c); - compose(c, newarg.cube); - - /* New indexes */ - compute_ind(newarg.s, newarg.cube, newarg.ind); - - swapmove(&(newarg.last[0]), &(newarg.lastinv[0])); - swapmove(&(newarg.last[1]), &(newarg.lastinv[1])); - newarg.niss = !(arg->niss); - - dfs(&newarg); - - free_alg(inv); - free(c); - free(newarg.cube); -} - -static bool -dfs_move_checkstop(DfsArg *arg) -{ - int i, goal, nsols; - Move mm; - Trans tt = uf; /* Avoid uninitialized warning */ - - /* Moving and computing bound */ - arg->bound = 0; - goal = arg->d - arg->current_alg->len; - for (i = 0; i < arg->s->n_coord; i++) { - if (arg->last[0] != NULLMOVE) { - mm = transform_move(arg->ind[i].t, arg->last[0]); - arg->ind[i].val = move_coord(arg->s->coord[i], - mm, arg->ind[i].val, &tt); - arg->ind[i].t = transform_trans(tt, arg->ind[i].t); + print_alg(sol, false); + threader->append_sol(sol, arg->threaddata); } - - arg->bound = - MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val)); - if (arg->opts->can_niss && !arg->niss) - arg->bound = MIN(1, arg->bound); - - if (arg->bound > goal) - return true; - } - - pthread_mutex_lock(arg->sols_mutex); - nsols = arg->sols->len; - pthread_mutex_unlock(arg->sols_mutex); - - return nsols >= arg->opts->max_solutions; -} - -static void * -instance_thread(void *arg) -{ - bool b, inv; - Cube c; - Move m; - ThreadDataSolve *td; - AlgListNode *node; - DfsArg darg; - - td = (ThreadDataSolve *)arg; - - while (1) { - b = false; - - pthread_mutex_lock(td->start_mutex); - if ((node = *(td->node)) == NULL) - b = true; - else - *(td->node) = (*(td->node))->next; - pthread_mutex_unlock(td->start_mutex); - - if (b) - break; - - inv = node->alg->inv[0]; - m = node->alg->move[0]; - - copy_cube(td->arg.cube, &c); - if (inv) - invert_cube(&c); - - copy_dfsarg(&td->arg, &darg); - compute_ind(td->arg.s, &c, darg.ind); - darg.cube = &c; - - darg.niss = inv; - darg.last[0] = m; - darg.last[1] = NULLMOVE; - darg.lastinv[0] = NULLMOVE; - darg.lastinv[1] = NULLMOVE; - darg.current_alg = new_alg(""); - append_move(darg.current_alg, m, inv); - - dfs(&darg); - - free_alg(darg.current_alg); + return; } - return NULL; -} - -static void -multidfs(DfsArg *arg) -{ - int i; - Cube local_cube; - Alg *alg; - AlgList *start; - AlgListNode **node; - pthread_t t[arg->opts->nthreads]; - ThreadDataSolve td[arg->opts->nthreads]; - pthread_mutex_t *start_mutex, *sols_mutex; - - node = malloc(sizeof(AlgListNode *)); - start_mutex = malloc(sizeof(pthread_mutex_t)); - sols_mutex = malloc(sizeof(pthread_mutex_t)); - - start = new_alglist(); - pthread_mutex_init(start_mutex, NULL); - pthread_mutex_init(sols_mutex, NULL); + if (arg->current_alg->len == arg->d) + return; - for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { - alg = new_alg(""); - append_move(alg, arg->s->moveset->sorted_moves[i], false); - append_alg(start, alg); - if (arg->opts->can_niss && !arg->s->final) { - alg->inv[0] = true; - append_alg(start, alg); +/* TODO: do not alloc */ + newarg.cubedata = solver->alloc_cubedata(solver->param); + for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { + m = solver->moveset->sorted_moves[i]; + if (solver->moveset->can_append(arg->current_alg, m, arg->niss) + && compare_last(arg->current_alg, m, arg->niss) >= 0) { + append_move(arg->current_alg, m, arg->niss); + + solver->copy_cubedata( + solver->param, arg->cubedata, newarg.cubedata); + newarg.threaddata = arg->threaddata; + newarg.opts = arg->opts; + newarg.d = arg->d; + newarg.niss = arg->niss; + newarg.current_alg = arg->current_alg; + if (!solver->move_check_stop( + solver->param, &newarg, threader)) + dfs(&newarg, solver, threader); + + remove_last_move(arg->current_alg); } - free_alg(alg); } - *node = start->first; - - copy_cube(arg->cube, &local_cube); - - for (i = 0; i < arg->opts->nthreads; i++) { - copy_dfsarg(arg, &(td[i].arg)); - td[i].arg.cube = &local_cube; - td[i].arg.sols_mutex = sols_mutex; - - td[i].thid = i; - td[i].start = start; - td[i].node = node; - td[i].start_mutex = start_mutex; + solver->free_cubedata(solver->param, newarg.cubedata); - pthread_create(&t[i], NULL, instance_thread, &td[i]); + if (arg->opts->can_niss && !arg->niss && + solver->niss_makes_sense( + solver->param, arg->cubedata, arg->current_alg)) { + solver->invert_cube(solver->param, arg->cubedata); + arg->niss = true; + dfs(arg, solver, threader); } - - for (i = 0; i < arg->opts->nthreads; i++) - pthread_join(t[i], NULL); - - free_alglist(start); - free(node); - free(start_mutex); - free(sols_mutex); } -static bool -niss_makes_sense(DfsArg *arg) -{ - Move m, mm; - uint64_t u; - int i; - - if (arg->s->final || arg->niss || !arg->opts->can_niss) - return false; - - if (arg->last[0] == NULLMOVE) - return true; - - m = inverse_move(arg->last[0]); - for (i = 0; i < arg->s->n_coord; i++) { - mm = transform_move(arg->ind[i].t, m); - u = move_coord(arg->s->coord[i], mm, 0, NULL); - if (ptableval(arg->s->pd[i], u) > 0) - return true; - } - - return false; -} - -static bool -solvestop(int d, int op, SolveOptions *opts, AlgList *sols) -{ - bool opt_done, max_moves_exceeded, max_sols_exceeded; - - opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op; - max_moves_exceeded = d > opts->max_moves; - max_sols_exceeded = sols->len >= opts->max_solutions; - - return opt_done || max_moves_exceeded || max_sols_exceeded; -} - -/* Public functions **********************************************************/ - AlgList * -solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) +solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader) { - int i, j, d, op, est; - bool ready[99], one_ready, zerosol; - Movable ind[99][10]; - AlgList *s; - Cube *c[99]; - DfsArg arg[99]; - - prepare_cs(cs, opts); - s = new_alglist(); - - for (i = 0, one_ready = false; cs->step[i] != NULL; i++) { - c[i] = malloc(sizeof(Cube)); - copy_cube(cube, c[i]); - apply_trans(cs->t[i], c[i]); - - arg[i].cube = c[i]; - arg[i].t = cs->t[i]; - arg[i].s = cs->step[i]; + int i, d, optimal; + bool ready[MAX_SOLVERS], stop, one_ready; + DfsArg arg[MAX_SOLVERS]; + AlgList *sols; + + one_ready = false; + for (i = 0; solver[i] != NULL; i++) { + arg[i].cubedata = + solver[i]->prepare_cube(solver[i]->param, cube); arg[i].opts = opts; - arg[i].sols = s; - - if ((ready[i] = cs->step[i]->ready(c[i]))) { - one_ready = true; - /* Only for local use for 0 moves solutions */ - compute_ind(cs->step[i], c[i], ind[i]); - } - } - if (!one_ready) { - fprintf(stderr, "Cube not ready for solving step: "); - fprintf(stderr, "%s\n", cs->ready_msg); - return s; + ready[i] = arg[i].cubedata != NULL; + one_ready = one_ready || ready[i]; } - /* If the empty moves sequence is a solution for one of the - * alternatives, all longer solutions will be discarded, so we may - * just set its ready[] value to false. If the solution is accepted - * we append it and start searching from d = 1. */ - for (i = 0, zerosol = false; cs->step[i] != NULL; i++) { - if (ready[i]) { - est = 0; - for (j = 0; j < cs->step[i]->n_coord; j++) - est = MAX(est, ptableval(cs->step[i]->pd[j], - ind[i][j].val)); - if (est == 0) { - ready[i] = false; - zerosol = true; - } - } - } - if (zerosol && opts->min_moves == 0) { - append_alg(s, new_alg("")); - opts->min_moves = 1; - if (opts->verbose) - printf("Step is already solved" - "(empty alg is a solution)\n"); + sols = new_alglist(); + if (!one_ready) { + fprintf(stderr, "Cube not ready for solving\n"); + return sols; } - for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { + optimal = opts->max_moves; + stop = false; + for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) { if (opts->verbose) fprintf(stderr, "Searching depth %d\n", d); - for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { + for (i = 0; solver[i] != NULL && !stop; i++) { if (!ready[i]) continue; arg[i].d = d; - multidfs(&arg[i]); - - if (s->len > 0 && op == -1) - op = d; - } - } - - for (i = 0; cs->step[i] != NULL; i++) - free(c[i]); - - return s; -} + threader->dispatch(&arg[i], sols, solver[i], threader); -/* TODO: make more general! */ -Alg * -solve_2phase(Cube *cube, int nthreads) -{ - int bestlen, newb; - Alg *bestalg, *ret; - AlgList *sols1, *sols2; - AlgListNode *i; - Cube c; - SolveOptions opts1, opts2; - - opts1.min_moves = 0; - opts1.max_moves = 13; - opts1.max_solutions = 20; - opts1.nthreads = nthreads; - opts1.optimal = 3; - opts1.can_niss = false; - opts1.verbose = false; - opts1.all = true; + if (sols->len > 0) + optimal = MIN(optimal, d); - opts2.min_moves = 0; - opts2.max_moves = 19; - opts2.max_solutions = 1; - opts2.nthreads = nthreads; - opts2.can_niss = false; - opts2.verbose = false; - - /* We skip step1 if it is solved on U/D */ - if (check_drud(cube)) { - sols1 = new_alglist(); - append_alg(sols1, new_alg("")); - } else { - sols1 = solve(cube, &drud_HTM, &opts1); - } - bestalg = new_alg(""); - bestlen = 999; - for (i = sols1->first; i != NULL; i = i->next) { - copy_cube(cube, &c); - apply_alg(i->alg, &c); - sols2 = solve(&c, &dranyfin_DR, &opts2); - - if (sols2->len > 0) { - newb = i->alg->len + sols2->first->alg->len; - if (newb < bestlen) { - bestlen = newb; - copy_alg(i->alg, bestalg); - compose_alg(bestalg, sols2->first->alg); - } + stop = sols->len >= opts->max_solutions; } - - free_alglist(sols2); + stop = stop || + (opts->optimal != -1 && d >= opts->optimal + optimal); } - free_alglist(sols1); - - ret = cleanup(bestalg); - free_alg(bestalg); - - return ret; + return sols; } diff --git a/src/solve.h b/src/solve.h @@ -2,10 +2,52 @@ #define SOLVE_H #include "moves.h" -#include "steps.h" -#include "trans.h" -AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts); -Alg * solve_2phase(Cube *cube, int nthreads); +#define MAX_SOLVERS 99 + +typedef struct dfsarg DfsArg; +typedef struct threader Threader; +typedef struct solver Solver; + +/* TODO: add solver and threader in DfsData, remove from dispatch args and similar */ + +struct dfsarg { + void * cubedata; + void * threaddata; + SolveOptions * opts; + int d; + bool niss; + Alg * current_alg; +}; + +struct threader { + void (*append_sol)(Alg *, void *); + void (*dispatch)(DfsArg *, AlgList *, Solver *, Threader *); + int (*get_nsol)(void *); +/* TODO: threader should have param, like solver? */ +}; + +struct solver { + Moveset * moveset; + bool (*move_check_stop)(void *, DfsArg *, Threader *); + Alg * (*validate_solution)(void *, Alg *); + bool (*niss_makes_sense)(void *, void *, Alg *); +/* TODO: move param to somewhere where it makes more sense */ + void * param; +/* TODO: the following should be part of a generic cube description */ +/* TODO: remove alloc? */ + 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 *); +/* TODO: remove dependence on Cube, preparation should be done before */ + void * (*prepare_cube)(void *, Cube *); +}; + +void dfs(DfsArg *, Solver *, Threader *); +/* TODO: remove dependence on Cube, preparation should be done before */ +AlgList * solve(Cube *, SolveOptions *, Solver **, Threader *); #endif diff --git a/src/solver_step.c b/src/solver_step.c @@ -0,0 +1,296 @@ +#include "solver_step.h" + +typedef struct { + Cube * cube; + uint64_t * val; + Trans * t; +} CubeData; + +static void apply_alg_cubedata(void *, void *, Alg *); +static void init_indexes(Step *, CubeData *); +static void * prepare_cube(void *, Cube *); +static bool move_check_stop_eager(void *, DfsArg *, Threader *); +static bool move_check_stop_lazy(void *, DfsArg *, Threader *); +static bool move_check_stop_nonsol(void *, DfsArg *, Threader *); +static bool is_solved_step(void *, void *); +static Alg * validate_solution(void *, Alg *); +static void * alloc_cubedata(void *); +static void copy_cubedata(void *, void *, void *); +static void free_cubedata(void *, void *); +static void invert_cubedata(void *, void *); +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) +{ + Step *s = (Step *)param; + CubeData *data = (CubeData *)cubedata; + + apply_alg(alg, data->cube); + init_indexes(s, data); +} + +static void +init_indexes(Step *step, CubeData *data) +{ + int i; + Cube moved; + Trans t, tt; + + for (i = 0; i < step->n_coord; i++) { + t = step->coord_trans[i]; + copy_cube(data->cube, &moved); + apply_trans(t, &moved); + data->val[i] = index_coord(step->coord[i], &moved, &tt); + data->t[i] = transform_trans(tt, t); + } +} + +static void * +prepare_cube(void *param, Cube *cube) +{ + int i; + Step *s; + CubeData *data; + + s = (Step *)param; + + for (i = 0; i < s->n_coord; i++) { + s->pd[i] = malloc(sizeof(PruneData)); + s->pd[i]->moveset = s->moveset; +/* TODO: check if moveset initialization works fine, + e.g. if there is a variable to save the initialized status + or if it gets initialized multiple times */ + init_moveset(s->moveset); + s->pd[i]->coord = s->coord[i]; + gen_coord(s->coord[i]); + s->pd[i]->compact = s->pd_compact[i]; + s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */ + } + + data = alloc_cubedata(param); + data->cube = malloc(sizeof(Cube)); + copy_cube(cube, data->cube); + init_indexes(s, data); + + return data; +} + +static bool +move_check_stop_eager(void *param, DfsArg *arg, Threader *threader) +{ + int nsol; + + if (move_check_stop_nonsol(param, arg, threader)) + return true; + + nsol = threader->get_nsol(arg->threaddata); + return nsol >= arg->opts->max_solutions; +} + +static bool +move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader) +{ + int nsol; + + nsol = threader->get_nsol(arg->threaddata); + if (nsol >= arg->opts->max_solutions) + return true; + + return move_check_stop_nonsol(param, arg, threader); +} + +static bool +move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) +{ + int i, goal, bound; + Move mm, lastmove; + Trans tt = uf; + CubeData *data; + Step *s; + + s = (Step *)param; + data = (CubeData *)arg->cubedata; + + bound = 0; + goal = arg->d - arg->current_alg->len; +/* TODO: check if len is 0 */ + lastmove = arg->current_alg->move[arg->current_alg->len-1]; + for (i = 0; i < s->n_coord; i++) { + mm = transform_move(data->t[i], lastmove); + data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); + data->t[i] = transform_trans(tt, data->t[i]); + + bound = MAX(bound, ptableval(s->pd[i], data->val[i])); + if (arg->opts->can_niss && !arg->niss) + bound = MIN(1, bound); + + if (bound > goal) { + return true; + } + } + + return false; +} + +static bool +is_solved_step(void *param, void *cubedata) +{ + int i; + Step *s; + CubeData *data; + + s = (Step *)param; + data = (CubeData *)cubedata; + + for (i = 0; i < s->n_coord; i++) + if (data->val[i] != 0) + return false; + + return true; +} + +static Alg * +validate_solution(void *param, Alg *alg) +{ + return ((Step *)param)->is_valid(alg); +} + +static void * +alloc_cubedata(void *param) +{ + Step *s; + CubeData *data; + + s = (Step *)param; + + data = malloc(sizeof(CubeData)); + /* We do not need to allocate a cube */ + data->val = malloc(s->n_coord * sizeof(uint64_t)); + data->t = malloc(s->n_coord * sizeof(Trans)); + + return data; +} + +static void +copy_cubedata(void *param, void *src, void *dst) +{ + int i; + Step *s; + CubeData *newdata, *olddata; + + s = (Step *)param; + olddata = (CubeData *)src; + newdata = (CubeData *)dst; + + /* Copy reference: we never move the cube */ + newdata->cube = olddata->cube; + for (i = 0; i < s->n_coord; i++) { + newdata->val[i] = olddata->val[i]; + newdata->t[i] = olddata->t[i]; + } +} + +static void +free_cubedata(void *param, void *cubedata) +{ + CubeData *data; + + data = (CubeData *)cubedata; + + free(data->t); + free(data->val); + /* We do not free the cube */ + free(data); +} + +static void +invert_cubedata(void *param, void *cubedata) +{ + Step *s; + CubeData *data; + + s = (Step *)param; + data = (CubeData *)cubedata; + + invert_cube(data->cube); + init_indexes(s, data); +} + +static bool +niss_makes_sense(void *param, void *cubedata, Alg *alg) +{ + Step *s; + CubeData *data; + + s = (Step *)param; + data = (CubeData *)cubedata; + + if (s->final) + return false; + + if (alg->len_normal == 0) + return true; + + Move m = inverse_move(alg->move_normal[alg->len_normal-1]); + for (int i = 0; i < s->n_coord; i++) { + Move mm = transform_move(data->t[i], m); + uint64_t u = move_coord(s->coord[i], mm, 0, NULL); + if (ptableval(s->pd[i], u) > 0) + return true; + } + + return false; +} + +static Solver * +new_stepsolver_nocheckstop(Step *step) +{ + Solver *solver; + + solver = malloc(sizeof(Solver)); + + solver->moveset = step->moveset; + solver->param = step; + + solver->apply_alg = apply_alg_cubedata; + solver->prepare_cube = prepare_cube; + solver->is_solved = is_solved_step; + solver->validate_solution = validate_solution; + solver->alloc_cubedata = alloc_cubedata; + solver->copy_cubedata = copy_cubedata; + solver->free_cubedata = free_cubedata; + solver->invert_cube = invert_cubedata; + solver->niss_makes_sense = niss_makes_sense; + + return solver; +} + +Solver * +new_stepsolver_eager(Step *step) +{ + Solver *solver; + + solver = new_stepsolver_nocheckstop(step); + solver->move_check_stop = move_check_stop_eager; + + return solver; +} + +Solver * +new_stepsolver_lazy(Step *step) +{ + Solver *solver; + + solver = new_stepsolver_nocheckstop(step); + solver->move_check_stop = move_check_stop_lazy; + + return solver; +} + +void +free_stepsolver(Solver *solver) +{ + free(solver); +} diff --git a/src/solver_step.h b/src/solver_step.h @@ -0,0 +1,12 @@ +#ifndef SOLVER_STEP_H +#define SOLVER_STEP_H + +#include "cube.h" +#include "solve.h" +#include "steps.h" + +Solver *new_stepsolver_eager(Step *); +Solver *new_stepsolver_lazy(Step *); +void free_stepsolver(Solver *); + +#endif diff --git a/src/steps.c b/src/steps.c @@ -106,11 +106,12 @@ check_htr(Cube *cube) return true; } -bool +Alg * validate_singlecw_ending(Alg *alg) { int i; bool nor, inv; + Alg *ret; Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; for (i = 0; i < alg->len; i++) { @@ -126,11 +127,19 @@ validate_singlecw_ending(Alg *alg) nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2)); inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i)); - return nor && inv; + if (nor && inv) { + ret = new_alg(""); + copy_alg(alg, ret); + } else { + ret = NULL; + } + + return ret; } /* Public functions **********************************************************/ +/* void compute_ind(Step *s, Cube *cube, Movable *ind) { @@ -147,6 +156,7 @@ compute_ind(Step *s, Cube *cube, Movable *ind) ind[i].t = transform_trans(tt, t); } } +*/ void prepare_cs(ChoiceStep *cs, SolveOptions *opts) diff --git a/src/steps.h b/src/steps.h @@ -2,6 +2,7 @@ #define STEPS_H #include "pruning.h" +#include "movesets.h" bool check_centers(Cube *cube); bool check_coud_HTM(Cube *cube); @@ -13,10 +14,10 @@ bool check_cornershtr(Cube *cube); bool check_eofb(Cube *cube); bool check_drud(Cube *cube); bool check_htr(Cube *cube); -void compute_ind(Step *a, Cube *cube, Movable *ind); +/*void compute_ind(Step *a, Cube *cube, Movable *ind);*/ void prepare_cs(ChoiceStep *cs, SolveOptions *opts); bool always_valid(Alg *alg); -bool validate_singlecw_ending(Alg *alg); +Alg * validate_singlecw_ending(Alg *alg); #ifndef STEPS_C diff --git a/src/threader_eager.c b/src/threader_eager.c @@ -0,0 +1,162 @@ +#include <pthread.h> +#include "threader_eager.h" + +typedef struct { + AlgList * sols; + pthread_mutex_t * sols_mutex; +} ThreadData; + +typedef struct { + DfsArg * arg; + Solver * solver; + Threader * threader; + AlgList * starts; + AlgListNode ** node; + pthread_mutex_t * start_mutex; +} ThreadInitData; + +static void append_sol(Alg *, void *); +static void * instance_thread(void *); +static void dispatch(DfsArg *, AlgList *, Solver *, Threader *); +static AlgList * possible_starts(DfsArg *, Solver *); +static int get_nsol(void *); + +Threader threader_eager = { + .append_sol = append_sol, + .dispatch = dispatch, + .get_nsol = get_nsol, +}; + +static void +append_sol(Alg *alg, void *threaddata) +{ + ThreadData *td = (ThreadData *)threaddata; + + pthread_mutex_lock(td->sols_mutex); + append_alg(td->sols, alg); + pthread_mutex_unlock(td->sols_mutex); +} + +static AlgList * +possible_starts(DfsArg *arg, Solver *solver) +{ + AlgList *ret = new_alglist(); + + if (solver->is_solved(solver->param, arg->cubedata)) { + if (arg->opts->min_moves == 0) + append_sol(new_alg(""), arg->threaddata); + return ret; + } + + for (int i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { + Move m = solver->moveset->sorted_moves[i]; + Alg *alg = new_alg(""); + append_move(alg, m, false); + append_alg(ret, alg); + free_alg(alg); + +/* TODO: check if step not final */ + if (arg->opts->can_niss) { + alg = new_alg(""); + append_move(alg, m, true); + append_alg(ret, alg); + free_alg(alg); + } + } + + return ret; +} + +static void * +instance_thread(void *arg) +{ + ThreadInitData *tid = (ThreadInitData *)arg; + + while (true) { + pthread_mutex_lock(tid->start_mutex); + AlgListNode *node = *(tid->node); + if (node == NULL) { + pthread_mutex_unlock(tid->start_mutex); + break; + } + *(tid->node) = (*(tid->node))->next; + pthread_mutex_unlock(tid->start_mutex); + + 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); + + DfsArg newarg; + newarg.cubedata = data; + newarg.threaddata = tid->arg->threaddata; + newarg.opts = tid->arg->opts; + newarg.d = tid->arg->d; + newarg.niss = inv; + newarg.current_alg = new_alg(""); + copy_alg(node->alg, newarg.current_alg); + + dfs(&newarg, tid->solver, tid->threader); + + tid->solver->free_cubedata(tid->solver->param, data); + free_alg(newarg.current_alg); + } + + return NULL; +} + +static void +dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader) +{ + int nthreads = arg->opts->nthreads; + ThreadInitData tid[nthreads]; + pthread_t t[nthreads]; + + pthread_mutex_t *sols_mutex = malloc(sizeof(pthread_mutex_t)); + pthread_mutex_init(sols_mutex, NULL); + + arg->threaddata = malloc(sizeof(ThreadData)); + ThreadData *td = (ThreadData *)arg->threaddata; + td->sols = sols; + td->sols_mutex = sols_mutex; + + AlgList *starts = possible_starts(arg, solver); + AlgListNode *node = starts->first; + pthread_mutex_t *start_mutex = malloc(sizeof(pthread_mutex_t)); + pthread_mutex_init(start_mutex, NULL); + for (int i = 0; i < nthreads; i++) { + tid[i].arg = arg; + tid[i].solver = solver; + tid[i].threader = threader; + tid[i].starts = starts; + tid[i].node = &node; + tid[i].start_mutex = start_mutex; + + pthread_create(&t[i], NULL, instance_thread, &tid[i]); + } + + for (int i = 0; i < nthreads; i++) + pthread_join(t[i], NULL); + + free(td); + free(sols_mutex); + free_alglist(starts); + free(start_mutex); +} + +static int +get_nsol(void *threaddata) +{ + ThreadData *td = (ThreadData *)threaddata; + + pthread_mutex_lock(td->sols_mutex); + int n = td->sols->len; + pthread_mutex_unlock(td->sols_mutex); + + return n; +} diff --git a/src/threader_eager.h b/src/threader_eager.h @@ -0,0 +1,8 @@ +#ifndef THREADER_EAGER_H +#define THREADER_EAGER_H + +#include "solve.h" + +extern Threader threader_eager; + +#endif diff --git a/src/threader_single.c b/src/threader_single.c @@ -0,0 +1,35 @@ +#include "threader_single.h" + +static void append_sol(Alg *, void *); +static void dispatch(DfsArg *, AlgList *, Solver *, Threader *); +static int get_nsol(void *); + +Threader threader_single = { + .append_sol = append_sol, + .dispatch = dispatch, + .get_nsol = get_nsol, +}; + +static void +append_sol(Alg *alg, void *threaddata) +{ + append_alg((AlgList *)threaddata, alg); +} + +static void +dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader) +{ + arg->threaddata = sols; + arg->niss = false; + arg->current_alg = new_alg(""); + + dfs(arg, solver, threader); + + free_alg(arg->current_alg); +} + +static int +get_nsol(void *threaddata) +{ + return ((AlgList *)threaddata)->len; +} diff --git a/src/threader_single.h b/src/threader_single.h @@ -0,0 +1,8 @@ +#ifndef THREADER_SINGLE_H +#define THREADER_SINGLE_H + +#include "solve.h" + +extern Threader threader_single; + +#endif diff --git a/tests/alg_tests.h b/tests/alg_tests.h @@ -7,6 +7,7 @@ extern Test test_append_move; extern Test test_new_alg; /* +extern Test remove_last_move; extern Test test_compose_alg; extern Test test_inverse_alg; extern Test test_on_inverse;