SICP 2.42 & 2.43: The N Queens Problem

From SICP section 2.2.3 Sequences as Conventional Interfaces

The eight queens puzzle is the problem of placing eight queens on an 8x8 chess board so that no two queens attack each other. A solution requires that no two queens share the same row, column, or diagonal. One possible solution (there are 92) is shown in the figure below.



The eight queens puzzle is an example of the more general n queens problem of placing n queens on an nxn chessboard. SICP suggests that one way to solve the puzzle is to work across the board, placing a queen in each column. Once k - 1 queens are placed, the kth queen must be placed in a position where it is not in check from any of the queens already on the board. This approach can be formulated 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.

Exercise 2.42 implements a partial solution as the procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an nxn board. The internal procedure queen-cols 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 the parameter new-row is a proposed row in which to place the queen for the kth column.

Our task is to 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. (Note that the word position in this problem means the row and column of a single queen, not the placement of all pieces on the board, as is the normal use of the word position in chess terminology. Here the plural form positions is used to indicate the position of all the queens on a single board. A set of positions represents one solution to the problem.) We 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.

Since a position is just a row-column pair, we can use what should by now be the familiar method for representing pairs.

(define (make-position row col)
   (cons row col))

(define (position-row position)
   (car position))

(define (position-col position)
   (cdr position))

We can represent an empty board with null, and adjoin a new position to a board using list operations.

(define empty-board null)

(define (adjoin-position row col positions)
   (append positions (list (make-position row col))))

A queen is safe if no other queen is in the same row, column, or diagonal. Since we're only placing one queen in each column at a time, we can skip checking the column.

(define (safe? col positions)
   (let ((kth-queen (list-ref positions (- col 1)))
         (other-queens (filter (lambda (q)
                                 (not (= col (position-col q))))
                               positions)))
   (define (attacks? q1 q2)
     (or (= (position-row q1) (position-row q2))
         (= (abs (- (position-row q1) (position-row q2)))
            (abs (- (position-col q1) (position-col q2))))))

   (define (iter q board)
     (or (null? board)
         (and (not (attacks? q (car board)))
              (iter q (cdr board)))))
   (iter kth-queen other-queens)))

The safe? procedure starts be defining the symbols kth-queen and other-queens. We use the list-ref procedure introduced in SICP section 2.2.1 to separate the kth queen from the rest of the board. Next we define an attacks? procedure that takes two queens and returns true if they are in the same row or on the same diagonal. Then we define an iterative helper procedure to check and see if the kth queen attacks any of the others.

After adding in the definitions for accumulate, flatmap, and enumerate-interval given earlier in the text, we can finally test our implementation of queens.

> (queens 1)
(((1 . 1)))
> (queens 2)
()
> (queens 3)
()

So far, so good. There is only one solution to the puzzle for a 1x1 board, and no possible solutions for 2x2 and 3x3 boards.

> (queens 4)
(((2 . 1) (4 . 2) (1 . 3) (3 . 4)) ((3 . 1) (1 . 2) (4 . 3) (2 . 4)))

The two solutions given for a 4x4 board are illustrated below.




For the remaining tests, we'll just show how many distinct solutions queens comes up with instead of listing them all. You can check that the number of solutions matches those given in the Online Encyclopedia of Integer Sequences A000170.

> (length (queens 5))
10
> (length (queens 6))
4
> (length (queens 7))
40
> (length (queens 8))
92
> (length (queens 9))
352
> (length (queens 10))
724

Exercise 2.43 gives the following alternate implementation for a portion of the queens procedure above.

(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))

This new implementation works, but it runs extremely slowly because the order of nested mappings in flatmap has been swapped. Our task is to explain why this interchange makes the program run slowly, and to estimate how long it will take the new implementation to solve the eight queens puzzle assuming that the original implementation solved the puzzle in time T.

In the original solution, queen-cols is called once for each column in the board. This is an expensive procedure to call, since it generates the sequence of all possible ways to place k queens in k columns. By moving queen-cols so it gets called by flatmap, we're transforming a linear recursive process to a tree-recursive process. The flatmap procedure is called for each row of the kth column, so the new procedure is generating all the possible solutions for the first k - 1 columns for each one of these rows.

We learned back in section 1.2.2 that a tree-recursive process grows exponentially. If it takes time T to execute the original version of queens for a given board size, we can expect the new version to take roughly T^board-size time to execute.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.40 & 2.41: Nested Mappings

From SICP section 2.2.3 Sequences as Conventional Interfaces

The next sub-section of SICP shows us how we can express nested loops using sequence operations. The first example given is the following problem:

Given a positive integer n, find all ordered pairs of distinct positive integers i and j, where 1 <= j < i <= n, such that (i + j) is prime.

