Solving Combinatorial Problems with STL and Backtracking

The STL approach extends nicely to problems of all sorts, and helps make for more generic solutions


February 01, 2000
URL:http://www.drdobbs.com/cpp/solving-combinatorial-problems-with-stl/184401194

Algorithms that use general problem solving techniques are among the most simple and powerful algorithms available. They successively create possible solutions to a problem and test each solution for correctness. Such code can be written once and then reused for many different problems. This allows a programmer to avoid writing a specialized algorithm for each problem.

Backtracking is one example of these techniques. Backtracking works on the class of problems called combinatorial problems. A problem is combinatorial if the solution can be expressed as an ordered set of choices from a list provided in the problem statement. For example, scheduling is a combinatorial problem because the solution is an ordered list of jobs.

Backtracking is part of a family of related algorithms: branch-and-bound, hill-climbing, Z*, A*, alpha-beta search, etc., all which use general problem solving techniques to solve combinatorial problems. Of these algorithms, backtracking is both simple and representative. It is relatively easy to learn, and the techniques backtracking uses are similar to its more complicated cousins.

Unfortunately, many treatments of backtracking ignore its greatest strength — its generality. Specialized algorithms are written for each problem, leading to one algorithm to solve the n-queens problems, another to solve optimal packing, etc. I use C++ templates and STL to write a generic algorithm that works for any problem solvable by backtracking. My class requires you to write a simple criterion function that the algorithm will use to find the solution.

A Brute Force Approach

The easiest way to understand backtracking is to start by studying a brute force approach that is simple but impractical. Later I transform it into the efficient and practical technique of backtracking.

A combinatorial problem typically has a finite number of solutions. The brute force algorithm generates every possible solution to a combinatorial problem and then tests it for correctness.

do {
   generate the next solution;
   test solution for validity;
} while (solution is invalid);

This algorithm is general and slow. It works for any problem that has a finite number of testable solutions, so it is general. It is slow because there are an exponential number of possible solutions to a combinatorial problem.

However, the algorithm's simplicity makes it easy to use. Generating all possible solutions to a combinatorial problem is trivial; once the code is written it can be used for any future problem. The only remaining task is writing a function that tests if a solution is valid. The problem statement defines how to test the solution, so a few minutes of coding produces an algorithm guaranteed to find an answer, no matter how slowly.

Optimizing the Process

I use the n-coloring problem as an example. The n-coloring problem requires you to color a map with n colors such that no adjacent regions are colored the same. This problem is easy to understand, but it has many important real world applications.

Consider using the brute force technique described above to color the United States with four colors. There are over 1029 possible colorings. No computer could generate and test this many solutions in a reasonable time. There needs to be a better way.

Imagine you are trying to color a map by hand. Would you color the entire map, then check if it was valid? Not if you're smart. You would color one state at a time, and immediately check if it was the same color as a neighbor. If it matched the color of a neighbor you would immediately correct your mistake — there is no point in coloring the rest of the map because the final result is guaranteed to be invalid.

Therefore, you would keep changing the color of the state until it didn't conflict with its neighbors. If you couldn't find a color that was correct, you'd conclude that you made a bad decision earlier. You would then backtrack to a previously colored state, change its color and then proceed forward.

Decision Trees

Any solution to a combinatorial problem may be regarded as a series of decisions. Coloring the contiguous U.S. map with four colors consists of 49 decisions, one decision for each state. Each decision has four possible choices.

A problem's solution space is defined as the set of all possible solutions. Decision trees represent the solution space in a tree structure. The tree has one level for each decision. The root of the tree represents the initial state. The root has one child for each choice that can be made for the first decision. Each of these children each has their own set of children representing the choices available for the second decision. This pattern continues to the bottom of the tree.

Thus, the decision tree for coloring the U.S. would have 49 levels, one for each state, and each node would have four children, one for each color. Any traversal from the root to a leaf represents one possible solution to the problem. Figure 1 illustrates a decision tree for coloring three states with two colors.

