Solve bug related to duplicate solutions

7 files changed, 62 insertions, 48 deletions

diff --git a/src/core/io_trans.h b/src/core/io_trans.h
index f0db095..71b2287 100644
--- a/src/core/io_trans.h
+++ b/src/core/io_trans.h
@@ -6,7 +6,7 @@ readtrans(const char buf[static NISSY_SIZE_TRANSFORMATION])
 {
         uint8_t t;
 
-        for (t = 0; t < 48; t++)
+        for (t = 0; t < NTRANS; t++)
                 if (!strncmp(buf, transstr[t], 11))
                         return t;
 
diff --git a/src/core/moves.h b/src/core/moves.h
index 7d4972e..037944b 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -61,7 +61,7 @@ allowednextmove_mask(uint8_t *moves, uint8_t n)
                 result = disable_moves(result, (base1 - 1) * 3);
 
         if (n == 1)
-        return result;
+                return result;
 
         base2 = movebase(moves[n-2]);
         axis2 = moveaxis(moves[n-2]);
diff --git a/src/core/transform.h b/src/core/transform.h
index f956718..a6bb937 100644
--- a/src/core/transform.h
+++ b/src/core/transform.h
@@ -387,7 +387,7 @@ symmetry_mask(cube_t cube)
         uint64_t t, ret;
         cube_t transformed;
 
-        for (t = 0, ret = 0; t < 48; t++) {
+        for (t = 0, ret = 0; t < NTRANS; t++) {
                 transformed = transform(cube, t);
                 ret |= ((uint64_t)equal(cube, transformed)) << t;
         }
diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h
index 291ae48..3812a4a 100644
--- a/src/solvers/h48/gendata_cocsep.h
+++ b/src/solvers/h48/gendata_cocsep.h
@@ -101,7 +101,7 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg)
 
                 if (arg->rep != NULL)
                         arg->rep[*arg->n] = arg->cube;
-                for (t = 0, cc = 0; t < 48; t++) {
+                for (t = 0, cc = 0; t < NTRANS; t++) {
                         d = transform_corners(arg->cube, t);
                         j = coord_cocsep(d);
                         if (i == j && arg->selfsim != NULL)
diff --git a/src/solvers/h48/gendata_eoesep.h b/src/solvers/h48/gendata_eoesep.h
index d3b73ea..23fbb3c 100644
--- a/src/solvers/h48/gendata_eoesep.h
+++ b/src/solvers/h48/gendata_eoesep.h
@@ -50,7 +50,7 @@ gendata_esep_classes(
                 if (visited[i])
                         continue;
                 c = invcoord_esep(i);
-                for (t = 0; t < 48; t++) {
+                for (t = 0; t < NTRANS; t++) {
                         j = coord_esep(transform(c, t));
                         cl = class << UINT32_C(16);
                         ti = inverse_trans(t) << UINT32_C(8);
@@ -206,7 +206,7 @@ gendata_eoesep_marksim(
         c = invcoord_eoesep(i);
         for (m = 0; m < 18; m++) {
                 moved = move(c, m);
-                for (t = 0; t < 48; t++) {
+                for (t = 0; t < NTRANS; t++) {
                         transformed = transform(moved, t);
                         coord = coord_eoesep_sym(transformed, esep_classes);
                         pval = get_eoesep_pval(buf8, coord);
@@ -232,7 +232,7 @@ gendata_eoesep_next(
         int64_t coord;
         cube_t moved, transformed;
 
-        for (t = 0; t < 48; t++) {
+        for (t = 0; t < NTRANS; t++) {
                 transformed = transform(c, t);
                 for (m = 0; m < 18; m++) {
                         moved = move(transformed, m);
diff --git a/src/solvers/h48/gendata_types_macros.h b/src/solvers/h48/gendata_types_macros.h
index d7c88af..a2026b2 100644
--- a/src/solvers/h48/gendata_types_macros.h
+++ b/src/solvers/h48/gendata_types_macros.h
@@ -43,7 +43,7 @@ _t by _ttrep).
         int64_t VAR_COCLASS = COCLASS(ARG_COCSEPDATA[VAR_COCSEP]); \
         cube_t VAR_REP = transform(ARG_CUBE, VAR_TTREP); \
         uint64_t VAR_S = ARG_SELFSIM[VAR_COCLASS]; \
-        for (uint8_t VAR_T = 0; VAR_T < 48 && VAR_S; VAR_T++, VAR_S >>= 1) { \
+        for (uint8_t VAR_T = 0; VAR_T < NTRANS && VAR_S; VAR_T++, VAR_S >>= 1) { \
                 if (!(VAR_S & 1)) continue; \
                 ARG_CUBE = transform(VAR_REP, VAR_T); \
                 ARG_CUBE = transform(ARG_CUBE, VAR_INVERSE_TTREP); \
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 1ca294a..d168985 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -57,8 +57,7 @@ typedef struct {
 } dfsarg_solve_h48_maketasks_t;
 
 STATIC int64_t solve_h48_appendsolution(dfsarg_solve_h48_t *);
-STATIC bool solve_h48_appendmoves(dfsarg_solve_h48_t *, int8_t,
-    uint8_t *, uint8_t);
+STATIC int64_t solve_h48_appendallsym(dfsarg_solve_h48_t *);
 STATIC bool solve_h48_appendchar(dfsarg_solve_h48_t *, char);
 STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *);
 STATIC int64_t solve_h48_maketasks(
@@ -73,15 +72,10 @@ STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, int8_t, int8_t,
 STATIC int64_t
 solve_h48_appendsolution(dfsarg_solve_h48_t *arg)
 {
-        uint8_t t;
-        int64_t ret;
-        uint64_t solstart;
-
         if (*arg->nsols >= arg->maxsolutions ||
             arg->nmoves + arg->npremoves > *arg->shortest_sol + arg->optimal)
                 return 0;
 
-        solstart = *arg->solutions_used;
         invertmoves(arg->premoves, arg->npremoves, arg->moves + arg->nmoves);
 
         /* Do not append the solution in case premoves cancel with normal */
@@ -90,18 +84,63 @@ solve_h48_appendsolution(dfsarg_solve_h48_t *arg)
         if (arg->npremoves > 1 && !allowednextmove(arg->moves, arg->nmoves+2))
                 return 0;
 
-        for (t = 0, ret = 0; t < 48 && *arg->nsols < arg->maxsolutions; t++) {
+        return solve_h48_appendallsym(arg);
+}
+
+STATIC int64_t
+solve_h48_appendallsym(dfsarg_solve_h48_t *arg)
+{
+        bool eq;
+        uint8_t t, i, j, k, n;
+        int64_t ret, strl, l;
+        char *m;
+        uint8_t all[NTRANS][MAXLEN];
+
+        n = arg->nmoves + arg->npremoves;
+
+        for (t = 0, j = 0; t < NTRANS; t++) {
                 if (!(arg->symmask0 & (UINT64_C(1) << (uint64_t)t)))
                         continue;
 
-                if (!solve_h48_appendmoves(arg, arg->nmoves + arg->npremoves,
-                    arg->moves, t))
-                        goto solve_h48_appendsolution_error;
+                for (i = 0; i < n; i++)
+                        all[j][i] = transform_move(arg->moves[i], t);
+
+                /* Sort parallel moves for consistency */
+                for (i = 0; i < n - 1; i++)
+                        if (moveaxis(all[j][i]) == moveaxis(all[j][i+1]) &&
+                            movebase(all[j][i]) == movebase(all[j][i+1]) + 1)
+                                SWAP(all[j][i], all[j][i+1]);
+
+                /* Check for duplicate solutions */
+                for (k = 0; k < j; k++) {
+                        eq = true;
+                        for (i = 0; i < n; i++)
+                                if (all[k][i] != all[j][i])
+                                        eq = false;
+                        /* If a solution was already found, we skip it */
+                        if (eq)
+                                continue;
+                }
+
+                /* If all is good, the solution is accepted */
+                j++;
+        }
+
+        /* The solutions are appended */
+        for (k = 0; k < j && *arg->nsols < arg->maxsolutions; k++) {
+                l = arg->solutions_size - *arg->solutions_used;
+                m = *arg->solutions + *arg->solutions_used;
+                strl = writemoves(all[k], n, l, m);
+                if (strl < 0)
+                        goto solve_h48_appendallsym_error;
 
-                LOG("Solution found: %s\n", *arg->solutions + solstart);
+                LOG("Solution found: %s\n", m);
+
+                *arg->solutions_used += MAX(0, strl-1);
 
                 if (!solve_h48_appendchar(arg, '\n'))
-                        goto solve_h48_appendsolution_error;
+                        goto solve_h48_appendallsym_error;
+
                 (*arg->nsols)++;
                 *arg->shortest_sol =
                     MIN(*arg->shortest_sol, arg->nmoves + arg->npremoves);
@@ -110,37 +149,12 @@ solve_h48_appendsolution(dfsarg_solve_h48_t *arg)
 
         return ret;
 
-solve_h48_appendsolution_error:
+solve_h48_appendallsym_error:
         LOG("Could not append solution to buffer: size too small\n");
         return NISSY_ERROR_BUFFER_SIZE;
 }
 
 STATIC bool
-solve_h48_appendmoves(
-        dfsarg_solve_h48_t *arg,
-        int8_t n,
-        uint8_t *moves,
-        uint8_t t
-)
-{
-        int i;
-        int64_t strl;
-        uint8_t mm[MAXLEN];
-
-        for (i = 0; i < n; i++)
-                mm[i] = transform_move(moves[i], t);
-
-        strl = writemoves(mm, n, arg->solutions_size - *arg->solutions_used,
-            *arg->solutions + *arg->solutions_used);
-
-        if (strl < 0)
-                return false;
-
-        *arg->solutions_used += MAX(0, strl-1);
-        return true;
-}
-
-STATIC bool
 solve_h48_appendchar(dfsarg_solve_h48_t *arg, char c)
 {
         if (arg->solutions_size <= *arg->solutions_used)
@@ -397,7 +411,7 @@ solve_h48_maketasks(
 
                 /* Avoid symmetry-equivalent moves from the starting cube */
                 if (maketasks_arg->nmoves == 1)
-                        for (t = 0; t < 48; t++)
+                        for (t = 0; t < NTRANS; t++)
                                 if (solve_arg->symmask0 &
                                     (UINT64_C(1) << (uint64_t)t))
                                         mm &= ~(UINT32_C(1) <<