Section 28

Algorithms that Backtrack

Solving problems does not always proceed on a direct route to the goal. Sometimes we make progress by pursuing one approach only to discover that we are stuck because we took a wrong turn. In those cases, we backtrack in our exploration and take a different turn at some branch, in the hope that it leads us to a solution. Algorithms can proceed like that. In the first subsection, we deal with an algorithm that can help us traverse a graph, which is of course the situation we just discussed. The second subsection is an extended exercise that uses backtracking in the context of chess.

28.1  Traversing Graphs

On occasion, we need to navigate through a maze of one-way streets. Or, we may wish to draw a graph of whom we consider a friend, whom they consider a friend, and so on. Or, we need to plan a route through a network of pipelines. Or, we ask the Internet to find some way to send a message from one place to another.

All these situations share a common element: a directed graph.

Specifically, there is always some collection of nodes and a collection of edges. The edges represent one-way connections between the nodes. Consider figure 76. The black bullets are the nodes; the arrows between them are the one-way connections. The sample graph consists of seven nodes and nine edges.

Now suppose we wish to plan routes in the graph of figure 76. For example, if we plan to go from C to D, the route is simple: it consists of the origination node C and the destination node D. In contrast, if we wish to travel from E to D, we have two choices:

  1. We either travel from E to F and then to D.

  2. Or, we travel from E to C and then to D.

For some nodes, however, it is impossible to connect them. In particular, it is impossible in our sample graph to move from C to G by following the arrows.

[curriculum4a-Z-G-33.gif]
Figure 76:  A directed graph

In the real world, graphs have more than just seven nodes and many more edges. Hence it is natural to develop functions that plan routes in graphs. Following the general design recipe, we start with a data analysis. Here is a compact representation of the graph in figure 76 using lists:

(define Graph 
  '((A (B E))
    (B (E F))
    (C (D))
    (D ())
    (E (C F))
    (F (D G))
    (G ())))

The list contains one list per node. Each of these lists starts with the name of a node followed by the list of its neighbors. For example, the second list represents node B with its two outgoing edges to E and F.

Exercise 28.1.1.   Translate the above definition into proper list form using list and proper symbols.

The data definition for node is straightforward: A node is a symbol.

Formulate a data definition for graphs with arbitrarily many nodes and edges. The data definition must specify a class of data that contains Graph.    Solution

Based on the data definitions for node and graph, we can now produce the first draft of a contract for find-route, the function that searches a route in a graph:

;; find-route : node node graph  ->  (listof node)
;; to create a path from origination to destination in G
(define (find-route origination destination G) ...)

What this header leaves open is the exact shape of the result. It implies that the result is a list of nodes, but it does not say exactly which nodes the list contains. To understand this aspect, we must study some examples.

Consider the first problem mentioned above. Here is an expression that formulates the problem in Scheme:

(find-route 'C 'D Graph)

A route from 'C to 'D consists of just two nodes: the origination and the destination node. Hence, we should expect the answer (list 'C 'D). Of course, one might argue that since both the origination node and the destination node are known, the result should be empty. Here we choose the first alternative since it is more natural, but it requires only a minor change of the final function definition to produce the latter.

Now consider our second problem, going from 'E to 'D, which is more representative of the kinds of problems we might encounter. One natural idea is to inspect all of the neighbors of 'E and to find a route from one of them to 'D. In our sample graph, 'E has two neighbors: 'C and 'F. Suppose for a moment that we didn't know the route yet. In that case, we could again inspect all of the neighbors of 'C and find a route from those to our goal. Of course, 'C has a single neighbor and it is 'D. Putting together the results of all stages shows that the final result is (list 'E 'C 'D).

Our final example poses a new problem. Suppose find-route is given the arguments 'C, 'G, and Graph. In this case, we know from inspecting figure 76 that there is no connecting route. To signal the lack of a route, find-route should produce a value that cannot be mistaken for a route. One good choice is false, a value that isn't a list and naturally denotes the failure of a function to compute a proper result.

This new agreement requires another change in our contract:

;; find-route : node node graph  ->  (listof node) or false
;; to create a path from origination to destination in G
;; if there is no path, the function produces false
(define (find-route origination destination G) ...)

Our next step is to understand the four essential pieces of the function: the ``trivial problem'' condition, a matching solution, the generation of a new problem, and the combination step. The discussion of the three examples suggests answers. First, if the origination argument of find-route is equal to its destination, the problem is trivial; the matching answer is (list destination). Second, if the arguments are different, we must inspect all neighbors of origination in graph and determine whether there is a route from one of those to destination.