Figure 1: A decision tree for coloring three states with two colors.

Pruning the Tree

Backtracking uses a decision tree to formalize the ad hoc hand coloring method described above. It starts at the root of the tree with no states colored. It colors the first state by choosing one of the four children of the root. To keep the algorithm simple, the backtracking algorithm always chooses the leftmost child. It traverses to that child, making it the current node.

The algorithm then colors the next state by choosing the leftmost child of the current node. As with coloring by hand, the algorithm now checks to see if the coloring is valid. Suppose it finds that both states are the same color; assuming the states are adjacent on the map, the coloring is invalid.

Since the coloring is invalid, there is no need to traverse any lower in the tree; all lower branches are guaranteed to yield invalid results as well. Therefore the algorithm prunes the current node from the tree, and backtracks to the previous node.

Pruning the tree guarantees that the invalid colorings are not considered. The gains are not negligible. The case above pruned 447-2 nodes from the decision tree, which is over 1028 decisions that were not examined.

The backtrack algorithm continues to traverse the tree, descending level by level as long as the coloring is valid, and backtracking and pruning as soon as it detects an invalid coloring.

Note that at each step the algorithm needs to test only the most recent decision. If the algorithm is coloring the nth state, the n-1 states must be valid since they were just checked in the previous step. Thus, the algorithm only checks to see if the nth state's coloring conflicts with its adjacent states. If not, the coloring of all n states must be valid.

Storing Decision Trees

Although I described the algorithm as if it traversed a preexisting decision tree, it actually uses a more intelligent technique. The decision tree for even a modest problem would exceed the storage capacities of any known computer.

Instead, the algorithm generates only one node of the tree at a time, which is always the current leaf. Invalid nodes are not stored because they are pruned. This allows the algorithm to store the entire tree in an array. Each array element represents one level in the tree; the nth element of the array is a child of the n-1th node.

For the coloring problem, let the colors be numbered 1 to 4. The algorithm colors the first state by appending the first color to an empty array, giving [1]. It then colors the next state by appending 1 to the array, giving [1,1]. This coloring is invalid (assume the states are adjacent), so the algorithm must backtrack. Conceptually, the algorithm backs up to the previous node, flags it invalid, and then creates a new child node. In practice, the algorithm just increments the last element's value, giving [1,2]. This coloring is valid, so the algorithm creates a new child, giving [1,2,1].

What happens when the current node is invalid and it is the last valid color? Instead of incrementing the element, the algorithm backtracks by deleting the last element until it finds an element that it can increment. Thus [3,2,4] become [3,3], and [4,1,4,4,4] becomes [4,2]. In effect, the algorithm counts in base n arithmetic.

This implementation is very general. The integers in the array merely represent the nodes in the decision tree. By defining what the integers represent, the algorithm will work with any decision tree.

STL Implementation

Most backtracking algorithms are implemented using an array of ints to store the decision tree, and require a user-defined function that validates the decision tree. The algorithm generates a decision, passes it to the user-defined function, and either backtracks or continues forward based on the result of the function call. However, backtracking is a generalized algorithm. It should be implemented in a generic way that will work for any data type and any container choice. For example, it would be nice to use enums to represent the color choices for the map coloring problem.

STL provides a powerful paradigm to make the backtracking algorithm generic. In STL, algorithms are implemented as functions that use iterators to traverse over a container. Iterators have the same semantics as C-style pointers. Templates allow the functions to use iterators from any type of container, letting you use C-style arrays, vectors, deques, etc., without any changes to the algorithm's code.

My backtrack algorithm uses templates that allow it to use any STL container to store the decision tree. The template arguments allow you to specify your data type (int, enum, etc.), the container that stores the decision tree (vector, c array, etc.), and the user-defined function that evaluates the decision tree's correctness.

