<< Computer AlgorithmsUse  Ctrl +  or    to enlarge or reduce text size.

An All Purpose Backtracking Engine
– Illustrated by Coloring Maps –


We describe here a general purpose backtracking engine. To show how it works we use it to color a map as in the “four color problem.”

Sometimes the only way to solve a problem is by exhaustive search, that is, going through every possibility and testing them one by one.

Suppose the problem can be expressed like this:  Find all sequences of  n  numbers
a1 a2 a3 ... an
where each number lies within a certain range, say from 1 to p, and the sequence satisfies a certain condition.

The map coloring problem can be put in that form. By “color a map” we mean color its regions – counties, states, countries, whatever – so that two regions that abut one another get different colors. (The map is assumed to be planar and each of its regions connected.) Here’s how the problem would look using the general scheme above:  n is the number of regions which are numbered 1 to n, and ai is the color of the ith region. The range of each  ai  is restricted by the number of available colors, which are numbered from 1 to p.

One way to solve the problem is to assign all  n  of the ‘a’ every possible combination of values within range, checking each time to see if together they meet the condition. We might have to test an enormous number of possibilities:  if each entry could independently take on p values there would be  p·p·p· ... ·p  =  pn  of them.

Backtracking is another approach. It can be used if a partial test and solution makes sense. The idea is to “grow” a successful sequence from left to right, testing along the way, instead of setting it all at once and testing. For typographical reasons, instead of  ai  we write A(i).

Given the sequence up to a certain point, we find all possibilities for the next number. That is, given  A(1 to k)  we find all possible  A(k+1)  so that tacking it on doesn’t contradict the condition.  If we can’t find any, we “backtrack,” that is, reject  A(k)  and go back to  A(1 to k-1).  Then we continue checking as before.

Thus as we grow A – starting from a valid A(1) – we determine as soon as possible if it is doomed to fail, and thus avoid testing many of the  pn  possibilities using the first approach.

In the four color problem, if we have colored k of the regions as the start of a possibly valid map coloring, we then try to color the  k+1st  region so that it differs from all the regions it abuts. If it can’t be done (the abutting regions use up all the available colors) then the coloring for the earlier k regions cannot begin a valid coloring. So we backtrack to  A(1) ... A(k-1)  and try again.

Instead of going from  k  →  k+1  we will go from  k – 1  →  k  which will make the coding a bit simpler.  In detail:  Assume we have A(i) up to but not including  k.
A(1)  A(2)  ...  A(k-1)
We want a routine called Backtrack that keeps a stack of possibilities for each position from 1 to k – 1. When Backtrack needs a list of all possible candidates for A(k) it goes to a routine called FindCandidates.

FindCandidates finds all X such that
A(1)  A(2)  ...  A(k-1)  X
doesn’t contradict the condition of the problem, and places them at the end of the stack along with a count of how many there are.

If there are no such X, Backtrack “backtracks” by decrementing  k  and removing A(k-1) from its list of possibilities for position  k – 1  since  A(1 to k-1)  cannot be the beginning of a solution.

The stack has the format
c c c c c c c H c c c c c c c c c c c c c c c c c H c c c c c c c c c c c c c H ...
where the  kth  block of c’s  are candidates for  A(k),  and at the end of each block  H  tells how many there are.  (We are using the format described by Herbert Wilf and Albert Nijenhuis.)

Let M be the location of the last item on the stack. We can remove a block  “ccccccccN”  by simply decreasing M so it points to the number before that block.

Thus Backtrack searches. After incrementing k it goes to FindCandidates which either adds possibilities to the stack or indicates that there aren’t any and then returns to Backtrack.  Backtrack keeps going until  k = n.

At that point we can do whatever we want with that particular solution  A(1 to n),  perhaps do other testing and winnowing, or track the minimum of a function of  A(1 to n),  or, as in the example below, just print it out.

Then Backtrack can continue to try to find other solutions using its stack of possibilities. The stack length bobbles up and down, at first mostly up, then mostly down. When the stack is empty Backtrack is done, it has found all possible solutions.

Or, if we’re interested in just finding one solution instead of all solutions, we can have Backtrack stop after finding the first.

Given a map and a palette of so many colors, the program below lists all possible colorings of the map using up to that many colors – and finds them using the backtrack method just described. It is written for PBCC and can be modified for Visual Basic, FORTRAN and any other BASIC-like compiler.

According to the “Four Color Theorem” a palette of only four colors will always suffice to color the map.
%nstack = 1000                'initial stack limit
' Represent the available colors by the numbers 1, 2, 3, 4, ..., p.
' Represent the regions of the map by the numbers 1, 2, 3, 4, 5, ..., N.
' Represent how the regions relate to each other by the matrix
' abut()  where
' abut(i,j) tells whether or not regions i and j are next to one another.
' Start off by coloring region 1 the color 1 and leave it that way.

Function PBMain
 Local N As Long              'number of regions on the map
 Local p As Long              'number of colors available
 Local i, j As Long           'general indices
 Local count As Long          'number of colorings
'-------------------------------------------------
 Local Kbt As Long            'one more than the length of partial array A()
 Local Mbt As Long            'current length of the stack
 Local nstack As Long         'maximum size of stack
 nstack = %nstack             'initial maximum size of stack
 Dim Stack(nstack) As Long    'the backtrack stack
 Local nc As Long             'number of candidates in a block
 Local m0 As Long             'Mbt saved
'--------------------------------------------------

 'Example map:  6 regions as follows
 '
 '             .------------------.
 '             |                  |
 '       .--------------.    1    |
 '       |              |         |
 '       |      2       |-----.   |
 '       |              |     |   |
 '       |------.-------|     |   |
 '       |      |       |     |   |
 '   .---|  3   |   4   |  5  |   |
 '   |   |      |       |     |   |
 '   |   |------·-------|     |   |
 '   |   |              |     |   |
 '   |   |      6       |-----·   |
 '   |   |              |         |
 '   |   ·--------------·         |
 '   |                            |
 '   ·----------------------------·

 N = 6      'number of regions   <-- change to suit
 Dim abut(N,N) As Long
 Dim A(N) As Long
 Dim colour(N) As Long         'used by FindCandidates
 ' Adjacency matrix for the above map.  We need only
 ' specify the non-zero abut(i,j) with i < j.  The
 ' program will make it symmetric.
 abut(1,2) = 1                 ' <--
 abut(1,3) = 1                 ' <--
 abut(1,5) = 1                 ' <--
 abut(1,6) = 1                 ' <--
 abut(2,3) = 1                 ' <--
 abut(2,4) = 1                 ' <--
 abut(2,5) = 1                 ' <--
 abut(3,4) = 1                 ' <--
 abut(3,6) = 1                 ' <--
 abut(4,5) = 1                 ' <--
 abut(4,6) = 1                 ' <--
 abut(5,6) = 1                 ' <--

 'fill in the reverse i,j automatically
 For i = 1 To N                'make abut() symmetric
 For j = i + 1 To N
  abut(j,i) = abut(i,j)
 Next
 Next

 Dim A(N) As Long              'A(i) is the color of region i
'--------------------------------------------------

 Do                'let user try various palette sizes p

  Input "Enter the size of the palette (eg 4): "; p
  If p <= 0 Then Exit Function
  count = 0
  Mbt = 0
  Kbt = 1

' Given a partial map coloring A(i) for regions i
' from 1 to Kbt - 1,  what are the possible colors
' for region Kbt, that is the color A(Kbt) ?
'
' Answer: Any color q (between 1 and p inclusive)
' so that there is no region i < Kbt  abutting
' region Kbt (that is, abut(i,Kbt) = 1) has that
' color (that is, A(i) = q).

FindCandidates:
  If Mbt + p + 2 >= nstack Then    'expand the stack space if necessary
   nstack = Mbt + p + 2
   ReDim Preserve stack(nstack)
  End If
  '-----------------------------
  For i = 1 To p                   'colors
   colour(i) = 1                   'start with all are possible
  Next
  For i = 1 To Kbt - 1             'regions so far
   If abut(i,Kbt) Then colour(A(i)) = 0  'this one is impossible
  Next
  m0 = Mbt
  For i = 1 To p
   If colour(i) Then
    Incr Mbt                       '* add possibility to stack *
    stack(Mbt) = i                 '*                          *
   End If
  Next
  Incr Mbt                         '* record how many we added *
  stack(Mbt) = Mbt - m0 - 1        '*                          *
'--------------------------------------------------

 ' This part is a general purpose backtracking engine.
 ' In general replace the section "ProcessArray", which
 ' in this example just prints it out, with whatever
 ' you want to do with A().  That might involve further
 ' testing and winnowing.

Backtrack:
  Do
   nc = stack(Mbt)          'how many candidates
   Decr Mbt
   If nc Then               'something there?
    A(Kbt) = Stack(Mbt)     'try it
    Stack(Mbt) = nc - 1     'one less candidate
    If Kbt = N Then
     GoTo ProcessArray      'have a complete A()
    Else
     Incr Kbt               'next stage
     GoTo FindCandidates    'find the possibilities
    End If
   Else
    Decr Kbt                'backtrack
   End If
  Loop Until Kbt = 0        'nothing to be tested
  GoTo Done
'--------------------------------------------------

ProcessArray:
  Incr count
  For i = 1 To N            'We'll just print it out.
   Print A(i);
  Next
  Print                     'Could stop here if want only
  GoTo Backtrack            'one solution rather than all.
'--------------------------------------------------

Done:
  Print
  Print count; "ways using"; p; "colors"
  Print

 Loop
End Function