1 files changed, 173 insertions, 0 deletions

diff --git a/src/solve.c b/src/solve.c
new file mode 100644
index 0000000..1f4a155
--- /dev/null
+++ b/src/solve.c
@@ -0,0 +1,173 @@
+#include "solve.h"
+
+/* Local functions ***********************************************************/
+
+static bool        allowed_next(Move move, DfsData *dd);
+static void        dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
+static void        dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd);
+static bool        dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd);
+static void        dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
+static bool        dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
+
+/* Local functions ***********************************************************/
+
+static bool
+allowed_next(Move move, DfsData *dd)
+{
+        if (!possible_next(dd->last2, dd->last1, move))
+                return false;
+
+        if (commute(dd->last1, move))
+                return dd->move_position[dd->last1] < dd->move_position[move];
+
+        return true;
+}
+
+static void
+dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+{
+        if (dfs_stop(c, s, opts, dd))
+                return;
+
+        if (dfs_check_solved(s, opts, dd))
+                return;
+
+        dfs_branch(c, s, opts, dd);
+
+        if (opts->can_niss && !dd->niss)
+                dfs_niss(c, s, opts, dd);
+}
+
+static void
+dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+{
+        Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves;
+
+        int i, maxnsol = opts->max_solutions;
+
+        for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) {
+                m = moves[i];
+                if (allowed_next(m, dd)) {
+                        dd->last2 = dd->last1;
+                        dd->last1 = m;
+                        append_move(dd->current_alg, m, dd->niss);
+
+                        dfs(apply_move(m, c), s, opts, dd);
+
+                        dd->current_alg->len--;
+                        dd->last2 = l2;
+                        dd->last1 = l1;
+                }
+        }
+}
+
+static bool
+dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd)
+{
+        if (dd->lb != 0)
+                return false;
+
+        if (dd->current_alg->len == dd->d) {
+                if (s->is_valid(dd->current_alg) || opts->all)
+                        append_alg(dd->sols, dd->current_alg);
+
+                if (opts->verbose)
+                        print_alg(dd->current_alg, false);
+        }
+
+        return true;
+}
+
+static void
+dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+{
+        Move l1 = dd->last1, l2 = dd->last2;
+        CubeTarget ct;
+
+        ct.cube = apply_move(inverse_move(l1), (Cube){0});
+        ct.target = 1;
+
+        if (dd->current_alg->len == 0 || s->estimate(ct)) {
+                dd->niss  = true;
+                dd->last1 = NULLMOVE;
+                dd->last2 = NULLMOVE;
+
+                dfs(inverse_cube(c), s, opts, dd);
+
+                dd->last1 = l1;
+                dd->last2 = l2;
+                dd->niss  = false;
+        }
+}
+
+static bool
+dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+{
+        CubeTarget ct = {
+                .cube   = c,
+                .target = dd->d - dd->current_alg->len
+        };
+
+        if (dd->sols->len >= opts->max_solutions)
+                return true;
+
+        dd->lb = s->estimate(ct);
+        if (opts->can_niss && !dd->niss)
+                dd->lb = MIN(1, dd->lb);
+
+        if (dd->current_alg->len + dd->lb > dd->d)
+                return true;
+
+        return false;
+}
+
+/* Public functions **********************************************************/
+
+AlgList *
+solve(Cube cube, Step *step, SolveOptions *opts)
+{
+        AlgListNode *node;
+        AlgList *sols = new_alglist();
+        Cube c;
+
+        if (step->detect != NULL)
+                step->pre_trans = step->detect(cube);
+        c = apply_trans(step->pre_trans, cube);
+
+        DfsData dd = {
+                .m           = 0,
+                .niss        = false,
+                .lb          = -1,
+                .last1       = NULLMOVE,
+                .last2       = NULLMOVE,
+                .sols        = sols,
+                .current_alg = new_alg("")
+        };
+
+        if (step->ready != NULL && !step->ready(c)) {
+                fprintf(stderr, "Cube not ready for solving step: ");
+                fprintf(stderr, "%s\n", step->ready_msg);
+                return sols;
+        }
+
+        moveset_to_list(step->moveset, dd.sorted_moves);
+        movelist_to_position(dd.sorted_moves, dd.move_position);
+
+        for (dd.d = opts->min_moves;
+             dd.d <= opts->max_moves &&
+                 !(sols->len && opts->optimal_only) &&
+                 sols->len < opts->max_solutions;
+             dd.d++) {
+                if (opts->verbose)
+                        fprintf(stderr,
+                                "Found %d solutions, searching depth %d...\n",
+                                sols->len, dd.d);
+                dfs(c, step, opts, &dd);
+        }
+
+        for (node = sols->first; node != NULL; node = node->next)
+                transform_alg(inverse_trans(step->pre_trans), node->alg);
+
+        free_alg(dd.current_alg);
+        return sols;
+}