Figure 2.8: A solution to the eightqueens puzzle.
The “eightqueens 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 procedurequeencols
that returns the sequence of all ways to place queens in the first k columns of the board.(define (queens boardsize) (define (queencols k) (if (= k 0) (list emptyboard) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (restofqueens) (map (lambda (newrow) (adjoinposition newrow k restofqueens)) (enumerateinterval 1 boardsize))) (queencols ( k 1)))))) (queencols boardsize))
In this procedure
restofqueens
is a way to place k  1 queens in the first k  1 columns, andnewrow
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 procedureadjoinposition
, which adjoins a new rowcolumn position to a set of positions, andemptyboard
, which represents an empty set of positions. You must also write the proceduresafe?
, 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.)
Choosing a representation
We have a choice here of what kind of representation to use. I chose to represent each board position as a list. The first element in the list represents which row the queen is in in the first column of the board. The second element in the list represents which row the queen is in in the second column. Etc. The last element in the list represents which row the queen is in in the last column. The number of elements in the list is the same as the number of columns on the board, which is the boardsize
argument in the queens
procedure.
The procedure queens
returns a list of all the legal board positions for a given boardsize
. It’s a list of sublists, with each sublist being of length boardsize
.
Example: The position in Figure 2.8, which is a solution for boardsize
= 8, is (3 7 2 8 5 1 4 6)
. That would be one of the lists in the full set of solutions for boardsize
= 8.
Understanding the given procedure
What is emptyboard
?
It’s our job to define emptyboard
. When k
= 0, the procedure returns (list emptyboard)
. k
= 0 means there are 0 columns. What are the ways we can arrange 0 queens in 0 columns? There aren’t any. So we define emptyboard
as nil
:
(define emptyboard nil)
What does queencols
do?
queencols
is a procedure that returns a list of all the safe ways to place queens in the first k
columns of the board.
Example: If boardsize
is 4 and k
is 2, then queencols
is ((1 3) (1 4) (2 4) (3 1) (4 2) (4 1))
.
What does restofqueens
represent?
restofqueens
is used as an argument to a lambda
. It is a list of length k
1, representing one way to place k
 1 queens in the first k
 1 columns.
Example: If boardsize
is 4 and k
is 3, then restofqueens
could be (1 4)
.
What does newrow
represent?
newrow
is used as an argument to a different lambda
. It is a number representing a proposed row in which to place the queen for the k
th column.
Example: If boardsize
is 4, then newrow
could be 2.
What does adjoinposition
do?
It’s our job to define adjoinposition
. It’s a procedure that adjoins a new position (a row number in my representation) to a set of positions (list of row numbers in my representation). Its arguments are a number newrow
representing a possible row in which to place the queen in the current (k
th) column, a number k
representing the current column, and a list restofqueens
representing one way to safely place queens in k
 1 columns.
Example: If the row is 2, the column is 3, and restofqueens
is (1 4)
, then adjoinposition
returns (1 4 2)
.
Using this description, we see that we want adjoinposition
to stick newrow
onto the end of restofqueens
. We can use append
for this, after making newrow
into a list because append
expects lists as arguments.
In the definition below of adjoinposition
, I changed the names of the arguments from those used in queens
so as not to use the same argument names in two different procedures.
(define (adjoinposition row column positionsofar)
(append positionsofar (list row)))
Note that column
isn’t used in the definition. I kept it in there so I could use the queens
procedure as written in the exercise.
What does the map
do?
(map (lambda (newrow) (adjoinposition newrow k restofqueens))
(enumerateinterval 1 boardsize))
This maps the enumerated interval from 1 to boardsize
onto a list of length boardsize
. Each thing in the new list is a sublist of length k
. The sublists of length k
all start with the same k
 1 entries that were in restofqueens
and each has a different last entry, from 1 to boardsize
.
Example: If boardsize
is 4 and restofqueens
is (1 3)
, then this map
returns ((1 3 1) (1 3 2) (1 3 3) (1 3 4))
.
Note that the positions returned by this map
may or may not be legal board positions.
What does the flatmap
do?
(flatmap
(lambda (restofqueens)
(map (lambda (newrow)
(adjoinposition newrow k restofqueens))
(enumerateinterval 1 boardsize)))
(queencols ( k 1)))
This maps all the solutions for k
 1 columns onto lists of potential solutions for k
