premoves and niss

3 files changed, 179 insertions, 28 deletions

diff --git a/.gitignore b/.gitignore
index 5fb5b1f..236d875 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,7 +7,7 @@ run
 tables/*
 test/*/runtest
 test/run
-test/run.DSYM
+run.DSYM
 test/last.*
 tools/results
 .vscode
diff --git a/src/core/cube.h b/src/core/cube.h
index fe36f90..b24fb5c 100644
--- a/src/core/cube.h
+++ b/src/core/cube.h
@@ -285,6 +285,113 @@ move(cube_t c, uint8_t m)
         }
 }
 
+_static cube_t
+premove(cube_t c, uint8_t m){
+                switch (m) {
+        case _move_U:
+                return _premove(U3, c);
+        case _move_U2:
+                return _premove(U2, c);
+        case _move_U3:
+                return _premove(U, c);
+        case _move_D:
+                return _premove(D3, c);
+        case _move_D2:
+                return _premove(D2, c);
+        case _move_D3:
+                return _premove(D, c);
+        case _move_R:
+                return _premove(R3, c);
+        case _move_R2:
+                return _premove(R2, c);
+        case _move_R3:
+                return _premove(R, c);
+        case _move_L:
+                return _premove(L3, c);
+        case _move_L2:
+                return _premove(L2, c);
+        case _move_L3:
+                return _premove(L, c);
+        case _move_F:
+                return _premove(F3, c);
+        case _move_F2:
+                return _premove(F2, c);
+        case _move_F3:
+                return _premove(F, c);
+        case _move_B:
+                return _premove(B3, c);
+        case _move_B2:
+                return _premove(B2, c);
+        case _move_B3:
+                return _premove(B, c);
+        default:
+                LOG("move error, unknown move\n");
+                return zero;
+        }
+}
+_static uint8_t
+invertmove(uint8_t m)
+{
+        switch (m) {
+        case _move_U:
+                return _move_U3;
+        case _move_U2:
+                return _move_U2;
+        case _move_U3:
+                return _move_U;
+        case _move_D:
+                return _move_D3;
+        case _move_D2:
+                return _move_D2;
+        case _move_D3:
+                return _move_D;
+        case _move_R:
+                return _move_R3;
+        case _move_R2:
+                return _move_R2;
+        case _move_R3:
+                return _move_R;
+        case _move_L:
+                return _move_L3;
+        case _move_L2:
+                return _move_L2;
+        case _move_L3:
+                return _move_L;
+        case _move_F:
+                return _move_F3;
+        case _move_F2:
+                return _move_F2;
+        case _move_F3:
+                return _move_F;
+        case _move_B:
+                return _move_B3;
+        case _move_B2:
+                return _move_B2;
+        case _move_B3:
+                return _move_B;
+        default:
+                LOG("invertmove error, unknown move\n");
+                return _error;
+        }
+}
+
+_static uint8_t*
+invertpremoves(uint8_t *moves, uint8_t nmoves)
+{
+        uint8_t i;
+        uint8_t *ret = malloc(nmoves * sizeof(uint8_t));
+
+        for (i = 0; i < nmoves; i++)
+                ret[i] = invertmove(moves[i]);
+
+        // invert elements in the array
+        for (i = 0; i < nmoves / 2; i++)
+                _swap(ret[i], ret[nmoves - i - 1]);
+        return ret;
+}
+
+
+
 /*
 TODO transform is now relegated to a separated file because it is too long.
 It would be nice to make it shorter without loosing performance.
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 0843792..7430228 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -11,6 +11,10 @@ typedef struct {
         uint32_t *cocsepdata;
         uint32_t *h48data;
         char **nextsol;
+        bool niss;
+        int8_t npremoves;
+        uint8_t premoves[MAXLEN];
+        int8_t totmoves;
 } dfsarg_solveh48_t;
 
 typedef struct {
@@ -35,41 +39,63 @@ _static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
 _static void
 solve_h48_appendsolution(dfsarg_solveh48_t *arg)
 {
-        int strl;
+    int strl;
+    char *solution = *arg->nextsol; 
 
-        strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
-        LOG("Solution found: %s\n", *arg->nextsol);
-        *arg->nextsol += strl;
-        **arg->nextsol = '\n';
-        (*arg->nextsol)++;
-        (*arg->nsols)++;
+    strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
+    *arg->nextsol += strl; 
+
+    if (arg->npremoves) {
+        **arg->nextsol = ' ';
+        (*arg->nextsol)++;
+
+                uint8_t* invertedpremoves = invertpremoves(arg->premoves, arg->npremoves);
+        strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol);
+                free(invertedpremoves);
+        *arg->nextsol += strl;
+    }
+    LOG("Solution found: %s\n", solution);
+
+    **arg->nextsol = '\n';
+    (*arg->nextsol)++;
+    (*arg->nsols)++;
 }
 
 _static_inline bool
 solve_h48_stop(dfsarg_solveh48_t *arg)
 {
         uint32_t data, data_inv;
-        int8_t bound;
+        int8_t bound, newbound;
+        bool niss = false;
 
         bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
-        if (bound + arg->nmoves > arg->depth)
+        if (bound + arg->totmoves > arg->depth)
                 return true;
 
-        bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
-        if (bound + arg->nmoves > arg->depth)
+        newbound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
+        if (newbound + arg->totmoves > arg->depth)
                 return true;
+        if (newbound < bound) {
+                bound = newbound;
+                niss = true;
+        }
 
-/*
-        bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
-LOG("Using pval %" PRId8 "\n", bound);
-        if (bound + arg->nmoves > arg->depth)
+        newbound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
+        // LOG("Using pval %" PRId8 "\n", bound);
+        if (newbound + arg->totmoves > arg->depth)
                 return true;
-
-        bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
-        if (bound + arg->nmoves > arg->depth)
+        if (newbound < bound) {
+                bound = newbound;
+                niss = false;
+        }
+        newbound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
+        if (newbound + arg->totmoves > arg->depth)
                 return true;
-*/
-
+        if (newbound < bound) {
+                bound = newbound;
+                niss = true;
+        }
+        arg->niss = niss;
         return false;
 }
 
