G12FCO -- Formal Computation, lecture 8

G12FCO -- Formal Computation

Lecture 8 -- Eight Queens and other backtracks

The Eight Queens Problem

The Eight Queens problem is to place eight Queens on a chessboard so that no two attack each other -- that is, so that no two are on the same rank, or the same file, or the same diagonal. The left diagram shows one way of doing this; the right diagram shows a way of getting stuck -- we've placed five Queens, but there is no way of continuing to the next row (or column).

So, our usual style of algorithm is in danger of not working. We would like to set up an invariant something like

the first k columns contain Queens no two of which attack each other

which we can trivially initialise with k = 0 and then try to extend by increasing k. The first example shows that this could work, the second shows that it need not. So our algorithm has to be more tentative. We must be prepared for a given configuration not to be extensible. In that case, we must backtrack to a previous value of k and try to extend that in a different way; there may be no different way, in which case we must backtrack again, and perhaps yet again.

Writing this algorithm down is, however, surprisingly hard unless you are happy with recursion. The problem is that you need a sophisticated structure in the program to control whether we are looking to extend the current situation forwards or to backtrack, and after backtracking whether we are now going forwards afresh or re-backing, etc. This is exactly what recursion does best. Let's see:

	procedure place (k)
	  # k-1 Queens have already been placed, with the jth Queen in
	  #	column j and row p[j], for 1 <= j < k.  We try to
	  #	place the kth Queen.
	  if k = 9
	    then for i = 1 to 8 do print p[i] endfor, print newline
	    else for i = 1 to 8 do
	            p[k] = i
	            if "this configuration is OK" then place (k+1) endif
	         endfor
	  endif

and all we have to do to turn this into a complete program for this problem is to expand the test this configuration is OK and then to initiate the whole process by calling place (1). [As given, this code will print all 92 different solutions; if you want only the first, then you must exit after printing it.] The test is a "small matter of programming"; you must test to see whether the new Queen in column k and row i is in the same row or a same diagonal as any of the previous Queens. This is not particularly trivial, but nor is it difficult, and it's not really relevant to our present purpose.

Note that the backtracking has virtually disappeared from the program; it is implemented automatically by the recursion. As each instantiation of place is completed, we automatically backtrack to the place from which it was called, part-way through the internal loop.

This problem is really just a puzzle. It obviously generalises to N Queens on an N×N board with almost no changes. As N gets large, the time taken to complete the search increases dramatically; we will be looking at a significant fraction of the N^N different ways of assigning values between 1 and N to the elements of p. But for N no more than about 12, it works very well.

There are zillions of other problems which are also, it seems, best solved by a backtracking algorithm. We look at a few representative cases.

Packing problems

In these, the typical problem is that we have some `containers' of given sizes [often, all the same], and we need to know whether a given set of objects can be packed into them. In two or three dimensions, this can be a difficult problem even with only one container [think of packing a suitcase -- or a car boot! -- to go on holiday]. In one dimension, you might expect it to be a lot easier; but it isn't.

Suppose, for example, we have containers of size 100, and our first few objects have sizes 50, 40, 30 and 20. We put the 50 into the first container, and now want to place the 40. Do we [`greedily'] place it in the first space that is big enough? If so, we have a space of 10 left over, that may be completely wasted if the objects we haven't yet seen are all bigger than 10; for example, if the remaining objects are 44 and 11, we will need a third container where two should have been sufficient. On the other hand, if we place the 40 in the second container, this enables us to fill the first container exactly with the 30 and 20, but leaves the second container perhaps over-full. Suppose, for example that the next two objects are of size 65; then 50+30+20;40;65;65 needs four containers where 50+40;30+65;20+65 needs only three.

A more sophisticated version of this example can be used to show that none of a wide range of plausible ideas always gives the best solution. It seems that the best solution can be found only by trial and error; or, in other words, by trying a placement and being prepared to backtrack it to try a different placement.