Since a node can have an arbitrary number of neighbors, this task is too complex for a single primitive. We need an auxiliary function. The task of the auxiliary function is to consume a list of nodes and to determine for each one of them whether there is a route to the destination node in the given graph. Put differently, the function is a list-oriented version of find-route. Let us call this function find-route/list. Here is a translation of this informal description into a contract, header, and purpose statement:

;; find-route/list : (listof node) node graph  ->  (listof node) or false
;; to create a path from some node on lo-originations to destination
;; if there is no path, the function produces false
(define (find-route/list lo-originations destination G) ...)

Now we can write a first draft of find-route as follows:

(define (find-route origination destination G)
  (cond
    [(symbol=? origination destination) (list destination)]
    [else ... (find-route/list (neighbors origination G) destination G) ...]))

The function neighbors generates a whole list of problems: the problems of finding routes from the neighbors of origination to destination. Its definition is a straightforward exercise in structural processing.

Exercise 28.1.2.   Develop the function neighbors. It consumes a node n and a graph g (see exercise 28.1.1) and produces the list of neighbors of n in g.    Solution

Next we need to consider what find-route/list produces. If it finds a route from any of the neighbors, it produces a route from that neighbor to the final destination. But, if none of the neighbors is connected to the destination, the function produces false. Clearly, find-route's answer depends on what find-route/list produces. Hence we should distinguish the answers with a cond-expression:

(define (find-route origination destination G)
  (cond
    [(symbol=? origination destination) (list destination)]
    [else (local ((define possible-route 
		    (find-route/list (neighbors origination G) 
                                     destination G)))
	    (cond
	      [(boolean? route) ...]
	      [else ; (cons? route) 
		...]))]))

The two cases reflect the two kinds of answers we might receive: a boolean or a list. If find-route/list produces false, it failed to find a route from origination's neighbors, and it is therefore impossible to reach destination at all. The answer in this case must therefore be false. In contrast, if find-route/list produces a list, the answer must be route from origination to destination. Since possible-route starts with one of origination's neighbors, it suffices to add origination to the front of possible-route.

;; find-route : node node graph  ->  (listof node) or false
;; to create a path from origination to destination in G
;; if there is no path, the function produces false
(define (find-route origination destination G)
  (cond
    [(symbol=? origination destination) (list destination)]
    [else (local ((define possible-route 
		    (find-route/list (neighbors origination G) destination G)))
	    (cond
	      [(boolean? possible-route) false]
	      [else (cons origination possible-route)]))]))

;; find-route/list : (listof node) node graph  ->  (listof node) or false
;; to create a path from some node on lo-Os to D
;; if there is no path, the function produces false
(define (find-route/list lo-Os D G)
  (cond
    [(empty? lo-Os) false]
    [else (local ((define possible-route (find-route (first lo-Os) D G)))
	    (cond
	      [(boolean? possible-route) (find-route/list (rest lo-Os) D G)]
	      [else possible-route]))]))

Figure 77:  Finding a route in a graph

Figure 77 contains the complete definition of find-route. It also contains a definition of find-route/list, which processes its first argument via structural recursion. For each node in the list, find-route/list uses find-route to check for a route. If find-route indeed produces a route, that route is the answer. Otherwise, if find-route fails and produces false, the function recurs. In other words, it backtracks its current choice of a starting position, (first lo-Os), and instead tries the next one in the list. For that reason, find-route is often called a BACKTRACKING ALGORITHM.

Backtracking in the Structural World: Intermezzo 3 discusses backtracking in the structural world. A particularly good example is exercise 18.1.13, which concerns a backtracking function for family trees. The function first searches one branch of a family tree for a blue-eyed ancestor and, if this search produces false, it searches the other half of the tree. Since graphs generalize trees, comparing the two functions is an instructive exercise. 

Last, but not least, we need to understand whether the function produces an answer in all situations. The second one, find-route/list, is structurally recursive and therefore always produces some value, assuming find-route always does. For find-route the answer is far from obvious. For example, when given the graph in figure 76 and two nodes in the graph, find-route always produces some answer. For other graphs, however, it does not always terminate.

Exercise 28.1.3.   Test find-route. Use it to find a route from A to G in the graph of figure 76. Ensure that it produces false when asked to find a route from C to G.    Solution

Exercise 28.1.4.   Develop the function test-on-all-nodes, which consumes a graph g and tests find-route on all pairs of nodes in g. Test the function on Graph.    Solution

[curriculum4a-Z-G-34.gif]

Figure 78:  A directed graph with cycle