In pseudocode, a solution using nested loops would be:

for i = 1 to n:
   for j = 1 to (i - 1):
       if isPrime( i + j ):
           print i, j, i + j

For n = 6, the output of the program above would be:

2, 1, 3
3, 2, 5
4, 1, 5
4, 3, 7
5, 2, 7
6, 1, 7
6, 5, 11

One way of looking at this is that the two nested loops generate a sequence of pairs, and the if statement applies a filter to each pair in the sequence.

In Scheme we can produce a sequence of pairs using nested mappings.

(accumulate append
           null
           (map (lambda (i)
                  (map (lambda (j) (list i j))
                       (enumerate-interval 1 (- i 1))))
                (enumerate-interval 1 n)))

The flatmap procedure is defined to abstract the portion of the code above that accumulates with append.

(define (flatmap proc seq)
   (accumulate append null (map proc seq)))

Procedures are then defined to filter out prime sums and to create the pair sum output from each pair in the sequence.

(define (prime-sum? pair)
   (prime? (+ (car pair) (cadr pair))))

(define (make-pair-sum pair)
   (list (car pair) (cadr pair) (+ (car pair) (cadr pair))))

Combining all of these steps with the filter and enumerate-interval procedures from earlier in SICP section 2.2.3, we get the complete procedure.

(define (prime-sum-pairs n)
   (map make-pair-sum
        (filter prime-sum?
                (flatmap
                 (lambda (i)
                   (map (lambda (j) (list i j))
                        (enumerate-interval 1 (- i 1))))
                 (enumerate-interval 1 n)))))

Exercise 2.40 asks us to define a procedure unique-pairs that, given an integer n, generates the sequence of pairs (i j) with 1 <= j < i <= n. We are to use unique-pairs to simplify the definition of prime-sum-pairs given above.

Since we already have code embedded in prime-sum-pairs that generates the sequence of unique pairs that we need, this exercise basically amounts to an extract method refactoring of that piece of code.

(define (unique-pairs n)
   (flatmap
    (lambda (i)
      (map (lambda (j) (list i j))
           (enumerate-interval 1 (- i 1))))
    (enumerate-interval 1 n)))

The body of unique-pairs is a simple copy/paste from prime-sum-pairs. Replacing that portion of code in the original is just as easy.

(define (prime-sum-pairs n)
   (map make-pair-sum
        (filter prime-sum?
                (unique-pairs n))))

We can test it with a known value to verify.

