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.