Structure and Interpretation of Computer Programs (26 page)

The
“eight-queens puzzle” asks how to place eight queens on a
chessboard so that no queen is in check from any other (i.e., no two
queens are in the same row, column, or diagonal). One possible
solution is shown in figure 
2.8
. One way to solve the
puzzle is to work across the board, placing a queen in each column.
Once we have placed
k
- 1 queens, we must place the
k
th queen in a
position where it does not check any of the queens already on the
board. We can formulate this approach recursively: Assume that we
have already generated the sequence of all possible ways to place
k
- 1 queens in the first
k
- 1 columns of the board. For each of
these ways, generate an extended set of positions by placing a queen
in each row of the
k
th column. Now filter these, keeping only
the positions for which the queen in the
k
th column is safe with
respect to the other queens. This produces the sequence of all ways
to place
k
queens in the first
k
columns. By continuing this
process, we will produce not only one solution, but all solutions to
the puzzle.

We implement this solution as a procedure
queens
, which returns
a sequence of all solutions to the problem of placing
n
queens on an
n
×
n
chessboard.
Queens
has an internal procedure
queen-cols
that returns the sequence of all ways to place queens in
the first
k
columns of the board.

(define (queens board-size)
  (define (queen-cols k)  
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

In this procedure
rest-of-queens
is a way to place
k
- 1 queens
in the first
k
- 1 columns, and
new-row
is a proposed row in
which to place the queen for the
k
th column. Complete the program
by implementing the representation for sets of board positions,
including the procedure
adjoin-position
, which adjoins a new row-column
position to a set of positions, and
empty-board
, which
represents an empty set of positions. You must also write the
procedure
safe?
, which determines for a set of positions,
whether the queen in the
k
th column is safe with respect to the
others. (Note that we need only check whether the new queen is
safe – the other queens are already guaranteed safe with respect to
each other.)

Exercise 2.43.
  Louis Reasoner is having a terrible time doing exercise 
2.42
. His
queens
procedure seems to work, but it runs extremely slowly.
(Louis never does manage to wait long enough for it to solve even the
6× 6 case.) When Louis asks Eva Lu Ator for help, she points
out that he has interchanged the order of the nested mappings in the
flatmap
, writing it as

(flatmap
 (lambda (new-row)
   (map (lambda (rest-of-queens)
          (adjoin-position new-row k rest-of-queens))
        (queen-cols (- k 1))))
 (enumerate-interval 1 board-size))

Explain why this interchange makes the program run slowly. Estimate
how long it will take Louis's program to solve the eight-queens
puzzle, assuming that the program in exercise 
2.42
solves
the puzzle in time
T
.

This section presents a simple language for drawing
pictures that illustrates the
power of data abstraction and closure,
and also exploits higher-order procedures in
an essential way. The language
is designed to make it easy to experiment with patterns
such as the ones in figure 
2.9
, which are
composed of repeated elements that are shifted and scaled.
²²
In this language,
the data objects being combined
are represented as procedures rather than as list structure.
Just as
cons
, which satisfies the
closure property,
allowed us to easily build arbitrarily complicated
list structure, the operations in this language, which also
satisfy the closure property, allow us to easily build
arbitrarily complicated patterns.

Figure 2.9:
  Designs generated with the picture language.

When we began our study of programming in
section 
1.1
, we emphasized the
importance of describing a language by focusing on the language's
primitives, its means of combination, and its means of abstraction.
We'll follow that framework here.

Part of the elegance of this picture language is that there is
only one kind of element, called a
painter
. A painter
draws an image that is shifted and scaled to fit within a designated
parallelogram-shaped frame. For example, there's a primitive painter
we'll call
wave
that makes a crude line drawing, as
shown in figure 
2.10
.
The actual shape of the drawing depends on the frame – all
four images in figure 
2.10
are produced by the same
wave
painter, but with respect to four different frames. Painters
can be more elaborate than this:
The primitive
painter called
rogers
paints a picture of MIT's founder,
William Barton Rogers, as shown in figure 
2.11
.
²³
The four images in figure 
2.11
are drawn with respect to the same four frames
as the
wave
images in figure 
2.10
.

To combine images,
we use various operations that construct new painters
from given painters.
For example, the
beside
operation takes two painters and produces a new,
compound painter that draws the first painter's image in the left half
of the frame and the second painter's image in the right half of the frame.
Similarly,
below
takes two painters and produces a compound
painter that draws the first painter's image below the second
painter's image.
Some operations transform a single painter to produce
a new painter. For example,
flip-vert
takes a painter and
produces a painter that draws its image upside-down, and
flip-horiz
produces a painter that draws the original
painter's image left-to-right reversed.

Figure 2.10:
  Images produced by the
wave
painter, with respect
to four different frames. The frames, shown with dotted lines, are not
part of the images.

Figure 2.11:
  Images of William Barton Rogers, founder and first
president of MIT, painted with respect to the same four frames as in
figure 
2.10
(original image reprinted with the permission
of the MIT Museum).