@@ -87,7 +113,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
                 return 0;
 
         if (issolved(arg->cube)) {
-                if (arg->nmoves != arg->depth)
+                if (arg->totmoves != arg->depth)
                         return 0;
                 solve_h48_appendsolution(arg);
                 return 1;
@@ -95,21 +121,39 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
 
         /* TODO: avoid copy, change arg and undo changes after recursion */
         nextarg = *arg;
-        nextarg.nmoves = arg->nmoves + 1;
         ret = 0;
-        for (m = 0; m < 18; m++) {
-                nextarg.moves[arg->nmoves] = m;
-                if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
+        nextarg.totmoves = arg->totmoves + 1;
+        if(arg->niss) {
+                nextarg.npremoves = arg->npremoves + 1;
+                for (m = 0; m < 18; m++) {
+                        nextarg.premoves[arg->npremoves] = m;
+                if (!allowednextmove(nextarg.premoves, nextarg.npremoves)) {
                         /* If a move is not allowed, neither are its 180
                          * and 270 degree variations */
                         m += 2;
                         continue;
                 }
-                nextarg.cube = move(arg->cube, m);
-                nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */
+                nextarg.cube = premove(arg->cube, m);
+                nextarg.inverse = move(arg->inverse, m);
                 ret += solve_h48_dfs(&nextarg);
+                }
+        } else {
+                nextarg.nmoves = arg->nmoves + 1;
+                for (m = 0; m < 18; m++) {
+                        nextarg.moves[arg->nmoves] = m;
+                        if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
+                                /* If a move is not allowed, neither are its 180
+                                * and 270 degree variations */
+                                m += 2;
+                                continue;
+                        }
+                        nextarg.cube = move(arg->cube, m);
+                        nextarg.inverse = premove(arg->inverse, m);
+                        ret += solve_h48_dfs(&nextarg);
+                }
         }
 
+
         return ret;
 }