columns and then flattens the list into one long list.
In other words, it combines the results of map
for all the solutions already found for k
 1 columns.
What does safe?
do?
It’s our job to define safe?
. It’s used in the filter to choose the safe solutions from the potential solutions produced by the flatmap
.
safe?
takes two arguments: the number of columns and a list representing some queen positions. That list will be of length k
. We know that the first k
 1 positions in the list are safe together, but we don’t know if the k
th number in the list is safe with the others and that’s what we need safe?
to find out.
There are two things to check for:

Is the last queen in the same row as another queen? In other words, is the last number in the list the same as any of the other numbers in the list?

Is the last queen on a diagonal with another queen? In other words, is the absolute value of the difference between the last number and any of the other numbers the same as the absolute value of the difference in their positions in the list?
I wrote a last
procedure. It returns the last item in a list. That’s the one we want to check against the others. I used let
so that the last item would only have to be pulled out once for each time safe?
is used.
(define (last items)
(if (equal? (cdr items) nil)
(car items)
(last (cdr items))))
The helper procedure, safe?helper
, is recursive. It checks the last element (which represents the row that the last queen is in) against each other element in turn (representing each other queen’s position) to see if the two are safe with respect to each other. The three lines that return #f
are when it finds an unsafe situation. If it gets to the end without finding an unsafe situation, it returns #t
.
I didn’t make use of the column
argument to safe?
. Instead, in the helper procedure, I used the length of the list representing the current partial set of positions. I could remove column
as an argument to safe?
and change the (lambda (positions) (safe? k positions))
line to say just safe?
. I didn’t, in order to fit my answer into the queens
procedure given in the exercise.
(define (safe? column position)
(let ((lastqueenposition (last position)))
(define (safe?helper partialposition)
(cond ((equal? (cdr partialposition) nil) #t)
((= (car partialposition) lastqueenposition) #f)
((= ( (length partialposition) 1) ( lastqueenposition (car partialposition))) #f)
((= ( (length partialposition) 1) ( (car partialposition) lastqueenposition)) #f)
(else (safe?helper (cdr partialposition)))))
(safe?helper position)))
Other procedures from the book that are needed to get queens
to run
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
(define (enumerateinterval low high)
(if (> low high)
nil
(cons low (enumerateinterval (+ low 1) high))))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
Testing of the queens
procedure after adding in the new definitions
> (queens 1)
((1))
> (queens 2)
()
> (queens 3)
()
> (queens 4)
((2 4 1 3) (3 1 4 2))
> (queens 5)
((1 3 5 2 4)
(1 4 2 5 3)
(2 4 1 3 5)
(2 5 3 1 4)
(3 1 4 2 5)
(3 5 2 4 1)
(4 1 3 5 2)
(4 2 5 3 1)
(5 2 4 1 3)
(5 3 1 4 2))
> (queens 6)
((2 4 6 1 3 5) (3 6 2 5 1 4) (4 1 5 2 6 3) (5 3 1 6 4 2))
(queens 7)
and (queens 8)
look correct too, but they take up more space so I didn’t copy them here. (queens 8)
has 92 solutions and does include (3 7 2 8 5 1 4 6)
, the solution shown in Figure 2.8.
(queens 11)
took about 10 seconds to run. I didn’t try higher input than that.
Other solutions
atomik’s answer on this page used the same representation I did. I realized from reading that answer that I could have stuck the new column onto the front of the list instead of the end. Then I wouldn’t have needed to append
in adjoinposition
and then I wouldn’t have needed to pull out the last entry using my last
procedure.
I started to rewrite my procedures to do it this way, but then I realized that I’d need a more complicated way of determining if a new queen was on a diagonal with an existing queen. I decided to go with my answer as is.
Several other answers used a pair of coordinates to represent each queen instead of a single number. The one I like the best is around the middle of this page.
I especially like what they said about checking diagonals:
The most interesting one of them is
samediagonal?
. It uses the fact that for all squares located on the same diagonal either row + col or row – col is a constant.