<< Computer Algorithms | Use Ctrl + or – to enlarge or reduce text size. |

– 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

a_{1} a_{2} a_{3} ... a_{n}

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 a

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 = p

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 a

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 p

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+1

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