nissy-nx

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

commit 719080e6a88c4e17ba33a8dfec817e2d89ee666e
parent 298e9e11eda1db26fabced2e4ff14ce51c15a862
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date:   Sat, 15 Jan 2022 19:16:34 +0100

Added one adhoc test (cornerhtr from CO)

Diffstat:
Aadhoc/README | 3+++
Aadhoc/compile.sh | 15+++++++++++++++
Aadhoc/cornersdrhtr.c | 128+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aadhoc/run | 0
Mdoc/nissy.1 | 2+-
Anissy | 0
Msrc/alg.c | 42+++++++++++++++++++++++-------------------
Msrc/alg.h | 3++-
Msrc/commands.c | 8++++----
9 files changed, 176 insertions(+), 25 deletions(-)

diff --git a/adhoc/README b/adhoc/README @@ -0,0 +1,3 @@ +This folder contains some ad-hoc code that is not included in the main nissy +program. You probably don't need it, but it may be worth looking into if you +are trying to extend nissy by writing your own steps or other functions. diff --git a/adhoc/compile.sh b/adhoc/compile.sh @@ -0,0 +1,15 @@ +#/!bin/sh + +mkdir build +cd build +cp -R ../../src ./ +rm src/shell.c +cp ../$1 src/ +cp ../../Makefile ./ +make +cp nissy ../run +rm src/* +rmdir src +rm * +cd .. +rmdir build diff --git a/adhoc/cornersdrhtr.c b/adhoc/cornersdrhtr.c @@ -0,0 +1,128 @@ +#include "commands.h" + +/* Some of the following functions are new, some are copied from steps.c */ +bool +allowed(Move m) +{ + return base_move(m) == U || m == R2 || m == F2; +} + +bool +allowed_next(Move l2, Move l1, Move m) +{ + return base_move(m) != base_move(l1); +} + +bool +check_cornershtr(Cube c) +{ + return coord_cornershtr.index(c) == 0; +} + +bool +check_coud_and_dbl(Cube c) +{ + return c.coud == 0 && what_corner_at(c, DBL) == DBL; +} + +static int +estimate_cornershtr_HTM(DfsArg *arg) +{ + return ptableval(&pd_cornershtr_HTM, arg->cube); +} + +static bool +validate_singlecw_ending(Alg *alg) +{ + int i; + bool nor, inv; + Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; + + for (i = 0; i < alg->len; i++) { + if (alg->inv[i]) { + l2i = l1i; + l1i = alg->move[i]; + } else { + l2 = l1; + l1 = alg->move[i]; + } + } + + 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; +} + +int +main() +{ + Moveset moveset_UR2F2 = { + .allowed = allowed, + .allowed_next = allowed_next, + }; + + init_moveset(&moveset_UR2F2); + + /* + * This step is the same as cornershtr_HTM in steps.c, except for + * the ready() function (which is not relevant anyway, it is there + * more for testing than anything else) and the moveset. + */ + Step step = { + .final = false, + .is_done = check_cornershtr, + .estimate = estimate_cornershtr_HTM, + .ready = check_coud_and_dbl, + .is_valid = validate_singlecw_ending, + .moveset = &moveset_UR2F2, + + .pre_trans = uf, + + .tables = {&pd_cornershtr_HTM}, + .ntables = 1, + }; + + SolveOptions opts = { + .min_moves = 0, + .max_moves = 20, + .max_solutions = 1, + .nthreads = 4, + .optimal = 0, + .can_niss = false, + .verbose = false, + .all = false, + .print_number = false, + .count_only = false + }; + + init_symcoord(); + + bool cphtr_state_done[BINOM8ON4*6]; + for (unsigned long int i = 0; i < BINOM8ON4*6; i++) + cphtr_state_done[i] = false; + + for (unsigned long int i = 0; i < FACTORIAL8; i++) { + AlgList *sols; + Cube c = {0}; + c.cp = i; /* inconsistent state because of side CO */ + + if (what_corner_at(c, DBL) != DBL || + cphtr_state_done[coord_cphtr.index(c)]) + continue; + + fprintf(stderr, "Doing cp %ld (cphtr state %ld)\n", + i, coord_cphtr.index(c)); + + cphtr_state_done[coord_cphtr.index(c)] = true; + /* Comment next two lines to get non-reduced list */ + Cube mirror = apply_trans(ur_mirror, c); + cphtr_state_done[coord_cphtr.index(mirror)] = true; + + sols = solve(c, &step, &opts); + printf("%.2d\t", sols->first->alg->len); + print_alglist(sols, opts.print_number); + } + + return 0; +} diff --git a/adhoc/run b/adhoc/run Binary files differ. diff --git a/doc/nissy.1 b/doc/nissy.1 @@ -152,7 +152,7 @@ Only find solutions that require at most moves more than the optimal solution. If .Ar N is 0, this is equivalent to -.It Fl o +.Fl o . .It Fl p Plain style: do not print the number of moves. diff --git a/nissy b/nissy Binary files differ. diff --git a/src/alg.c b/src/alg.c @@ -474,32 +474,36 @@ unniss(Alg *alg) } void -init_movesets() +init_moveset(Moveset *ms) { - int i, j; + int j; uint64_t l, one; Move m, l2, l1; - Moveset *ms; one = 1; - for (i = 0; i < nmoveset; i++) { - ms = all_ms[i]; - - 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); - } + 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); } } } } + +void +init_all_movesets() +{ + int i; + + for (i = 0; i < nmoveset; i++) + init_moveset(all_ms[i]); +} diff --git a/src/alg.h b/src/alg.h @@ -35,7 +35,8 @@ void print_alglist(AlgList *al, bool l); void swapmove(Move *m1, Move *m2); void unniss(Alg *alg); -void init_movesets(); +void init_moveset(Moveset *ms); +void init_all_movesets(); #endif diff --git a/src/commands.c b/src/commands.c @@ -367,7 +367,7 @@ solve_exec(CommandArgs *args) Cube c; AlgList *sols; - init_movesets(); + init_all_movesets(); init_symcoord(); c = apply_alg(args->scramble, (Cube){0}); @@ -388,7 +388,7 @@ scramble_exec(CommandArgs *args) Alg *scr; int i; - init_movesets(); + init_all_movesets(); init_symcoord(); srand(time(NULL)); @@ -407,7 +407,7 @@ gen_exec(CommandArgs *args) int i; fprintf(stderr, "Generating coordinates...\n"); - init_movesets(); + init_all_movesets(); init_symcoord(); fprintf(stderr, "Generating pruning tables...\n"); @@ -460,7 +460,7 @@ twophase_exec(CommandArgs *args) Cube c; Alg *sol; - init_movesets(); + init_all_movesets(); init_symcoord(); c = apply_alg(args->scramble, (Cube){0});