> (prime-sum-pairs 6)
((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

Exercise 2.41 asks us to 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.

If we were solving this using loops, we'd just nest our loops three deep. This exercise teaches us that nested mappings can be extended the same way. Let's start by creating a procedure that just finds ordered triples of distinct positive integers. We'll base it on unique-pairs from the previous exercise.

(define (ordered-triples n)
   (flatmap (lambda (i)
      (flatmap (lambda (j)
         (map (lambda (k)
                (list i j k))
              (enumerate-interval 1 (- j 1))))
       (enumerate-interval 1 (- i 1))))
    (enumerate-interval 1 n)))

> (ordered-triples 5)
((3 2 1)
(4 2 1)
(4 3 1)
(4 3 2)
(5 2 1)
(5 3 1)
(5 3 2)
(5 4 1)
(5 4 2)
(5 4 3))

Next we can create a filtering procedure that checks to see if a triple sums to a given integer.

(define (triple-sum? triple s)
   (= s (accumulate + 0 triple)))

> (triple-sum? (list 1 2 3) 5)
#f
> (triple-sum? (list 1 2 3) 6)
#t

We also need a procedure to append the sum of the elements of a triple to the end of the triple so it's included in the output.

(define (make-triple-sum triple)
   (append triple (list (accumulate + 0 triple))))

> (make-triple-sum (list 1 2 3))
(1 2 3 6)

Finally, we can put it all together. Since filter takes only two arguments, a predicate and a sequence, we need to embed our predicate procedure triple-sum? in the final solution so that it can have access to the target sum variable s.

(define (ordered-triple-sum n s)
   (define (triple-sum? triple)
     (= s (accumulate + 0 triple)))
   (map make-triple-sum
        (filter triple-sum?
                (ordered-triples n))))

> (ordered-triple-sum 5 10)
((5 3 2 10) (5 4 1 10))
> (ordered-triple-sum 10 5)
()
> (ordered-triple-sum 10 6)
((3 2 1 6))
> (ordered-triple-sum 12 12)
((5 4 3 12)
(6 4 2 12)
(6 5 1 12)
(7 3 2 12)
(7 4 1 12)
(8 3 1 12)
(9 2 1 12))

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.38 & 2.39: Folding Left and Right

From SICP section 2.2.3 Sequences as Conventional Interfaces

Exercise 2.38 informs us that another name for the accumulate procedure we've been using is fold-right, because it combines the elements of a sequence starting on the left and moving to the right. There's also a fold-left procedure that combines elements working in the opposite direction.

; fold-right is another name for accumulate
(define (fold-right op initial sequence)
   (if (null? sequence)
       initial
       (op (car sequence)
           (fold-right op initial (cdr sequence)))))

; fold-left is given in exercise 2.38
(define (fold-left op initial sequence)
   (define (iter result rest)
     (if (null? rest)
         result
         (iter (op result (car rest))
               (cdr rest))))
   (iter initial sequence))

We're given a few expressions that illustrate how these two procedures behave differently.

> (fold-right / 1 (list 1 2 3))
1 1/2
> (fold-left / 1 (list 1 2 3))
1/6
> (fold-right list null (list 1 2 3))
(1 (2 (3 ())))
> (fold-left list null (list 1 2 3))
(((() 1) 2) 3)

We're asked what property the op parameter needs to satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

The property that will guarantee that fold-right and fold-left will produce the same values for any sequence is commutativity. You may remember the commutative property of both addition and multiplication from algebra. It's the law that says that:

A + B = B + A

and

A x B = B x A

Subtraction and division are not commutative operations. The AND and OR operations in Boolean algebra are commutative.


Exercise 2.39 asks us to complete the following definitions of reverse (from exercise 2.18) in terms of fold-right and fold-left:

(define (reverse sequence)
   (fold-right (lambda (x y) <??>) null sequence))

(define (reverse sequence)
   (fold-left (lambda (x y) <??>) null sequence))

Since we only need to define the operator used in each implementation, the key to this exercise lies in how the operator is applied in each folding procedure. Pay close attention to the order of the arguments of the op procedure.

In fold-right the operator is applied to the car of the sequence and the result of a recursive call to fold-right. Just as we did in exercise 2.18, we can reverse the sequence using fold-right by appending the car of the sequence to the reverse of its cdr.

(define (reverse sequence)
   (fold-right (lambda (x y) (append y (list x))) null sequence))

In fold-left the operator is applied to the result sequence and the car of the unused elements in the initial sequence. Since the result sequence starts with an initial value of null, and we're starting at the end of the sequence and working backwards anyway, we can just cons each element to the end of the result.

(define (reverse sequence)
   (fold-left (lambda (x y) (cons y x)) null sequence))

As expected, we get the same test results for either of the two reverse implementations above.

> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.18: Reversing a List

From SICP section 2.2.1 Representing Sequences

Exercise 2.18 asks us to define a procedure reverse that takes a list as its argument and returns a list with the same elements in reverse order.

We'll be using the append procedure given in the text which takes two lists and appends the second list to the end of the first:

(define (append list1 list2)
   (if (null? list1)
       list2
       (cons (car list1) (append (cdr list1) list2))))

We can reverse a list by appending the car of the list to the reverse of the cdr of the list. (See how easy it is to start thinking in Scheme?) In other words, we just move the first item to the end of the list after reversing the remaining items. This means reverse will make a recursive call to itself, so we also need a base case to make the recursion stop. We can just stop when we reach an empty list.

(define (reverse items)
 (if (null? items)
     items
     (append (reverse (cdr items)) (list (car items)))))

Once again, we can test it out with a few example lists from the text.

> (reverse (list 1 2 3 4))
(4 3 2 1)
> (reverse (list 1 4 9 16 25))
(25 16 9 4 1)
> (reverse (list 1 3 5 7))
(7 5 3 1)
> (reverse (list 23 72 149 34))
(34 149 72 23)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

SICP 2.17: Last Item in a List

From SICP section 2.2.1 Representing Sequences

Exercise 2.17 asks us to define a procedure last-pair that returns a list that contains only the last element of a given (non-empty) list.

Earlier in SICP section 2.2.1 we saw that a list is represented in Scheme as a chain of pairs.


Our new procedure needs to return a list, so we need to be careful not to simply return the last value in the list, or even the last pair.

There are several correct ways to do this, but here's a recursive solution (based on the length example from the text) that uses the method of "cdring down" the list.

(define (last-pair items)
  (if (null? (cdr items))
      (list (car items))
      (last-pair (cdr items))))

The first line checks to see if the cdr of the list of items passed in is nil. If it is, the second line creates a new list from the car of the items. If not, the last line makes a recursive call to last-pair with the remaining items in the list.

We can verify that it works by testing it with several of the example lists from the chapter.

> (last-pair (list 1 2 3 4))
(4)
> (last-pair (list 1 4 9 16 25))
(25)
> (last-pair (list 1 3 5 7))
(7)
> (last-pair (list 23 72 149 34))
(34)

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.