Eight-queens puzzle

Figure 2.8: A solution to the
eight-queens puzzle. 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 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
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 co

As we are looking for a subset of positions where each column is occupied by exactly one queen, we can represent an NxN board setup in a simpler way - as a list of N numbers, each ranging from 1 to N, representing row number taken by the queen in the 1st ... Nth columns. Empty board would still be an emplty list.

Then we can use cons as adjoin-position, and check particular k-queens position by taking the first queen position and iterating over remaining k-1 queens, checking if the delta between positions equals zero or the number of iteration. With this approach safe? doesn't even need an explicit k as an argument - it is just the length of the position passed to safe? and is used implicity by iterating over the (cdr position):

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list '())
        (filter
          (lambda (position) (safe? position))
          (flatmap
            (lambda (rest-of-queens)
              (map (lambda (new-row)
                      (cons new-row rest-of-queens))
                   (enumerate-interval 1 board-size)))
            (queen-cols (- k 1))))))
  (define (safe? position)
    (safe-iter? (car position) 1 (cdr position)))
  (define (safe-iter? fst n rest-position)
    (cond ((null? rest-position) true)
          ((= fst (car rest-position)) false)
          ((= (abs (- fst (car rest-position))) n) false)
          (else (safe-iter? fst (+ n 1) (cdr rest-position)))))
  (queen-cols board-size))

StackExchange Code Review Q#1872, answer score: 3