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 #include "backtrack.h" 00022 00023 using namespace BackTrack; 00024 00025 00026 //--- class BackTrack::Algorithm ----------------------------------------------- 00027 00028 /** Constructor 00029 * 00030 * Constructs an backtracking algorithm to solve a problem. The problem is 00031 * implemented in 'solution' which represents a path through the decision 00032 * tree from the root to one leaf. 00033 */ 00034 Algorithm::Algorithm (Solution& solution, unsigned int max_iter) : 00035 solution(solution), max_iter(max_iter) 00036 { 00037 first = true; 00038 valid = false; 00039 level = -1; 00040 iter = 0; 00041 } 00042 00043 /** Find the next valid solution to the problem. 00044 * 00045 * Repeated calls will find all solutions to a problem if multiple solutions 00046 * exist. 00047 */ 00048 void Algorithm::find_next_solution() 00049 { 00050 valid = find_solution(); 00051 } 00052 00053 /** Is the current solution a valid solution? */ 00054 bool Algorithm::solution_is_valid() 00055 { 00056 return valid; 00057 } 00058 00059 /** Reset the decision tree, i.e. the next call to 'find_solution' finds 00060 * the first valid solution. 00061 */ 00062 void Algorithm::reset() 00063 { 00064 while (level >= 0) 00065 { 00066 solution.reset_at(level); 00067 --level; 00068 } 00069 first = true; 00070 } 00071 00072 /** Create the next leaf on the end of the solution. */ 00073 void Algorithm::create_left_leaf() 00074 { 00075 ++level; 00076 solution.set_first_at(level); 00077 } 00078 00079 /** Backtrack through the decision tree until a node was found that hasn't 00080 * been visited, return true if an unvisited node was found. 00081 */ 00082 bool Algorithm::visit_new_node() 00083 { 00084 // If the current node is the rightmost child we must backtrack 00085 // one level because there are no more children at this level. 00086 // So we back up until we find a non-rightmost child, then 00087 // generate the child to the right. If we back up to the top 00088 // without finding an unvisted child, then all nodes have been 00089 // generated. 00090 while (level >= 0 && solution.is_last_at(level)) 00091 { 00092 solution.reset_at(level); 00093 --level; 00094 } 00095 if (level < 0) 00096 return false; 00097 solution.set_next_at(level); 00098 return true; 00099 } 00100 00101 /** Find the next valid sibling of the last leaf, return true if a valid 00102 * sibling was found. 00103 */ 00104 bool Algorithm::find_valid_sibling() 00105 { 00106 // If the current node is not valid pass through all siblings until either 00107 // a valid sibling is found or the last sibling is reached. 00108 for (;;) 00109 { 00110 ++iter; 00111 if (max_iter != 0 && iter > max_iter) 00112 return false; 00113 if (solution.is_valid_at(level)) 00114 return true; 00115 if (solution.is_last_at(level)) 00116 return false; 00117 solution.set_next_at(level); 00118 } 00119 } 00120 00121 /** Find the next valid solution to the problem, return true if a solution 00122 * was found. 00123 */ 00124 bool Algorithm::find_solution() 00125 { 00126 // If first time, need to create a root. 00127 if (first) 00128 { 00129 first = false; 00130 level = -1; 00131 if (solution.is_last_level(level)) 00132 return solution.is_valid_at(level); 00133 create_left_leaf(); 00134 } 00135 // Otherwise visit new node since solution contains the last solution. 00136 else if (!visit_new_node()) 00137 return false; 00138 00139 for (;;) 00140 { 00141 if (find_valid_sibling()) 00142 { 00143 if (solution.is_last_level(level)) 00144 return true; 00145 create_left_leaf(); 00146 } 00147 else if (max_iter != 0 && iter > max_iter) 00148 return false; 00149 else if (!visit_new_node()) 00150 return false; // The tree has been exhausted, so no solution exists. 00151 } 00152 }