Computer operating systems have to solve a problem very like this one when they try to assign memory to a number of concurrent processes, while other processes are `swapped out' to disc to await their chance to run. Another practical application is the cloth-cutting problem -- you have a design for an item [say] of clothing, and you want to cut up the minimum length of cloth to make up your design [or to stamp out components from a minimum area of sheet metal, or whatever]. Yet another similar problem is the fair division problem; you have a number of children at a party and a pile of presents [enough for several per child], and you have to divide the presents so that the gap between `richest' and `poorest' is as small as possible. [Practical parents resolve this by having enough presents to give every child exactly the same.] A similar problem is dividing a boat-race crew into port and starboard sides with roughly equal pull.

Route problems

Given some villages and a network of roads, we've already solved the `minimum spanning tree' problem. Another relatively easily solved problem is the Euler tour -- is it possible to traverse all the roads of the network [perhaps visiting some villages several times] without using any road twice, finishing back where you started? For a connected network, the answer is yes if and only if there are an even number of roads out of each village, so there is an easy test to see if it's possible, and the theory of Euler circuits provides a reasonably simple constructive way of finding such a tour. The theory remains simple if all of the roads are one-way; in this case, the number of roads in to each village must equal the number of roads out. But if some of the roads are one-way, then there is almost no known theory, and we must resort to trial and error.

Two other important problems are much harder. The Hamiltonian circuit problem asks whether there is a route which visits every village exactly once, again finishing back where you started. The Travelling Salesman problem asks for the shortest route, again finishing back where you started, which visits every village at least once. We shall see later that these two problems are very closely related. Current theory suggests that we will again have to resort to trial and error. In other words, for Hamilton's problem, we will sometimes have to guess which village to visit next, and our guess will sometimes be wrong, so that we find ourselves in a dead-end, and have to retrace our steps and try a different guess.

Playing games

We're all familiar with the sort of analysis of games [chess, draughts, go, ludo, whatever] that runs, very crudely "If I go here, then he can go there, and then I can do this and he does that and so-and-so happens". At the heart of almost every game-playing program, and certainly every competent chess-playing program, is some backtracking code that implements this idea. Very schematically, this will look somewhat like:

	to analyse the current position:
	   if position is terminal
		then return result of game
		else construct list of legal moves
		     for each move on this list
			do play this move
			   analyse the resulting position
			   unplay this move
		     endfor
	   endif

If your program is exactly this, then you will wait an awfully long time for it to find you a good move in any game more complicated than noughts-and-crosses; so a great deal of optimisation is needed for a practical program! [This optimisation is discussed in the Game Theory module.] As before, the backtracking is implicit in the recursion [in this case, the instruction to analyse inside the for-loop].

Discussion

All backtracking is prone to `combinatorial explosion', that is, the phenomenon of exponential growth of the number of possible trials. We'll see how devastating this is in the next lecture. Nevertheless, some of these algorithms often work well in practice. This can be because a `greedy' guess is often correct, and it is only in `pathological' cases that delicate decisions need to be made. In other cases, it can be because a wrong guess can be detected and aborted early, using `branch and bound' techniques. This simply means that after completing the first set of guesses, we have a current `record' [or bound] against which to measure later sets, and we can [and should] backtrack as soon as it becomes clear that our current set [or branch] of guesses is not going to beat the record.

Another point to note, which we shall return to later, is that many of these problems can be solved by lucky guesses. If you place Queens at random on the chessboard, then you may strike lucky, and hit a placement that satisfies the conditions of the puzzle. If so, then you can easily test that your solution is good. Similarly, if you simply wander at random around some villages, then you may accidentally complete a Hamiltonian tour. If so, then you can easily show that you have done so. In these and other cases, finding a solution seems to be hard, but verifying the correctness of a proposed solution is easy.

top of page

G12FCO home page. border=0

Previous lecture. border=0

Next lecture. border=0

Coursework 2 .