1 files changed, 159 insertions, 0 deletions
diff --git a/backtrack.h b/backtrack.h
new file mode 100644
index 0000000..263e1dc
--- /dev/null
+++ b/backtrack.h
@@ -0,0 +1,159 @@
+/*
+ * Sudoku: A plugin for the Video Disk Recorder
+ *
+ * See the README file for copyright information and how to reach the author.
+ *
+ * $Id: backtrack.h 11 2005-10-28 01:00:01Z tom $
+ */
+
+#ifndef VDR_SUDOKU_BACKTRACK_H
+#define VDR_SUDOKU_BACKTRACK_H
+
+#include "sudoku.h"
+
+
+/** Generic backtracking algorithm
+ *
+ * Inspired by an article by Roger Labbe "Solving Combinatorial Problems with
+ * STL and Backtracking" in C/C++-Users Journal, February 2000, pp. 56-64.
+ *
+ * The solution to a combinatorial problem can be described as a sequence of
+ * decisions. The backtracking algorithm traverses the decision tree
+ * depth-first. Each solution of the problem is a path through the tree from the
+ * root to one leaf. The algorithm traverses the tree by changing the elements
+ * of the solution. An element passes through all siblings on a certain level,
+ * i.e. through all possible decisions. Each step is checked if it makes the
+ * solution invalid, in which case the traversal of the whole branch is
+ * cancelled. Otherwise the algorithm either goes one level deeper or if this is
+ * the last level it has found one valid solution. After the last sibling on a
+ * level has been processed the algorithm goes back one level. Finally all valid
+ * solutions have been found if it comes back to the root node.
+ *
+ * This implementation of the backtracking algorithm consists of two classes.
+ * The Algorithm class contains the generic backtracking algorithm itself. The
+ * Solution class is the virtual base class for all specific solution classes.
+ * To solve a certain problem the specific solution class has to inherit from
+ * Solution implementing all virtual methods.
+ *
+ * Example:
+ *
+ * \code
+ * class ColorStatesList : public Solution
+ * {
+ *   int clist[NUMBER_STATES];
+ *   void set_first_at(unsigned int level) { clist[level] = 0; }
+ *   void set_next_at(unsigned int level) { ++clist[level]; }
+ *   void reset_at(unsigned int level) {}
+ *   bool is_last_at(unsigned int level) { return clist[level] >= LAST_COLOR; }
+ *   bool is_valid_at(int level) { return check_all_neighbors_until(level); }
+ *   bool is_last_level(int level) [ return level >= NUMBER_STATES-1; }
+ *   ...
+ * };
+ *
+ * void find_all_solutions()
+ * {
+ *   ColorStatesList color_states_list(...);
+ *   Algorithm algorithm(color_states_list);
+ *   algorithm.find_next_solution();
+ *   while (algorithm.solution_is_valid())
+ *   {
+ *     // Do something with the solution.
+ *     ...
+ *     algorithm.find_next_solution();
+ *   }
+ * }
+ * \endcode
+ */
+namespace BackTrack
+{
+
+  //--- virtual base class BackTrack::Solution ---------------------------------
+
+  /** Virtual base class of solutions for the backtracking algorithm */
+  class Solution
+  {
+  public:
+
+    /** Destructor */
+    virtual ~Solution() {};
+
+    /** Set the element to the first sibling. */
+    virtual void set_first_at(unsigned int level) = 0;
+
+    /** Set the element to the next sibling. */
+    virtual void set_next_at(unsigned int level) = 0;
+
+    /** Reset the element. */
+    virtual void reset_at(unsigned int level) = 0;
+
+    /** Check if the element is set to the last sibling. */
+    virtual bool is_last_at(unsigned int level) const = 0;
+
+    /** Check if the element is valid (following elements ignored). */
+    virtual bool is_valid_at(int level) const = 0;
+
+    /** Check if the level is the last possible level. */
+    virtual bool is_last_level(int level) const = 0;
+  };
+
+
+  //--- class BackTrack::Algorithm ---------------------------------------------
+
+  /** Implementation of a generic backtracking algorithm */
+  class Algorithm
+  {
+    Solution& solution;
+    bool first;
+    bool valid;
+    int level;
+    unsigned int max_iter, iter;
+
+  public:
+
+    /** 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(Solution& solution, unsigned int max_iter = 0);
+
+    /** Find the next valid solution to the problem.
+     *
+     * Repeated calls will find all solutions to a problem if multiple solutions
+     * exist. Return true if a solution was found.
+     */
+    void find_next_solution();
+
+    /** Is the current solution a valid solution? */
+    bool solution_is_valid();
+
+    /** Reset the decision tree, i.e. the next call to 'find_solution' finds
+     * the first valid solution.
+     */
+    virtual void reset();
+
+  private:
+
+    /** Create the next leaf on the end of the solution. */
+    void create_left_leaf();
+
+    /** Backtrack through the decision tree until a node was found that hasn't
+     * been visited, return true if an unvisited node was found.
+     */
+    bool visit_new_node();
+
+    /** Find the next valid sibling of the last leaf, return true if a valid
+     * sibling was found.
+     */
+    bool find_valid_sibling();
+
+    /** Find the next valid solution to the problem, return true if a solution
+     * was found.
+     */
+    bool find_solution();
+  };
+
+} // namespace BackTrack
+
+#endif // VDR_SUDOKU_BACKTRACK_H