1 files changed, 140 insertions, 0 deletions
diff --git a/backtrack.cpp b/backtrack.cpp
new file mode 100644
index 0000000..963724a
--- /dev/null
+++ b/backtrack.cpp
@@ -0,0 +1,140 @@
+/*
+ * Sudoku: A plugin for the Video Disk Recorder
+ *
+ * See the README file for copyright information and how to reach the author.
+ *
+ * $Id: backtrack.cpp 11 2005-10-28 01:00:01Z tom $
+ */
+
+#include "backtrack.h"
+
+using namespace BackTrack;
+
+
+//--- class BackTrack::Algorithm -----------------------------------------------
+
+/** Constructor
+ *
+ * Constructs an backtracking algorithm to solve a problem. The problem is
+ * implemented in 'solution' which represents a path through the decision
+ * tree from the root to one leaf.
+ */
+Algorithm::Algorithm (Solution& solution, unsigned int max_iter) :
+  solution(solution), max_iter(max_iter)
+{
+  first = true;
+  valid = false;
+  level = -1;
+  iter = 0;
+}
+
+/** Find the next valid solution to the problem.
+ *
+ * Repeated calls will find all solutions to a problem if multiple solutions
+ * exist.
+ */
+void Algorithm::find_next_solution()
+{
+  valid = find_solution();
+}
+
+/** Is the current solution a valid solution? */
+bool Algorithm::solution_is_valid()
+{
+  return valid;
+}
+
+/** Reset the decision tree, i.e. the next call to 'find_solution' finds
+ * the first valid solution.
+ */
+void Algorithm::reset()
+{
+  while (level >= 0)
+  {
+    solution.reset_at(level);
+    --level;
+  }
+  first = true;
+}
+
+/** Create the next leaf on the end of the solution. */
+void Algorithm::create_left_leaf()
+{
+  ++level;
+  solution.set_first_at(level);
+}
+
+/** Backtrack through the decision tree until a node was found that hasn't
+ * been visited, return true if an unvisited node was found.
+ */
+bool Algorithm::visit_new_node()
+{
+  // If the current node is the rightmost child we must backtrack
+  // one level because there are no more children at this level.
+  // So we back up until we find a non-rightmost child, then
+  // generate the child to the right. If we back up to the top
+  // without finding an unvisted child, then all nodes have been
+  // generated.
+  while (level >= 0 && solution.is_last_at(level))
+  {
+    solution.reset_at(level);
+    --level;
+  }
+  if (level < 0)
+    return false;
+  solution.set_next_at(level);
+  return true;
+}
+
+/** Find the next valid sibling of the last leaf, return true if a valid
+ * sibling was found.
+ */
+bool Algorithm::find_valid_sibling()
+{
+  // If the current node is not valid pass through all siblings until either
+  // a valid sibling is found or the last sibling is reached.
+  for (;;)
+  {
+    ++iter;
+    if (max_iter != 0 && iter > max_iter)
+      return false;
+    if (solution.is_valid_at(level))
+      return true;
+    if (solution.is_last_at(level))
+      return false;
+    solution.set_next_at(level);
+  }
+}
+
+/** Find the next valid solution to the problem, return true if a solution
+ * was found.
+ */
+bool Algorithm::find_solution()
+{
+  // If first time, need to create a root.
+  if (first)
+  {
+    first = false;
+    level = -1;
+    if (solution.is_last_level(level))
+      return solution.is_valid_at(level);
+    create_left_leaf();
+  }
+  // Otherwise visit new node since solution contains the last solution.
+  else if (!visit_new_node())
+    return false;
+
+  for (;;)
+  {
+    if (find_valid_sibling())
+    {
+      if (solution.is_last_level(level))
+        return true;
+      create_left_leaf();
+    }
+    else if (max_iter != 0 && iter > max_iter)
+      return false;
+    else if (!visit_new_node())
+      return false; // The tree has been exhausted, so no solution exists.
+  }
+}