|
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.
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:
We either travel from E to F and then to D.
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.
|
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 fromoriginationtodestinationinG(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 fromoriginationtodestinationinG;; if there is no path, the function producesfalse(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 onlo-originationstodestination;; if there is no path, the function producesfalse(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:
![[curriculum4a-Z-G-33.gif]](curriculum4a-Z-G-33.gif)
(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.
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
|
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
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.
|
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 sizenxn, ;; fill each position with indicesiandjwith(f i j)(define (build-board n f) ...) ;;board-ref : board N N -> boolean;; to access a position with indicesi,jon 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
![[curriculum4a-Z-G-34.gif]](curriculum4a-Z-G-34.gif)
![[curriculum4a-Z-G-35.gif]](curriculum4a-Z-G-35.gif)