>Listing One provides the code for an STL-style backtracking algorithm. The algorithm is implemented as a functor, which is a class with operator() defined so the class can be used like a function [1]. Listing Two contains a program that performs map coloring on the U.S.

Listing One: An STL-style backtracking functor
#ifndef BackTrack_h
#define BackTrack_h

template <class T, class I, class V>
class BackTrack {
public:

   // precondition: first <= last
   BackTrack(const T&  first, const T&  last);


   // Finds the next solution to the problem. Repeated calls 
   // will find all solutions to a problem if multiple solutions 
   // exist.
   // Returns true if a solution was found.
   //
   // Set first to true to get the first solution.
   //
   bool operator() (const I& begin, I end, bool& first);


private:
   // Finds the next valid sibling of the leaf (end-1). 
   // Returns true is if a valid sibling was found.
   bool FindValidSibling (const I& begin, const I& end);


   // Backtracks through the decision tree until it finds a node
   // that hasn't been visited. Returns true if an unvisited 
   // node was found.
   bool VisitNewNode (const I& begin, I& end);

   void CreateLeftLeaf (I& end);

   T left_child;
   T right_child;

   V IsValid;
};

template <class T, class I, class V>
BackTrack<T,I,V>::BackTrack(const T& first, const T& last) 
   : left_child (first), right_child (last)
{
}

template <class T, class I, class V>
bool BackTrack<T,I,V>::VisitNewNode(const I& begin, I& end)
{
   // ALGORITHM:
   //
   // 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.

   // Back up as long as the node is the rightmost child of 
   // its parent.
   while (end-begin > 0 && *(end-1) == right_child)
      --end;

   I back = end-1;
   if (end-begin > 0 && *back != right_child) {
      ++(*back);
      return true;
   } else
      return false;
}

template <class T, class I, class V> 
bool BackTrack<T,I,V>::FindValidSibling
(const I& begin, const I& end)
{
   // Note that on entry to this routine the leaf has not yet 
   // been used or tested for validity, so the leaf is 
   // considered a "sibling" of itself.

   I back = end-1;
   while (true) {
      if (IsValid (begin, end))
         return true;
      else if (*back != right_child)
         ++(*back);
      else
         return false;
   }
}

template <class T, class I, class V>
inline void BackTrack<T,I,V>::CreateLeftLeaf (I& end)
{
   *(end++) = left_child;
}

template <class T, class I, class V> 
bool BackTrack<T,I,V>::operator () 
(const I& begin, I end, bool& first)
{
   const int size = end - begin;

   // If first time, need to create a root.
   // Otherwise need to visit new node since vector
   // contains the last solution.
   if (first) {
      first = false;
      end = begin;
      CreateLeftLeaf (end);
   } else if (!VisitNewNode (begin, end))
      return false;

   while (true) {
      if (FindValidSibling (begin, end)) {
         if (end - begin < size)
            CreateLeftLeaf (end);
         else
            return true;

      } else if (!VisitNewNode (begin, end))
         return false; // the tree has been exhausted, 
                       // so no solution exists.
   }
}
Listing 2: A program that colors a U.S. map with four colors, such that no adjacent states are the same color
#include <assert.h>

#include <functional>
#include <vector>

#include "BackTrack.h"


enum State
   {ME, NH, VT, MA, CT, RI, NY, PA, NJ, DE, MD, DC, 
    VA, NC, WV, SC, GA, FL, AL, TN, KY, OH, IN, MI, 
    MS, LA, AR, MO, IL, WI, IA, MN, ND, SD, NE, KS, 
    OK, TX, NM, CO, WY, MT, ID, UT, AZ, NV, CA, OR, WA};

const int NumberStates = 49;
const int MaxNeighbors = 8;

enum Color {Blue, Yellow, Green, Red};

inline Color& operator++ (Color& c)
{
   c = Color (c + 1);
   return c;
}

inline State& operator++ (State& c)
{
   c = State (c + 1);
   return c;
}

typedef std::vector<Color> Map;
typedef Map::iterator MapIter;


