Started working on solve

5 files changed, 97 insertions, 29 deletions

diff --git a/README.md b/README.md
index 383b50c..505b840 100644
--- 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
index 882c836..ec850f0 100755
--- 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
index 8ca2c72..3a85054 100644
--- 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
index 5dc7410..c4effbe 100644
--- 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
index a018401..68b87aa 100755
--- 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"