00001 /* 00002 * Sudoku: A plug-in for the Video Disk Recorder 00003 * 00004 * Copyright (C) 2005-2007, Thomas Günther <tom@toms-cafe.de> 00005 * 00006 * This program is free software; you can redistribute it and/or modify 00007 * it under the terms of the GNU General Public License as published by 00008 * the Free Software Foundation; either version 2 of the License, or 00009 * (at your option) any later version. 00010 * 00011 * This program is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License along 00017 * with this program; if not, write to the Free Software Foundation, Inc., 00018 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00019 */ 00020 00021 #ifndef VDR_SUDOKU_BACKTRACK_H 00022 #define VDR_SUDOKU_BACKTRACK_H 00023 00024 #include "sudoku.h" 00025 00026 00027 /** Generic backtracking algorithm 00028 * 00029 * Inspired by an article by Roger Labbe "Solving Combinatorial Problems with 00030 * STL and Backtracking" in C/C++-Users Journal, February 2000, pp. 56-64. 00031 * 00032 * The solution to a combinatorial problem can be described as a sequence of 00033 * decisions. The backtracking algorithm traverses the decision tree 00034 * depth-first. Each solution of the problem is a path through the tree from the 00035 * root to one leaf. The algorithm traverses the tree by changing the elements 00036 * of the solution. An element passes through all siblings on a certain level, 00037 * i.e. through all possible decisions. Each step is checked if it makes the 00038 * solution invalid, in which case the traversal of the whole branch is 00039 * cancelled. Otherwise the algorithm either goes one level deeper or if this is 00040 * the last level it has found one valid solution. After the last sibling on a 00041 * level has been processed the algorithm goes back one level. Finally all valid 00042 * solutions have been found if it comes back to the root node. 00043 * 00044 * This implementation of the backtracking algorithm consists of two classes. 00045 * The Algorithm class contains the generic backtracking algorithm itself. The 00046 * Solution class is the virtual base class for all specific solution classes. 00047 * To solve a certain problem the specific solution class has to inherit from 00048 * Solution implementing all virtual methods. 00049 * 00050 * Example: 00051 * 00052 * \code 00053 * class ColorStatesList : public Solution 00054 * { 00055 * int clist[NUMBER_STATES]; 00056 * void set_first_at(unsigned int level) { clist[level] = 0; } 00057 * void set_next_at(unsigned int level) { ++clist[level]; } 00058 * void reset_at(unsigned int level) {} 00059 * bool is_last_at(unsigned int level) { return clist[level] >= LAST_COLOR; } 00060 * bool is_valid_at(int level) { return check_all_neighbors_until(level); } 00061 * bool is_last_level(int level) [ return level >= NUMBER_STATES-1; } 00062 * ... 00063 * }; 00064 * 00065 * void find_all_solutions() 00066 * { 00067 * ColorStatesList color_states_list(...); 00068 * Algorithm algorithm(color_states_list); 00069 * algorithm.find_next_solution(); 00070 * while (algorithm.solution_is_valid()) 00071 * { 00072 * // Do something with the solution. 00073 * ... 00074 * algorithm.find_next_solution(); 00075 * } 00076 * } 00077 * \endcode 00078 */ 00079 namespace BackTrack 00080 { 00081 00082 //--- virtual base class BackTrack::Solution --------------------------------- 00083 00084 /** Virtual base class of solutions for the backtracking algorithm */ 00085 class Solution 00086 { 00087 public: 00088 00089 /** Destructor */ 00090 virtual ~Solution() {}; 00091 00092 /** Set the element to the first sibling. */ 00093 virtual void set_first_at(unsigned int level) = 0; 00094 00095 /** Set the element to the next sibling. */ 00096 virtual void set_next_at(unsigned int level) = 0; 00097 00098 /** Reset the element. */ 00099 virtual void reset_at(unsigned int level) = 0; 00100 00101 /** Check if the element is set to the last sibling. */ 00102 virtual bool is_last_at(unsigned int level) const = 0; 00103 00104 /** Check if the element is valid (following elements ignored). */ 00105 virtual bool is_valid_at(int level) const = 0; 00106 00107 /** Check if the level is the last possible level. */ 00108 virtual bool is_last_level(int level) const = 0; 00109 }; 00110 00111 00112 //--- class BackTrack::Algorithm --------------------------------------------- 00113 00114 /** Implementation of a generic backtracking algorithm */ 00115 class Algorithm 00116 { 00117 Solution& solution; 00118 bool first; 00119 bool valid; 00120 int level; 00121 unsigned int max_iter, iter; 00122 00123 public: 00124 00125 /** Constructor 00126 * 00127 * Constructs an backtracking algorithm to solve a problem. The problem is 00128 * implemented in 'solution' which represents a path through the decision 00129 * tree from the root to one leaf. 00130 */ 00131 Algorithm(Solution& solution, unsigned int max_iter = 0); 00132 00133 /** Find the next valid solution to the problem. 00134 * 00135 * Repeated calls will find all solutions to a problem if multiple solutions 00136 * exist. 00137 */ 00138 void find_next_solution(); 00139 00140 /** Is the current solution a valid solution? */ 00141 bool solution_is_valid(); 00142 00143 /** Reset the decision tree, i.e. the next call to 'find_solution' finds 00144 * the first valid solution. 00145 */ 00146 void reset(); 00147 00148 private: 00149 00150 /** Create the next leaf on the end of the solution. */ 00151 void create_left_leaf(); 00152 00153 /** Backtrack through the decision tree until a node was found that hasn't 00154 * been visited, return true if an unvisited node was found. 00155 */ 00156 bool visit_new_node(); 00157 00158 /** Find the next valid sibling of the last leaf, return true if a valid 00159 * sibling was found. 00160 */ 00161 bool find_valid_sibling(); 00162 00163 /** Find the next valid solution to the problem, return true if a solution 00164 * was found. 00165 */ 00166 bool find_solution(); 00167 }; 00168 00169 } // namespace BackTrack 00170 00171 #endif // VDR_SUDOKU_BACKTRACK_H