// store neighbor's of each state.
// Neighbor [i][0] == # of neighbors  of state i
// Neighbor [i][j] == jth neighbor of state i
State Neighbor [NumberStates][MaxNeighbors+1]; 

inline Connect (State s1, State s2)
{
   int count = ++Neighbor [s1][0];
   Neighbor [s1][count] = s2;

   count = ++Neighbor [s2][0];
   Neighbor [s2][count] = s1;

   assert (Neighbor [s1][0] <= MaxNeighbors);
   assert (Neighbor [s2][0] <= MaxNeighbors);
}


void BuildMap ()
{
   for (int i = 0; i < NumberStates; i++)
         Neighbor [i][0] = State(0);


   Connect (ME,NH);
   Connect (NH,VT); Connect (NH,MA);
   Connect (VT,MA); Connect (VT,NY);
   Connect (MA,NY); Connect (MA,CT); Connect (MA,RI);
   Connect (CT,RI); Connect (CT,NY);
   Connect (NY,NJ); Connect (NY,PA); Connect (NY,OH);
   Connect (PA,NJ); Connect (PA,DE); Connect (PA,MD); 
   Connect (PA,WV); Connect (PA,OH);

   // ... omitted to save space -- full source code available
   // on CUJ ftp site (see p. 3 for downloading instructions)

   Connect (UT,NV); Connect (UT,AZ);
   Connect (AZ,NV); Connect (AZ,CA);
   Connect (NV,OR); Connect (NV,CA);
   Connect (CA,OR);
   Connect (OR,WA);
}


struct ColorIsValid : 
   public std::binary_function<MapIter, MapIter, bool> 
{
   bool operator() (const MapIter& begin, const MapIter& end) 
   {
      State LastState = State (end-begin-1);
      Color LastColor = *(end-1);
      bool Valid = true;
      for (int i = 1; i <= Neighbor [LastState][0]; i++) {
         State NeighborState = Neighbor [LastState][i];
         if (NeighborState < LastState &&
             *(begin+NeighborState) == LastColor)
             return false;
      }
      return true;
   }
};



int main (int argc, char* argv [])
{
   Map tree (NumberStates);

   BackTrack <Color, MapIter, ColorIsValid> ColorMap (Blue, Red);
   BuildMap ();

   bool FirstTime = true;
   // find first 100 valid colorings of the U.S.
   for (int i = 0; i < 100; i++)
      bool Valid = 
         ColorMap (tree.begin(), tree.end(), FirstTime);

   return 0;
}

There are five steps in using the backtracking algorithm:

1. Define the types.

2. Define the operators.

3. Define a validator function.

4. Construct a BackTrack object.

5. Call it.

1. Define the Types

The BackTrack class has three template arguments:

template
<class I, class T, class V>
class BackTrack {...};

I is the iterator type for the container. T is the type of data being stored in the container, and V is a user-defined boolean function that will return true if the current decision tree is valid.

You will typically use a discrete type for T, such as int or enum, and an STL container iterator for I. For the map coloring problem you may choose to use an enum for the colors, and to store them in a vector. Thus:

enum Color {
   Blue,
   Yellow,
   Green,
   Red
};

Add some typdefs to make simpler type names, and declare the container:

typedef vector<Color> Map;
typedef Map::iterator MapIter;
Map tree (49);

2. Define the Operators

BackTrack uses the following operators on T: &, ==, !=, =, and ++ (prefix). The compiler predefines these operators for int. If you are using int for T, your work is done.

However, ++ is not defined for enum. So define your own:

Color& operator++ (Color& c){...}

3. Define a Validator Function

Derive your validator function from std::binary_function:

template<class T>
struct ColorIsValid:
   public std::binary_function<MapIter,
             MapIter, bool> {
   bool operator()
      (const MapIter& begin,
       const MapIter& end) const
   {
      // .. put validation code here
   }
};

