commit 7b48583d629d33971e9f1d5e7aa4ca7f11d8a032
parent d1aaa9264089fa64a98eecef09aa4a5d9773e345
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Nov 2023 22:59:21 +0100
Started working on solve
Diffstat:
5 files changed, 97 insertions(+), 29 deletions(-)
diff --git a/README.md b/README.md
@@ -37,6 +37,12 @@ for benchmarks.
## TODO:
+### Simple solver
+
+* tests
+* finish implementation
+* benchmarks
+
### Coordinates
* [done] eo
@@ -55,8 +61,10 @@ All solving functions take a cube and some parameters as input.
* Depth [uint, <= 20]: all solvers work at fixed depth. The caller
implementation can implement an A* search.
-* Full [bool]: if false, stop at first solution found, otherwise
- find all solutions at that depth.
+* max [int]: the maximum number of solutions to find. Set to a negative
+ value for all solutions.
+* sol [move_t *]: the array for returning the solutions. The caller
+ should make sure that it can hold at least max * depth values.
* Table [uint8_t *]: table with all the necessare pre-computed info.
The table can be generated with a companion function, but reading
from and writing to file is delegated to the caller implementation.
diff --git a/benchmark/bench.sh b/benchmark/bench.sh
@@ -1,6 +1,6 @@
#!/bin/sh
-CC="cc -std=c99 -pthread -O3 -D$CUBETYPE"
+CC="cc -std=c99 -O3 -D$CUBETYPE"
if [ "$CUBETYPE" = "CUBE_AVX2" ]; then
CC="$CC -mavx2"
fi
diff --git a/cube.c b/cube.c
@@ -2129,33 +2129,33 @@ in the previous section(s) for unsupported architectures.
#else
#define PERM4(r, i, j, k, l) \
- aux = r[i]; \
- r[i] = r[l]; \
- r[l] = r[k]; \
- r[k] = r[j]; \
- r[j] = aux;
+ aux = r[i]; \
+ r[i] = r[l]; \
+ r[l] = r[k]; \
+ r[k] = r[j]; \
+ r[j] = aux;
#define PERM22(r, i, j, k, l) \
- aux = r[i]; \
- r[i] = r[j]; \
- r[j] = aux; \
- aux = r[k]; \
- r[k] = r[l]; \
- r[l] = aux;
-#define CO(a, b) \
- aux = (a & _cobits) + (b & _cobits); \
- auy = (aux + _ctwist_cw) >> 2U; \
- auz = (aux + auy) & _cobits2; \
- a = (a & _pbits) | auz;
-#define CO4(r, i, j, k, l) \
- CO(r[i], _ctwist_cw) \
- CO(r[j], _ctwist_cw) \
- CO(r[k], _ctwist_ccw) \
- CO(r[l], _ctwist_ccw)
+ aux = r[i]; \
+ r[i] = r[j]; \
+ r[j] = aux; \
+ aux = r[k]; \
+ r[k] = r[l]; \
+ r[l] = aux;
+#define CO(a, b) \
+ aux = (a & _cobits) + (b & _cobits); \
+ auy = (aux + _ctwist_cw) >> 2U; \
+ auz = (aux + auy) & _cobits2; \
+ a = (a & _pbits) | auz;
+#define CO4(r, i, j, k, l) \
+ CO(r[i], _ctwist_cw) \
+ CO(r[j], _ctwist_cw) \
+ CO(r[k], _ctwist_ccw) \
+ CO(r[l], _ctwist_ccw)
#define EO4(r, i, j, k, l) \
- r[i] ^= _eobit; \
- r[j] ^= _eobit; \
- r[k] ^= _eobit; \
- r[l] ^= _eobit;
+ r[i] ^= _eobit; \
+ r[j] ^= _eobit; \
+ r[k] ^= _eobit; \
+ r[l] ^= _eobit;
static cube_t _arraytocube(cube_array_t);
static void _cubetoarray(cube_t, cube_array_t *);
@@ -3728,3 +3728,60 @@ coord_eo(cube_t c)
{
return _coord_eo(c);
}
+
+/******************************************************************************
+Section: solvers
+
+This is a continuation of the generic methods section. Here you can find the
+implementation of all the solving algorithms.
+******************************************************************************/
+
+typedef struct {
+ cube_t cube;
+ uint8_t d;
+ int max;
+ move_t *sol;
+ int ns;
+ int nm;
+ move_t m[20];
+} dfs_arg_t;
+
+int
+solve_small_dfs(dfs_arg_t arg)
+{
+ if (arg.ns == arg.max)
+ return 0;
+
+ if (issolved(arg.cube)) {
+ if (arg.nm != arg.d)
+ return 0;
+ memcpy(&arg.sol[arg.d*arg.ns], arg.m, arg.d * sizeof(move_t));
+ return 1;
+ }
+
+ /* TODO: loop over moves and recur */
+ return 0;
+}
+
+int
+solve_small(cube_t cube, uint8_t depth, int max, move_t *sol)
+{
+ dfs_arg_t arg;
+
+ if (!issolvable(cube) || depth > 20)
+ return -1;
+
+ arg = (dfs_arg_t) {
+ .cube = cube,
+ .d = depth,
+ .max = max,
+ .sol = sol,
+ .ns = 0,
+ .nm = 0,
+ .m = {0}
+ };
+
+ return solve_small_dfs(arg);
+
+ return 0;
+}
diff --git a/cube.h b/cube.h
@@ -33,3 +33,6 @@ cube_t compose(cube_t, cube_t);
cube_t transform(cube_t, trans_t);
int16_t coord_eo(cube_t);
+
+/* Solvers return -1 in case of error, the number of solutions otherwise */
+int solve_small(cube_t, uint8_t, int, move_t *);
diff --git a/test/test.sh b/test/test.sh
@@ -2,7 +2,7 @@
re="${TEST:-$@}"
-CC="cc -DDEBUG -std=c99 -pthread -pedantic -Wall -Wextra \
+CC="cc -DDEBUG -std=c99 -pedantic -Wall -Wextra \
-Wno-unused-parameter -Wno-unused-function -g3 -D$CUBETYPE"
if [ "$CUBETYPE" = "CUBE_AVX2" ]; then
CC="$CC -mavx2"
