3 files changed, 94 insertions, 31 deletions

diff --git a/TODO.txt b/TODO.txt
index 6e000ad..8add9cc 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,11 +1,12 @@
-## Generic solver
+## Solving
+
+### Generic solver
 
-* finish implementation
 * tests: solve full cube (max 7-8 moves?)
 * more tests: eo and other stuff
 * benchmarks
 
-## Coordinates
+### Coordinates
 
 * [done] eo
 * co
@@ -17,22 +18,10 @@
 
 What about symcoord?
 
-## More I/O
-
-
-## Solving
-
-All solving functions take a cube and some parameters as input.
+### More solvers
 
-* Depth [uint, <= 20]: all solvers work at fixed depth. The caller
-  implementation can implement an A* search.
-* 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.
+* solve_light: first based on solve_generic, then optimize; benchmark
+  to see up to what length it works best (7 moves? 10 moves?)
 
 ### Implement the following solvers:
 
diff --git a/cube.c b/cube.c
index 3ba3926..cd93d48 100644
--- a/cube.c
+++ b/cube.c
@@ -3688,19 +3688,51 @@ implementation of all the solving algorithms.
 
 typedef struct {
         cube_t cube;
-        int (*estimate)(cube_t);
         uint8_t depth;
         int maxsols;
         move_t *sols;
         int nsols;
         int nmoves;
         move_t moves[20];
+        int (*estimate)(cube_t);
 } dfs_arg_t;
 
-int
+static bool
+allowednextmove(dfs_arg_t arg, move_t m)
+{
+        int n;
+        move_t mbase, l1base, l2base, maxis, l1axis, l2axis;
+
+        n = arg.nmoves;
+
+        if (n == 0)
+                return true;
+
+        mbase = m / 3;
+        maxis = mbase / 2;
+        l1base = arg.moves[n-1] / 3;
+        l1axis = l1base / 2;
+
+        if (mbase == l1base || (maxis == l1axis && mbase < l1base))
+                return false;
+
+        if (n == 1)
+                return true;
+
+        l2base = arg.moves[n-2] / 3;
+        l2axis = l1base / 2;
+
+        return l1axis != l2axis || mbase != l2base;
+}
+
+static int
 solve_generic_dfs(dfs_arg_t arg)
 {
-        int bound = arg.estimate(arg.cube);
+        dfs_arg_t nextarg;
+        int bound, ret;
+        move_t m;
+
+        bound = arg.estimate(arg.cube);
 
         if (arg.nsols == arg.maxsols || bound + arg.nmoves > arg.depth)
                 return 0;
@@ -3714,36 +3746,43 @@ solve_generic_dfs(dfs_arg_t arg)
                 return 1;
         }
 
-        /* TODO: loop over moves and recur */
-        return 0;
+        memcpy(&nextarg, &arg, sizeof(dfs_arg_t));
+        nextarg.nmoves = arg.nmoves + 1;
+        for (m = 0, ret = 0; m < 18; m++) {
+                if (allowednextmove(arg, m)) {
+                        nextarg.cube = move(arg.cube, m);
+                        nextarg.moves[arg.nmoves] = m;
+                        ret += solve_generic_dfs(nextarg);
+                }
+        }
+
+        return ret;
 }
 
 int
 solve_generic(
         cube_t cube,
-        int (*estimate)(cube_t),
         uint8_t depth,
         int maxsols,
         move_t *sols
+        int (*estimate)(cube_t),
 )
 {
         dfs_arg_t arg;
 
-        if (!issolvable(cube) || depth > 20)
+        if (!issolvable(cube) || depth > 20 || estimate == NULL)
                 return -1;
 
         arg = (dfs_arg_t) {
                 .cube = cube,
-                .estimate = estimate,
                 .depth = depth,
                 .maxsols = maxsols,
                 .sols = sols,
                 .nsols = 0,
                 .nmoves = 0,
                 .moves = {0}
+                .estimate = estimate,
         };
 
         return solve_generic_dfs(arg);
-
-        return 0;
 }
diff --git a/cube.h b/cube.h
index 3f9b509..889569f 100644
--- a/cube.h
+++ b/cube.h
@@ -169,9 +169,44 @@ int16_t coord_eo(cube_t); /* Edge orientation */
 /******************************************************************************
 Solvers
 
-Solvers return -1 in case of error, the number of solutions otherwise
+All solvers work at fixed depth, i.e. they will only find solutions of the
+specified length. Iterating over the possible lengths, if desired, is left as
+an implementation detail for the user of this library.
 
-TODO
+The solutions are returned as a list of moves, which can then be converted to
+a string using writemoves().
+
+Unless specified otherwise, all the solutions are not trivially simplifiable.
+This means that sequences like U U2 or R L R will not appear in any solution.
+Moreover, two consecutive parallel moves are always going to be sorted in
+increasing order. For example, L R2 may never appear in a solution, but R2 L
+could.
+
+Solvers return -1 in case of error, the number of solutions found otherwise.
+
+TODO NISS / INVERSE / LINEAR as a mask?
+
+All solvers take at least the following parameters, satisfying the conditions
+in square brackets:
+        - cube_t cube [issolvable(cube)]: The cube to solve.
+        - uint8_t depth [depth <= 20]: The lenght of the solution.
+        - int maxsols: The maximum number of solutions to find. The solver
+          stops when the limit is reached. If set to a negative number, all
+          the solutions are found.
+        - move_t *ret: The array where the moves of the solutions are stored.
+          There is no separator between different solutions; to read the
+          solutions, use the fact that all solutions has the same length: the
+          i-th move of the j-th solution is ret[j*depth + i].
+
+Some solvers take other parameters. See below for details.
 ******************************************************************************/
 
-int solve_generic(cube_t, int (*)(cube_t), uint8_t, int, move_t *);
+int solve_generic(
+        cube_t cube,
+        uint8_t depth,
+        int maxsols,
+        move_t *ret
+        int (*estimate)(cube_t),
+);
+
+int solve_light(cube_t, int