The validator function takes iterators pointing to the beginning and end of the container holding the tree. This function should return true if the coloring is valid. Remember that at the time of the call every element except the last has already been checked for validity, so you only need to check that the back element, *(end-1), is valid.

The problem statement almost always exactly defines what the validator needs to test. For example, the n-color problem requires that no adjacent area have the same color. In pseudocode the test would look like this:

for (each neighbor of  *(end-1))
   if (neighbor's color ==
       *(end-1)'s color)
      return false;
return true;

4. Construct a BackTrack Object

To generate the decision tree the algorithm needs to know the valid range for T, the type. The BackTrack constructor accepts these values as parameters:

BackTrack(const T&  first,
          const T&  last);

Now you can construct a BackTrack object:

BackTrack<Color, MapIter, ColorIsValid>
ColorMap (Blue, Red);

5. Call the BackTrack Object

BackTrack's operator() takes the begin and end iterators to your container, along with a bool parameter that specifies whether this is the first call. (I discuss that parameter shortly.) Finding a valid coloring now requires one line of code:

bool FirstTime = true;
bool IsValid =
   ColorMap(tree.begin(), tree.end(),
      FirstTime);

This function returns true if a valid solution was found. If one was found, the tree now contains the coloring for each state.

Many problems, including map coloring, have multiple solutions. Once you have found the first solution you can call operator() again to get the next solution. This works because the current position in the tree and the solution have the same representation. Backtracking from the current solution will result in the next valid solution to be found. The variable FirstTime is set to false when operator() is called, guaranteeing that subsequent calls find the next solution.

Implementation Details

operator() starts by creating an empty tree. It generates the first node by calling CreateLeftLeaf. This private function takes an iterator pointing to the end of the container, and appends the first valid value of T, which is stored in the private variable left_child.

operator() now enters a loop that will generate the lower levels of the tree. The loop first passes the decision tree to the function bool FindValidSibling(). This function finds the first valid sibling of the current leaf. At the time of call the current leaf has not been checked for validity, so the function first checks if this leaf is valid. It does this by calling the user-defined validator function stored in the private variable IsValid. If the leaf is valid, FindValidSibling returns true without changing the decision tree. However, if the leaf is invalid, FindValidSibling will generate the next sibling to the leaf by using operator++ to increment the leaf's value. FindValidSibling successively calls IsValid and then increments the leaf until IsValid returns true or all siblings have been generated without success. If a valid sibling is found, true is returned.

operator() checks the result of FindValidSibling. If it returned true, the node is valid. If the tree has been completely generated, the solution is valid and operator() returns true. Otherwise operator() must generate the next level in the tree and test it. So it calls CreateLeftLeaf and returns to the top of the loop, causing FindValidSibling to be called on the new tree.

However, if the node was invalid, operator() must now backtrack to a valid node. Function VisitNewNode accomplishes this. It backs up one level as long as the current leaf is the last valid value of T, which is stored in private variable right_child. Once VisitNewNode finds a leaf unequal to right_child, it creates a new leaf by incrementing the current leaf's value and returns true. VisitNewNode returns false if it returns all the way to the root, having searched the entire tree.

Efficiency

How a problem is represented greatly influences how long it takes to find a solution. You must consider two things. First, the nearer to the root you can prune the tree the greater the reduction in run time. Second, you should remember that whenever the validator function is called, all but the last element have already been validated.

Consider map coloring. You can color the states in any order you want. Suppose you order the states alphabetically. The algorithm would first color Alabama, then Arizona. Because these states are not adjacent, you would never be able to prune the tree at this level, since all possible colorings of these two states can lead to valid solutions. However, if you order the states by adjacency, so that Maine is colored first, followed by New Hampshire, you can prune at this level. Of the 16 nodes at level 2, four will be pruned, which removes over 1029 nodes from consideration.

Conclusion

Using my BackTrack class is straightforward. The hardest task is writing the validator function, but even this is easy, as the problem statement completely defines its functionality. I can typically whip up a solution in half an hour or less. After a few attempts I expect other users will be able to do the same.

Choosing the best algorithm for a combinatorial problem is beyond the scope of this paper. There are many combinatorial problems for which backtracking does not work, or does not work quickly enough. The best survey of these algorithms that I have found is the book Heuristics: Intelligent Search Strategies for Computer Problem Solving, by Judea Pearl [2]. While out of print, the book's clear presentation of the topic will more than repay the effort it may take to find it.

Even when backtracking is not the best choice, my class can still be useful. You can use it to unit test your specialized algorithm. Better yet, use BackTrack as a backup debug-only algorithm to double check the results of the specialized algorithm, using #ifdef #endif blocks to remove the code from your production builds. (This technique is discussed in Steve Maguire's Writing Solid Code [3].)

References

[1] Bjarne Stroustrup. The C++ Programming Language, 3rd Edition (Addison-Wesley, 1997), p. 514.

[2] Judea Pearl. Heuristics: Intelligent Search Strategies for Computer Problem Solving (Addison-Wesley, 1984).

[3] Steve Maguire. Writing Solid Code (Microsoft Press, 1993), pp. 33-38.


Roger Labbe is the C++ Simulation Manager for DCS Corporation in Virginia, where he develops and manages avionics simulations as well as flight planning software. He has previously developed embedded software for flight management computers..

February 2000/Solving Combinatorial Problems with STL and Backtracking/Listing 1

Listing 1: An STL-style backtracking functor

#ifndef BackTrack_h
#define BackTrack_h

template <class T, class I, class V>
class BackTrack {
public:

   // precondition: first <= last
   BackTrack(const T&  first, const T&  last);


   // Finds the next solution to the problem. Repeated calls 
   // will find all solutions to a problem if multiple solutions 
   // exist.
   // Returns true if a solution was found.
   //
   // Set first to true to get the first solution.
   //
   bool operator() (const I& begin, I end, bool& first);


private:
   // Finds the next valid sibling of the leaf (end-1). 
   // Returns true is if a valid sibling was found.
   bool FindValidSibling (const I& begin, const I& end);


   // Backtracks through the decision tree until it finds a node
   // that hasn't been visited. Returns true if an unvisited 
   // node was found.
   bool VisitNewNode (const I& begin, I& end);

   void CreateLeftLeaf (I& end);

   T left_child;
   T right_child;

   V IsValid;
};

template <class T, class I, class V>
BackTrack<T,I,V>::BackTrack(const T& first, const T& last) 
   : left_child (first), right_child (last)
{
}

template <class T, class I, class V>
bool BackTrack<T,I,V>::VisitNewNode(const I& begin, I& end)
{
   // ALGORITHM:
   //
   // 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.

   // Back up as long as the node is the rightmost child of 
   // its parent.
   while (end-begin > 0 && *(end-1) == right_child)
      --end;

   I back = end-1;
   if (end-begin > 0 && *back != right_child) {
      ++(*back);
      return true;
   } else
      return false;
}

template <class T, class I, class V> 
bool BackTrack<T,I,V>::FindValidSibling
(const I& begin, const I& end)
{
   // Note that on entry to this routine the leaf has not yet 
   // been used or tested for validity, so the leaf is 
   // considered a "sibling" of itself.

   I back = end-1;
   while (true) {
      if (IsValid (begin, end))
         return true;
      else if (*back != right_child)
         ++(*back);
      else
         return false;
   }
}

template <class T, class I, class V>
inline void BackTrack<T,I,V>::CreateLeftLeaf (I& end)
{
   *(end++) = left_child;
}

template <class T, class I, class V> 
bool BackTrack<T,I,V>::operator () 
(const I& begin, I end, bool& first)
{
   const int size = end - begin;

   // If first time, need to create a root.
   // Otherwise need to visit new node since vector
   // contains the last solution.
   if (first) {
      first = false;
      end = begin;
      CreateLeftLeaf (end);
   } else if (!VisitNewNode (begin, end))
      return false;

   while (true) {
      if (FindValidSibling (begin, end)) {
         if (end - begin < size)
            CreateLeftLeaf (end);
         else
            return true;

      } else if (!VisitNewNode (begin, end))
         return false; // the tree has been exhausted, 
                       // so no solution exists.
   }
}
February 2000/Solving Combinatorial Problems with STL and Backtracking/Listing 2

Listing 2: A program that colors a U.S. map with four colors, such that no adjacent states are the same color

#include <assert.h>

#include <functional>
#include <vector>

#include "BackTrack.h"


enum State
   {ME, NH, VT, MA, CT, RI, NY, PA, NJ, DE, MD, DC, 
    VA, NC, WV, SC, GA, FL, AL, TN, KY, OH, IN, MI, 
    MS, LA, AR, MO, IL, WI, IA, MN, ND, SD, NE, KS, 
    OK, TX, NM, CO, WY, MT, ID, UT, AZ, NV, CA, OR, WA};

const int NumberStates = 49;
const int MaxNeighbors = 8;

enum Color {Blue, Yellow, Green, Red};

inline Color& operator++ (Color& c)
{
   c = Color (c + 1);
   return c;
}

inline State& operator++ (State& c)
{
   c = State (c + 1);
   return c;
}

typedef std::vector<Color> Map;
typedef Map::iterator MapIter;


// store neighbor's of each state.
// Neighbor [i][0] == # of neighbors  of state i
// Neighbor [i][j] == jth neighbor of state i
State Neighbor [NumberStates][MaxNeighbors+1]; 

inline Connect (State s1, State s2)
{
   int count = ++Neighbor [s1][0];
   Neighbor [s1][count] = s2;

   count = ++Neighbor [s2][0];
   Neighbor [s2][count] = s1;

   assert (Neighbor [s1][0] <= MaxNeighbors);
   assert (Neighbor [s2][0] <= MaxNeighbors);
}


void BuildMap ()
{
   for (int i = 0; i < NumberStates; i++)
         Neighbor [i][0] = State(0);


   Connect (ME,NH);
   Connect (NH,VT); Connect (NH,MA);
   Connect (VT,MA); Connect (VT,NY);
   Connect (MA,NY); Connect (MA,CT); Connect (MA,RI);
   Connect (CT,RI); Connect (CT,NY);
   Connect (NY,NJ); Connect (NY,PA); Connect (NY,OH);
   Connect (PA,NJ); Connect (PA,DE); Connect (PA,MD); 
   Connect (PA,WV); Connect (PA,OH);

   // ... omitted to save space -- full source code available
   // on CUJ ftp site (see p. 3 for downloading instructions)

   Connect (UT,NV); Connect (UT,AZ);
   Connect (AZ,NV); Connect (AZ,CA);
   Connect (NV,OR); Connect (NV,CA);
   Connect (CA,OR);
   Connect (OR,WA);
}


struct ColorIsValid : 
   public std::binary_function<MapIter, MapIter, bool> 
{
   bool operator() (const MapIter& begin, const MapIter& end) 
   {
      State LastState = State (end-begin-1);
      Color LastColor = *(end-1);
      bool Valid = true;
      for (int i = 1; i <= Neighbor [LastState][0]; i++) {
         State NeighborState = Neighbor [LastState][i];
         if (NeighborState < LastState &&
             *(begin+NeighborState) == LastColor)
             return false;
      }
      return true;
   }
};



int main (int argc, char* argv [])
{
   Map tree (NumberStates);

   BackTrack <Color, MapIter, ColorIsValid> ColorMap (Blue, Red);
   BuildMap ();

   bool FirstTime = true;
   // find first 100 valid colorings of the U.S.
   for (int i = 0; i < 100; i++)
      bool Valid = 
         ColorMap (tree.begin(), tree.end(), FirstTime);

   return 0;
}

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.