BackTrack Namespace Reference

Generic backtracking algorithm. More...

Classes
class	Solution
	Virtual base class of solutions for the backtracking algorithm. More...
class	Algorithm
	Implementation of a generic backtracking algorithm. More...

---

Detailed Description

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:

 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();
   }
 }