Consider the graph in figure 78. It differs radically from the graph in figure 76 in that it is possible to start a route in a node and to return to the same node. Specifically, it is possible to move from B to E to C and back to B. And indeed, if applied find-route to 'B, 'D, and a representation of the graph, it fails to stop. Here is the hand-evaluation:

  (find-route 'B 'D Cyclic-graph)
= ... (find-route 'B 'D Cyclic-graph) ...
= ... (find-route/list (list 'E 'F) 'D Cyclic-graph) ...
= ... (find-route 'E 'D Cyclic-graph) ...
= ... (find-route/list (list 'C 'F) 'D Cyclic-graph) ...
= ... (find-route 'C 'D Cyclic-graph) ...
= ... (find-route/list (list 'B 'D) 'D Cyclic-graph) ...
= ... (find-route 'B 'D Cyclic-graph) ...
= ... 

where Cyclic-Graph stands for a Scheme representation of the graph in figure 78. The hand-evaluation shows that after seven applications of find-route and find-route/list the computer must evaluate the exact same expression from which we started. Since the same input produces the same output and the same behavior for functions, we know that the function loops forever and does not produce a value.

In summary, if some given graph is cycle-free, find-route produces some output for any given inputs. After all, every route can only contain a finite number of nodes, and the number of routes is finite, too. The function therefore either exhaustively inspects all solutions starting from some given node or finds a route from the origination to the destination node. If, however, a graph contains a cycle, that is, a route from some node back to itself, find-route may not produce a result for some inputs. In the next part, we will study a programming technique that helps us finds routes even in the presence of cycles in a graph.

Exercise 28.1.5.   Test find-route on 'B, 'C, and the graph in figure 78. Use the ideas of section 17.8 to formulate the tests as boolean-valued expression.    Solution

Exercise 28.1.6.   Organize the find-route program as a single function definition. Remove parameters from the locally defined functions.    Solution

28.2  Extended Exercise: Checking (on) Queens

A famous problem in the game of chess concerns the placement of queens on a board. For our purposes, a chessboard is a ``square'' of, say, eight-by-eight or three-by-three tiles. The queen is a game piece that can move in a horizontal, vertical, or diagonal direction arbitrarily far. We say that a queen threatens a tile if it is on the tile or can move to it. Figure 79 shows an example. The solid disk represents a queen in the second column and sixth row. The solid lines radiating from the disk go through all those tiles that are threatened by the queen.

[curriculum4a-Z-G-35.gif]
Figure 79:  A chessboard with a single queen

The queen-placement problem is to place eight queens on a chessboard of eight-by-eight tiles such that the queens on the board don't threaten each other. In computing, we generalize the problem of course and ask whether we can place n queens on some board of arbitrary size m by m.

Even a cursory glance at the problem suggests that we need a data representation of boards and some basic functions on boards before we can even think of designing a program that solves the problem. Let's start with some basic data and function definitions.

Exercise 28.2.1.   Develop a data definition for chessboards.

Hint: Use lists. Represent tiles with true and false. A value of true should indicate that a position is available for the placement of a queen; false should indicate that a position is occupied by, or threatened by, a queen.    Solution

Next we need a function for creating a board and another one for checking on a specific tile. Following the examples of lists, let's define build-board and board-ref.

Exercise 28.2.2.   Develop the following two functions on chessboards:

;; build-board : N (N N  ->  boolean)  ->  board
;; to create a board of size n x n, 
;; fill each position with indices i and j with (f i j)
(define (build-board n f) ...)

;; board-ref : board N N  ->  boolean
;; to access a position with indices i, j on a-board
(define (board-ref a-board i j) ...)

Test them rigorously! Use the ideas of section 17.8 to formulate the tests as boolean-valued expressions.    Solution

In addition to these generic functions on a chessboard representation, we also need at least one function that captures the concept of a ``threat'' as mentioned in the problem statement.

Exercise 28.2.3.   Develop the function threatened?, which computes whether a queen can reach a position on the board from some given position. That is, the function consumes two positions, given as posn structures, and produces true if a queen on the first position can threaten the second position.

Hint: The exercise translate the chess problem of ``threatening queens'' into the mathematical problem of determining whether in some given grid, two positions are on the same vertical, horizontal, or diagonal line. Keep in mind that each position belongs to two diagonals and that the slope of a diagonal is either +1 or -1.    Solution

Once we have data definitions and functions for the ``language of chessboards,'' we can turn our attention to the main task: the algorithm for placing a number of queens on some given board.

Exercise 28.2.4.   Develop placement. The function consumes a natural number and a board and tries to place that many queens on the board. If the queens can be placed, the function produces an appropriate board. If not, it produces false.    Solution