commit cb800102a14fb6923546b9d036dbf4e6a5b7542a
parent d2eb169c675101a64fb873a289fad1d4fe70c5e5
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sun, 15 Dec 2024 10:50:00 +0100
Solve bug related to duplicate solutions
Diffstat:
7 files changed, 62 insertions(+), 48 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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", m);
- LOG("Solution found: %s\n", *arg->solutions + solstart);
+ *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) <<
