SICP Exercise 2.42

Question

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 by placing \(n\) queens on an \(n\times 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
         (λ (positions)
           (safe? k positions))
         (flatmap
          (λ (rest-of-queens)
            (map (λ (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}\) columns 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.)

Answer

For complex tasks like this, it helps to start out by building a dummy version of the real thing you want to have later. In this case, when I was building this, I had the safe? procedure simply return #t every single time, so that all positions would be accepted. This helped to first of all make sure that the way the list of positions is being constructed is correct. Then, as soon as that works, we can turn our attention to actually implementing the safety check.

We must also consider the data representation, for which there are basically infinite possibilities. I decided to represent a board of positions as a two-dimensional list containing each single queen position as $x,y$-coordinates.

So, here is the full list of procedures:

(define (adjoin-position row col positions)
  (cons (list row col) positions))

(define empty-board nil)

(define (same-row? pos1 pos2)
  (equal? (car pos1) (car pos2)))
(define (same-dia? pos1 pos2)
  (let ((row1 (car pos1))
        (row2 (car pos2))
        (col1 (cadr pos1))
        (col2 (cadr pos2)))
    (= (abs (- row2 row1)) (abs (- col2 col1)))))

(define (get-queen-at-k k pos)
  (car (filter (λ (q) (= (cadr q) k)) pos)))
(define (get-queens-not-at-k k pos)
  (filter (λ (q) (not (= (cadr q) k))) pos))

(define (safe? k queens-in-pos)
  (let ((queen-at-k (get-queen-at-k k queens-in-pos))
        (queens-not-at-k (get-queens-not-at-k k queens-in-pos)))
    (if (equal? nil queens-not-at-k)
        #t
        (accumulate
         (λ (a b) (and a b))
         #t
         (map (λ (x) (not (or (same-row? x queen-at-k)
                                   (same-dia? x queen-at-k))))
              queens-not-at-k)))))

Let’s test it:

(queens 8)

Results:

(((4 8) (2 7) (7 6) (3 5) (6 4) (8 3) (5 2) (1 1))
 ((5 8) (2 7) (4 6) (7 5) (3 4) (8 3) (6 2) (1 1))
[...]
((5 8) (7 7) (2 6) (6 5) (3 4) (1 3) (4 2) (8 1)))

Let’s pick one element of the returned list at random and draw it to make sure that it is actually a valid position. I am using the following position:

((6 8) (3 7) (5 6) (8 5) (1 4) (4 3) (2 2) (7 1))

This is a valid position, as seen in the following image: