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 numbersa1 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 thatA(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 formatc 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 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 Main
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