>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..
