commit 81daed66c3415827de7ab6a15c081a8f696f7a95
parent f2907e471b3caddc5844bc6994e1cbd249019747
Author: enricotenuti <tenutz_27@outlook.it>
Date: Mon, 26 Aug 2024 17:56:17 +0200
premoves and niss
Diffstat:
3 files changed, 180 insertions(+), 29 deletions(-)
diff --git 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
@@ -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
@@ -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;
-
- 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)++;
+ int strl;
+ char *solution = *arg->nextsol;
+
+ 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;
}