commit 47a65b676d1de889706517f05659f0bb659782c9
parent a2b868261d0504c95b1091db0ce014fd567281c3
Author: enricotenuti <tenutz_27@outlook.it>
Date: Thu, 29 Aug 2024 19:07:48 +0200
nissbranch ver1
Diffstat:
| M | .gitignore | | | 1 | + |
| M | src/core/cube.h | | | 157 | ++----------------------------------------------------------------------------- |
| M | src/core/moves.h | | | 162 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/solvers/h48/solve.h | | | 83 | +++++++++++++++++++++++++++++++++---------------------------------------------- |
4 files changed, 201 insertions(+), 202 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -7,6 +7,7 @@ run
tables/*
test/*/runtest
test/run
+test/run.DSYM
run.DSYM
test/last.*
tools/results
diff --git a/src/core/cube.h b/src/core/cube.h
@@ -13,11 +13,13 @@ _static cube_t frommoves(const char *);
_static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *);
_static cube_t getcube(int64_t, int64_t, int64_t, int64_t);
-_static cube_t move(cube_t, uint8_t);
_static cube_t transform_edges(cube_t, uint8_t);
_static cube_t transform_corners(cube_t, uint8_t);
_static cube_t transform(cube_t, uint8_t);
+/* declared in moves.h */
+_static cube_t move(cube_t, uint8_t);
+
_static cube_t
cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
{
@@ -239,159 +241,6 @@ applytrans(cube_t cube, const char *buf)
return transform(cube, t);
}
-_static cube_t
-move(cube_t c, uint8_t m)
-{
- switch (m) {
- case _move_U:
- return _move(U, c);
- case _move_U2:
- return _move(U2, c);
- case _move_U3:
- return _move(U3, c);
- case _move_D:
- return _move(D, c);
- case _move_D2:
- return _move(D2, c);
- case _move_D3:
- return _move(D3, c);
- case _move_R:
- return _move(R, c);
- case _move_R2:
- return _move(R2, c);
- case _move_R3:
- return _move(R3, c);
- case _move_L:
- return _move(L, c);
- case _move_L2:
- return _move(L2, c);
- case _move_L3:
- return _move(L3, c);
- case _move_F:
- return _move(F, c);
- case _move_F2:
- return _move(F2, c);
- case _move_F3:
- return _move(F3, c);
- case _move_B:
- return _move(B, c);
- case _move_B2:
- return _move(B2, c);
- case _move_B3:
- return _move(B3, c);
- default:
- LOG("move error, unknown move\n");
- return zero;
- }
-}
-
-_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/core/moves.h b/src/core/moves.h
@@ -1,8 +1,23 @@
+/* probably these can be placed in constants file */
+#define NONISS 0x00
+#define NISS 0x01
+#define INVERSEBRANCH 0x03
+#define BRANCH 0x02
+#define ALLMOVES 0x3FFFF
+#define NOHALFTURNS 0x2DB6D
+
_static_inline bool allowednextmove(uint8_t *, uint8_t);
+_static uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t);
+
_static_inline uint8_t inverse_trans(uint8_t);
_static_inline uint8_t movebase(uint8_t);
_static_inline uint8_t moveaxis(uint8_t);
+_static cube_t move(cube_t, uint8_t);
+_static cube_t premove(cube_t, uint8_t);
+_static uint8_t inverse_move(uint8_t);
+_static uint8_t* invertpremoves(uint8_t *, uint8_t);
+
_static bool
allowednextmove(uint8_t *moves, uint8_t n)
{
@@ -28,6 +43,40 @@ allowednextmove(uint8_t *moves, uint8_t n)
return axis[1] != axis[2] || base[0] != base[2];
}
+static uint32_t
+disable_moves(uint32_t current_result, uint8_t base_index)
+{
+ return current_result & ~((1 << base_index) | (1 << (base_index + 1)) | (1 << (base_index + 2)));
+}
+
+_static uint32_t
+allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch)
+{
+ uint32_t result = ALLMOVES;
+ if (h48branch & BRANCH)
+ result &= NOHALFTURNS;
+ if (n < 1)
+ return result;
+
+ uint8_t base1 = movebase(moves[n-1]);
+ uint8_t axis1 = moveaxis(moves[n-1]);
+
+ result = disable_moves(result, base1 * 3);
+ if (base1 >= 9)
+ result = disable_moves(result, (base1 * 3) - 9);
+
+ if (n == 1)
+ return result;
+
+ uint8_t base2 = movebase(moves[n-2]);
+ uint8_t axis2 = moveaxis(moves[n-2]);
+
+ if(axis1 == axis2)
+ result = disable_moves(result, base2 * 3);
+
+ return result;
+}
+
_static_inline uint8_t
inverse_trans(uint8_t t)
{
@@ -45,3 +94,116 @@ moveaxis(uint8_t move)
{
return move / 6;
}
+
+_static cube_t
+move(cube_t c, uint8_t m)
+{
+ switch (m) {
+ case _move_U:
+ return _move(U, c);
+ case _move_U2:
+ return _move(U2, c);
+ case _move_U3:
+ return _move(U3, c);
+ case _move_D:
+ return _move(D, c);
+ case _move_D2:
+ return _move(D2, c);
+ case _move_D3:
+ return _move(D3, c);
+ case _move_R:
+ return _move(R, c);
+ case _move_R2:
+ return _move(R2, c);
+ case _move_R3:
+ return _move(R3, c);
+ case _move_L:
+ return _move(L, c);
+ case _move_L2:
+ return _move(L2, c);
+ case _move_L3:
+ return _move(L3, c);
+ case _move_F:
+ return _move(F, c);
+ case _move_F2:
+ return _move(F2, c);
+ case _move_F3:
+ return _move(F3, c);
+ case _move_B:
+ return _move(B, c);
+ case _move_B2:
+ return _move(B2, c);
+ case _move_B3:
+ return _move(B3, c);
+ default:
+ LOG("move error, unknown move\n");
+ return zero;
+ }
+}
+
+_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
+inverse_move(uint8_t m)
+{
+ return m - 2 * (m % 3) + 2;
+}
+
+_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] = inverse_move(moves[i]);
+
+ // invert elements in the array
+ for (i = 0; i < nmoves / 2; i++)
+ _swap(ret[i], ret[nmoves - i - 1]);
+ return ret;
+}
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
@@ -11,10 +11,9 @@ typedef struct {
uint32_t *cocsepdata;
uint32_t *h48data;
char **nextsol;
- bool niss;
+ uint8_t nissbranch;
int8_t npremoves;
uint8_t premoves[MAXLEN];
- int8_t totmoves;
} dfsarg_solveh48_t;
typedef struct {
@@ -65,37 +64,30 @@ _static_inline bool
solve_h48_stop(dfsarg_solveh48_t *arg)
{
uint32_t data, data_inv;
- int8_t bound, newbound;
- bool niss = false;
+ int8_t bound;
+ arg->nissbranch = NONISS;
bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
- if (bound + arg->totmoves > arg->depth)
+ if (bound + arg->nmoves + arg->npremoves > arg->depth)
return true;
- newbound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
- if (newbound + arg->totmoves > arg->depth)
+ bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
+ if (bound + arg->nmoves + arg->npremoves > arg->depth)
return true;
- if (newbound < bound) {
- bound = newbound;
- niss = true;
- }
- newbound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
+ bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
// LOG("Using pval %" PRId8 "\n", bound);
- if (newbound + arg->totmoves > arg->depth)
+ if (bound + arg->nmoves + arg->npremoves > arg->depth)
return true;
- 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)
+ if (bound + arg->nmoves + arg->npremoves == arg->depth)
+ arg->nissbranch = INVERSEBRANCH;
+
+ bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
+ if (bound + arg->nmoves + arg->npremoves > arg->depth)
return true;
- if (newbound < bound) {
- bound = newbound;
- niss = true;
- }
- arg->niss = niss;
+ if (bound + arg->nmoves + arg->npremoves == arg->depth)
+ arg->nissbranch = BRANCH;
+
return false;
}
@@ -113,7 +105,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
return 0;
if (issolved(arg->cube)) {
- if (arg->totmoves != arg->depth)
+ if (arg->nmoves + arg->npremoves != arg->depth)
return 0;
solve_h48_appendsolution(arg);
return 1;
@@ -122,34 +114,28 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
/* TODO: avoid copy, change arg and undo changes after recursion */
nextarg = *arg;
ret = 0;
- nextarg.totmoves = arg->totmoves + 1;
- if(arg->niss) {
- nextarg.npremoves = arg->npremoves + 1;
+ uint32_t allowed;
+ if(arg->nissbranch & 0x01) {
+ allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch);
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 = premove(arg->cube, m);
- nextarg.inverse = move(arg->inverse, m);
- ret += solve_h48_dfs(&nextarg);
+ if(allowed & (1 << m)) {
+ nextarg.npremoves = arg->npremoves + 1;
+ nextarg.premoves[arg->npremoves] = m;
+ nextarg.inverse = move(arg->inverse, m);
+ nextarg.cube = premove(arg->cube, m);
+ ret += solve_h48_dfs(&nextarg);
+ }
}
} else {
- nextarg.nmoves = arg->nmoves + 1;
+ allowed = allowednextmoveH48(arg->moves, arg->nmoves, arg->nissbranch);
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;
+ if (allowed & (1 << m)) {
+ nextarg.nmoves = arg->nmoves + 1;
+ nextarg.moves[arg->nmoves] = m;
+ nextarg.cube = move(arg->cube, m);
+ nextarg.inverse = premove(arg->inverse, m);
+ ret += solve_h48_dfs(&nextarg);
}
- nextarg.cube = move(arg->cube, m);
- nextarg.inverse = premove(arg->inverse, m);
- ret += solve_h48_dfs(&nextarg);
}
}
@@ -192,6 +178,7 @@ solve_h48(
LOG("Found %" PRId64 " solutions, searching at depth %"
PRId8 "\n", nsols, arg.depth);
arg.nmoves = 0;
+ arg.npremoves = 0;
solve_h48_dfs(&arg);
}
