## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.42

## Problem

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 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 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 `emtpy-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.)

## Solution

Here are the procedures, other than the ones we need to write, that are used by procedure `queens`. All of these procedures were defined earlier in the text.

(define nil (quote ())) (define (filter predicate sequence) (cond ((null? sequence) nil) ((predicate (car sequence)) (cons (car sequence) (filter predicate (cdr sequence)))) (else (filter predicate (cdr sequence))))) (define (enumerate-interval low high) (if (> low high) nil (cons low (enumerate-interval (+ low 1) high)))) (define (accumulate op initial sequence) (if (null? sequence) initial (op (car sequence) (accumulate op initial (cdr sequence))))) (define (flatmap proc seq) (accumulate append nil (map proc seq))) (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))

Let's start by numbering the board rows from 1 to *n*, top-to-bottom,
and columns 1 to *n*, left-to-right. We'll represent a set of board
positions of *k* queens on an *n*-row by *k*-column board as a list of
numbers *r*_{i}, , where *i* is the column and *r*_{i} is the row,
, where a queen is to be placed; i.e., the first number in
the list is the row number of the queen in column 1, the second
number in the list is the row number of the queen in column 2, etc.
Then a sequence of board layouts is a list of these *k*-element
lists.

An empty board is represented as the empty list.

(define empty-board nil)

`rest-of-queens` is a list of row positions for *k*-1 queens in
`board-size` rows in the first *k*-1 columns, i.e., it's one of the
board position lists described above. `new-row` is a number from 1
to `board-size` in which we're to place a queen in the newly-added
*k*th column. `adjoin-position` should return a list representation
which is the `rest-of-queens` representation with a new list element
representing the queen's row in column *k*. The simplest way to
do this is simply to add the new row to the position list via `cons`:

(define (adjoin-position new-row column rest-of-queens) (cons new-row rest-of-queens))

This means that new columns are added to the beginning of the
position list rather than the end, i.e., the head of the list is
the *k*th column and not the first as we stated above, but that's OK
-- we'll just change the definition of the representation to match
this convenient new order!

The predicate procedure `safe?` just has to determine the validity of
the position of the queen we just added, i.e., the `car` of the list.
Since we're only adding one queen per new column, we don't need to
check for queens in the same column as the new one: there can be
only one. We do need to check the position of the new queen
against queens in the same row, which is easy -- check for equality
-- and for queens on the same diagonal.

To check the diagonals, we can implement a recursive plan. Start with the column at the beginning of the list and a row offset of 1. If there's a queen in this column whose row is equal to the new queen's row plus/minus the row offset, these two queens are in the same diagonal and the new queen is not safe; otherwise, increment the row offset and check the next column in the list. Repeat the process until we run out of columns.

Here's a definition of `safe?` that implements the recursive plan,
checking the new queen's position a column at a time for the same
row or same diagonal. Note that we could check for edge conditions
(row + row offset > number of rows, or row - row offset < 0), but we
don't strictly need to since these conditions will never evaluate
to true, and not checking is simpler:

(define (safe? column positions) (define (next-column-safe? new-row positions row-offset) (if (null? positions) #t (let ((this-row (car positions))) (if (or (= this-row new-row) (= (+ this-row row-offset) new-row) (= (- this-row row-offset) new-row)) #f (next-column-safe? new-row (cdr positions) (+ 1 row-offset)))))) (next-column-safe? (car positions) (cdr positions) 1))

Now we're ready to test our solution:

(queens 1)

*Output:*

`
`

((1))

(queens 2)

*Output:*

`
`

()

(queens 3)

*Output:*

`
`

()

(queens 4)

*Output:*

`
`

((3 1 4 2) (2 4 1 3))

The solution lists for `board-size` 5-8 are rather long and don't
display nicely, so we only show the number of solutions for each
evaluation here. You can verify that these are the correct number
of solutions (and read a lot more about the queens problem) by
consulting the following web page:

http://mathworld.wolfram.com/QueensProblem.html

(length (queens 5))

*Output:*

`
`

10

(length (queens 6))

*Output:*

`
`

4

(length (queens 7))

*Output:*

`
`

40

(length (queens 8))

*Output:*

`
`

92