From 3568412f8f230774d0d11d7ed1c897424f95d3ef Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Thu, 11 Nov 2021 21:37:34 +0100
Subject: Rewritten from scratch. Welocme nissy 2.0!

---
 src/solve.c | 173 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 173 insertions(+)
 create mode 100644 src/solve.c

(limited to 'src/solve.c')

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;
+}
-- 
cgit v1.3