nissy-nx

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

commit e18f8e4eefadd733d985e99e2710111afa5a710a
parent def25ea64b097d2a994eb33c91dc66248233afec
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date:   Tue, 15 Mar 2022 15:54:39 +0100

Prepare for big changes in coordinates

Diffstat:
MTODO.md | 31+++++++++++++++----------------
Mnissy | 0
Msrc/cubetypes.h | 6+++++-
Msrc/moves.c | 22+++++++++++-----------
Msrc/moves.h | 15+++++++++++++++
Msrc/pruning.c | 4++--
Msrc/symcoord.c | 32++++++++++++++++----------------
Msrc/trans.h | 2+-
8 files changed, 65 insertions(+), 47 deletions(-)

diff --git a/TODO.md b/TODO.md @@ -4,11 +4,19 @@ This is a list of things that I would like to add or change at some point. It's more of a personal reminder than anything else. ## For version 2.1 -### Installation +### Moving coordinates * Implement coord->move to apply moves directly on coordinates - (can this be used to improve solving speed? Applying moves on - three coordinates is better than applying a move on a Cube and - then transforming it, but I still need to work with inverses...) +* add transformer to transform coordinate (optional, only for sym coordinates) +* For each coordinate, manually disallow "bad" moves, or just ignore the error + (probably better to check: low performance cost, detect problems that I might + be overlooking) +* remove selsims, do this directly inside transfinder +* change genptable where needed +* Remove coord->cube (and edit README.md accordingly) +* Remove sym_data->rep (but keep transtorep)? +* Use this to improve solver: add 2 or 3 helper coordinates to optimal solver, + to avoid transforming every time. We still need to transform when checking + inverse scramble, though. ### Documentation * Write an examples.md file * More screenshots! @@ -44,14 +52,13 @@ including e.g. solutions that were not shown because -c) (graphical: maybe there is a cubing.js function; command line: ???) ## Distribution - -* Add EXAMPLES.md file * webapp (cgi) -* installation: get ptables with curl or similar (on Windows what?) - also, keep only one compressed format (+uncompressed?) on server ## Technical stuff +### Testing +* write some proper tests, move test_coord to the testing module(s) + ### Memory management * free pruning table after solve is done? if I do this I need to deafault to a small table for < 8 moves solutions or smth @@ -65,14 +72,6 @@ including e.g. solutions that were not shown because -c) * Check if memory is enough for loading pruning tables; if not, abort * For optimal solver: choose largest that fits in memory between nxopt and light -### Other optimal solvers -* try htr corners + edges in slice but not oriented (300Mb table); - de Bondt's trick does not work, but I can use full symmetry and - take advantage of the fact that it is a subset invariant under half-turns - (like in light optimal solver) -* Another idea: DR + cornershtr (5Gb table); same as above, de Bondt's trick - does not work but I can use half-turn trick - ### Structural changes * client/server architecture: run a server process in the background so that multiple client processess can send it queries and get results; this would diff --git a/nissy b/nissy Binary files differ. diff --git a/src/cubetypes.h b/src/cubetypes.h @@ -95,6 +95,8 @@ typedef struct threaddatagenpt ThreadDataGenpt; typedef Cube (*AntiIndexer) (uint64_t); typedef bool (*Checker) (Cube); +typedef uint64_t (*CoordMover) (Move, uint64_t); +typedef uint64_t (*CoordTransformer) (Trans, uint64_t); typedef int (*Estimator) (DfsArg *); typedef bool (*Validator) (Alg *); typedef void (*Exec) (CommandArgs *); @@ -168,7 +170,9 @@ coordinate Indexer index; AntiIndexer cube; uint64_t max; - TransFinder trans; + TransFinder transfind; + CoordMover move; + CoordTransformer transform; }; struct diff --git a/src/moves.c b/src/moves.c @@ -138,17 +138,17 @@ static char equiv_alg_string[100][NMOVES] = { }; /* Transition tables, to be loaded up at the beginning */ -static int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; -static int eofb_mtable[NMOVES][POW2TO11]; -static int eorl_mtable[NMOVES][POW2TO11]; -static int eoud_mtable[NMOVES][POW2TO11]; -static int cp_mtable[NMOVES][FACTORIAL8]; -static int coud_mtable[NMOVES][POW3TO7]; -static int cofb_mtable[NMOVES][POW3TO7]; -static int corl_mtable[NMOVES][POW3TO7]; -static int cpos_mtable[NMOVES][FACTORIAL6]; +int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +int eofb_mtable[NMOVES][POW2TO11]; +int eorl_mtable[NMOVES][POW2TO11]; +int eoud_mtable[NMOVES][POW2TO11]; +int cp_mtable[NMOVES][FACTORIAL8]; +int coud_mtable[NMOVES][POW3TO7]; +int cofb_mtable[NMOVES][POW3TO7]; +int corl_mtable[NMOVES][POW3TO7]; +int cpos_mtable[NMOVES][FACTORIAL6]; /* Local functions implementation ********************************************/ diff --git a/src/moves.h b/src/moves.h @@ -5,6 +5,21 @@ #include "cube.h" #include "env.h" +/* + * Tables are exposed to allow for faster moves in some cases. + */ +extern int epose_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +extern int eposs_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +extern int eposm_mtable[NMOVES][FACTORIAL12/FACTORIAL8]; +extern int eofb_mtable[NMOVES][POW2TO11]; +extern int eorl_mtable[NMOVES][POW2TO11]; +extern int eoud_mtable[NMOVES][POW2TO11]; +extern int cp_mtable[NMOVES][FACTORIAL8]; +extern int coud_mtable[NMOVES][POW3TO7]; +extern int cofb_mtable[NMOVES][POW3TO7]; +extern int corl_mtable[NMOVES][POW3TO7]; +extern int cpos_mtable[NMOVES][FACTORIAL6]; + Cube apply_alg(Alg *alg, Cube cube); Cube apply_alg_generic(Alg *alg, Cube c, PieceFilter f, bool a); Cube apply_move(Move m, Cube cube); diff --git a/src/pruning.c b/src/pruning.c @@ -263,12 +263,12 @@ genptable_fixnasty(PruneData *pd, int d) Cube c, cc; Trans t[NTRANS]; - if (pd->coord->trans == NULL) + if (pd->coord->transfind == NULL) return; for (i = 0; i < pd->coord->max; i++) { if (ptableval_index(pd, i) == d) { - n = pd->coord->trans(i, t); + n = pd->coord->transfind(i, t); if (n == 1) continue; diff --git a/src/symcoord.c b/src/symcoord.c @@ -64,38 +64,38 @@ SymData * all_sd[] = { Coordinate coord_eofbepos_sym16 = { - .index = index_eofbepos_sym16, - .cube = antindex_eofbepos_sym16, + .index = index_eofbepos_sym16, + .cube = antindex_eofbepos_sym16, }; Coordinate coord_cp_sym16 = { - .index = index_cp_sym16, - .cube = antindex_cp_sym16, + .index = index_cp_sym16, + .cube = antindex_cp_sym16, }; Coordinate coord_drud_sym16 = { - .index = index_drud_sym16, - .cube = antindex_drud_sym16, - .max = POW3TO7 * CLASSES_EOFBEPOS_16, - .trans = transfinder_drud_sym16, + .index = index_drud_sym16, + .cube = antindex_drud_sym16, + .max = POW3TO7 * CLASSES_EOFBEPOS_16, + .transfind = transfinder_drud_sym16, }; Coordinate coord_drudfin_noE_sym16 = { - .index = index_drudfin_noE_sym16, - .cube = antindex_drudfin_noE_sym16, - .max = FACTORIAL8 * CLASSES_CP_16, - .trans = transfinder_drudfin_noE_sym16, + .index = index_drudfin_noE_sym16, + .cube = antindex_drudfin_noE_sym16, + .max = FACTORIAL8 * CLASSES_CP_16, + .transfind = transfinder_drudfin_noE_sym16, }; Coordinate coord_nxopt31 = { - .index = index_nxopt31, - .cube = antindex_nxopt31, - .max = POW3TO7 * BINOM8ON4 * CLASSES_EOFBEPOS_16 , - .trans = transfinder_nxopt31, + .index = index_nxopt31, + .cube = antindex_nxopt31, + .max = POW3TO7 * BINOM8ON4 * CLASSES_EOFBEPOS_16, + .transfind = transfinder_nxopt31, }; /* Functions *****************************************************************/ diff --git a/src/trans.h b/src/trans.h @@ -4,7 +4,7 @@ #include "moves.h" /* - * Tables are exposed to allow faster partial transofrmations in some + * Tables are exposed to allow faster partial transformations in some * specific cases (in symcoord) */ extern int epose_ttable[NTRANS][FACTORIAL12/FACTORIAL8];