Structure and Interpretation of Computer Programs

which is a sequence with one item, namely the set with no elements. The 

remove

 procedure used in 

permutations

 returns all the items in a given sequence except for a given item. This can be

expressed as a simple filter: 

(define (remove item sequence)

  (filter (lambda (x) (not (= x item)))

          sequence))

Exercise 2.40.  Define a procedure 

unique-pairs

 that, given an integer n, generates the sequence

of pairs (i,j) with 1< j< i< n. Use 

unique-pairs

 to simplify the definition of 

prime-sum-pairs

given above. 

Exercise 2.41.  Write a procedure to find all ordered triples of distinct positive integers i, j, and k less

than or equal to a given integer n that sum to a given integer s. 

Exercise 2.42.  

Figure 2.8:  A solution to the eight-queens puzzle.

Figure 2.8:  A solution to the eight-queens puzzle.

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 kth 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 kth column. Now filter these, keeping only the

positions for which the queen in the kth 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 kth 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 kth 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. 

2.2.4  Example: A Picture Language

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.

22

 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.

Figure 2.9:  Designs generated with the picture language.

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.

23

 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.

---