From 975e3eafbae15b93a1a4f160dd781d359a6c717b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 26 Dec 2021 19:38:28 +0100 Subject: Added two-phase solver --- TODO.md | 2 +- doc/nissy.1 | 5 +++++ nissy | Bin 317952 -> 318160 bytes nissy.exe | Bin 782089 -> 786001 bytes src/alg.c | 67 +++++++++++++++++++++++++++++++-------------------------- src/alg.h | 1 + src/commands.c | 29 ++++++++++++++++++++++++- src/solve.c | 51 +++++++++++++++++++++++++++++++++++++++++++ src/solve.h | 1 + src/steps.c | 2 +- src/steps.h | 46 +++++++++++++++++++++++++++++++++++++++ 11 files changed, 171 insertions(+), 33 deletions(-) diff --git a/TODO.md b/TODO.md index fc5d9bb..eb8d487 100644 --- a/TODO.md +++ b/TODO.md @@ -10,7 +10,6 @@ It's more of a personal reminder than anything else. ### Commands that are available in nissy 1.0, but not in this version (yet): * drcorners (solve corners after dr) * search and improve non-optimal subsequences -* **fast non-optimal solver (also needed for scramble)** * **scramble [dr, corners only, edges only, htr, fmc(RUF)...]** * save and edit algs as "variables" (or just use a "logging system" to keep info about previously run commands, @@ -32,6 +31,7 @@ including e.g. solutions that were not shown because -c) * transform alg, rufify etc... * more scramble stuff (scramble FMC with rufify...) * command notation to list available moves +* make multi-step solve much more general and create command ## Distribution diff --git a/doc/nissy.1 b/doc/nissy.1 index 549cc4f..643674a 100644 --- a/doc/nissy.1 +++ b/doc/nissy.1 @@ -160,6 +160,11 @@ for the .Ar solve command. . +.It Nm twophase Ar scramble +Find a solution using a two-phase method. This does not guarantee +to return an optimal solution (and in fact most often it does not), +but it is very fast. +. .It Nm unniss Ar scramble Rewrite the scramble without using NISS. . diff --git a/nissy b/nissy index ce40157..c697a48 100755 Binary files a/nissy and b/nissy differ diff --git a/nissy.exe b/nissy.exe index cd521d5..9dff82b 100755 Binary files a/nissy.exe and b/nissy.exe differ diff --git a/src/alg.c b/src/alg.c index d9317ab..4c732a3 100644 --- a/src/alg.c +++ b/src/alg.c @@ -107,36 +107,6 @@ allowed_next_HTM(Move l2, Move l1, Move m) return !(p || (commute(l1, l2) && q)); } -static int -axis(Move m) -{ - if (m == NULLMOVE) - return 0; - - if (m >= U && m <= B3) - return (m-1)/6 + 1; - - if (m >= Uw && m <= Bw3) - return (m-1)/6 - 2; - - if (base_move(m) == E || base_move(m) == y) - return 1; - - if (base_move(m) == M || base_move(m) == x) - return 2; - - if (base_move(m) == S || base_move(m) == z) - return 3; - - return -1; -} - -bool -commute(Move m1, Move m2) -{ - return axis(m1) == axis(m2); -} - void append_alg(AlgList *l, Alg *alg) { @@ -166,6 +136,30 @@ append_move(Alg *alg, Move m, bool inverse) alg->len++; } +static int +axis(Move m) +{ + if (m == NULLMOVE) + return 0; + + if (m >= U && m <= B3) + return (m-1)/6 + 1; + + if (m >= Uw && m <= Bw3) + return (m-1)/6 - 2; + + if (base_move(m) == E || base_move(m) == y) + return 1; + + if (base_move(m) == M || base_move(m) == x) + return 2; + + if (base_move(m) == S || base_move(m) == z) + return 3; + + return -1; +} + Move base_move(Move m) { @@ -175,6 +169,12 @@ base_move(Move m) return m - (m-1)%3; } +bool +commute(Move m1, Move m2) +{ + return axis(m1) == axis(m2); +} + void compose_alg(Alg *alg1, Alg *alg2) { @@ -184,6 +184,13 @@ compose_alg(Alg *alg1, Alg *alg2) append_move(alg1, alg2->move[i], alg2->inv[i]); } +void +copy_alg(Alg *src, Alg *dst) +{ + dst->len = 0; /* Overwrites */ + compose_alg(dst, src); +} + void free_alg(Alg *alg) { diff --git a/src/alg.h b/src/alg.h index e046526..ea95a9c 100644 --- a/src/alg.h +++ b/src/alg.h @@ -19,6 +19,7 @@ void append_move(Alg *alg, Move m, bool inverse); Move base_move(Move m); void compose_alg(Alg *alg1, Alg *alg2); bool commute(Move m1, Move m2); +void copy_alg(Alg *src, Alg *dst); void free_alg(Alg *alg); void free_alglist(AlgList *l); Alg * inverse_alg(Alg *alg); diff --git a/src/commands.c b/src/commands.c index 56ff944..02af19f 100644 --- a/src/commands.c +++ b/src/commands.c @@ -2,12 +2,12 @@ /* Arg parsing functions *****************************************************/ -CommandArgs * solve_parse_args(int c, char **v); CommandArgs * gen_parse_args(int c, char **v); CommandArgs * help_parse_args(int c, char **v); CommandArgs * print_parse_args(int c, char **v); CommandArgs * parse_only_scramble(int c, char **v); CommandArgs * parse_no_arg(int c, char **v); +CommandArgs * solve_parse_args(int c, char **v); /* Exec functions ************************************************************/ @@ -17,6 +17,7 @@ static void solve_exec(CommandArgs *args); static void steps_exec(CommandArgs *args); static void commands_exec(CommandArgs *args); static void print_exec(CommandArgs *args); +static void twophase_exec(CommandArgs *args); static void help_exec(CommandArgs *args); static void quit_exec(CommandArgs *args); static void unniss_exec(CommandArgs *args); @@ -92,6 +93,15 @@ help_cmd = { .exec = help_exec, }; +Command +twophase_cmd = { + .name = "twophase", + .usage = "twophase", + .description = "Find a solution quickly using a 2-phase method", + .parse_args = parse_only_scramble, + .exec = twophase_exec, +}; + Command quit_cmd = { .name = "quit", @@ -128,6 +138,7 @@ Command *commands[NCOMMANDS] = { &quit_cmd, &solve_cmd, &steps_cmd, + &twophase_cmd, &unniss_cmd, &version_cmd, }; @@ -383,6 +394,22 @@ print_exec(CommandArgs *args) print_cube(apply_alg(args->scramble, (Cube){0})); } +static void +twophase_exec(CommandArgs *args) +{ + Cube c; + Alg *sol; + + init_movesets(); + init_symcoord(); + + c = apply_alg(args->scramble, (Cube){0}); + sol = solve_2phase(c, 1); + + print_alg(sol, false); + free_alg(sol); +} + static void help_exec(CommandArgs *args) { diff --git a/src/solve.c b/src/solve.c index 5a72bba..cfb2bd3 100644 --- a/src/solve.c +++ b/src/solve.c @@ -438,3 +438,54 @@ solve(Cube cube, Step *step, SolveOptions *opts) return sols; } + +/* TODO: make more general! */ +Alg * +solve_2phase(Cube cube, int nthreads) +{ + int bestlen, newb; + Alg *bestalg; + AlgList *sols1, *sols2; + AlgListNode *i; + Cube c; + SolveOptions opts1, opts2; + + opts1.min_moves = 0; + opts1.max_moves = 13; + opts1.max_solutions = 100; + 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; + + sols1 = solve(cube, &drany_HTM, &opts1); + bestalg = new_alg(""); + bestlen = 999; + for (i = sols1->first; i != NULL; i = i->next) { + c = apply_alg(i->alg, cube); + 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); + + return bestalg; +} diff --git a/src/solve.h b/src/solve.h index 668cd9a..6ce6609 100644 --- a/src/solve.h +++ b/src/solve.h @@ -6,5 +6,6 @@ #include "trans.h" AlgList * solve(Cube cube, Step *step, SolveOptions *opts); +Alg * solve_2phase(Cube cube, int nthreads); #endif diff --git a/src/steps.c b/src/steps.c index 98e26b5..5de3206 100644 --- a/src/steps.c +++ b/src/steps.c @@ -1437,7 +1437,7 @@ static int detect_pretrans_drud(Cube cube, Trans *ret) { int i, n; - static Trans tt[3] = {uf, ur, fd}; + static Trans tt[3] = {uf, fr, rd}; for (i = 0, n = 0; i < 3; i++) if (check_drud(apply_trans(tt[i], cube))) diff --git a/src/steps.h b/src/steps.h index 5744e48..53f8e1b 100644 --- a/src/steps.h +++ b/src/steps.h @@ -7,6 +7,52 @@ extern Step * steps[NSTEPS]; +extern Step optimal_HTM; +extern Step optimal_light_HTM; +extern Step eofin_eo; +extern Step eofbfin_eofb; +extern Step eorlfin_eorl; +extern Step eoudfin_eoud; +extern Step eoany_HTM; +extern Step eofb_HTM; +extern Step eorl_HTM; +extern Step eoud_HTM; +extern Step coany_HTM; +extern Step coud_HTM; +extern Step corl_HTM; +extern Step cofb_HTM; +extern Step coany_URF; +extern Step coud_URF; +extern Step corl_URF; +extern Step cofb_URF; +extern Step drany_HTM; +extern Step drud_HTM; +extern Step drrl_HTM; +extern Step drfb_HTM; +extern Step dr_eo; +extern Step dr_eofb; +extern Step dr_eorl; +extern Step dr_eoud; +extern Step drud_eofb; +extern Step drrl_eofb; +extern Step drud_eorl; +extern Step drfb_eorl; +extern Step drfb_eoud; +extern Step drrl_eoud; +extern Step dranyfin_DR; +extern Step drudfin_drud; +extern Step drrlfin_drrl; +extern Step drfbfin_drfb; +extern Step htr_any; +extern Step htr_drud; +extern Step htr_drrl; +extern Step htr_drfb; +extern Step htrfin_htr; +extern Step cornershtr_HTM; +extern Step cornershtr_URF; +extern Step corners_HTM; +extern Step corners_URF; + void copy_estimatedata(EstimateData *s, EstimateData *d); void invert_estimatedata(EstimateData *ed); void reset_estimatedata(EstimateData *ed); -- cgit v1.3