sol-2.42.tex

We can for instance decide to represent a set of board positions as a list of distinct pairs, with pairs represented as list of two elements rather than as Lisp pairs.
With this representation, the missing procedures can be defined as follows:
\begtt\scm
(define empty-board nil)

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

(define (safe? k positions)
  (let ((queen-k (car positions))
        (rest-of-queens (cdr positions)))
    (null? (filter (lambda (queen)
                     (let ((d-row (- (car queen-k) (car queen)))
                           (d-col (- (cadr queen-k) (cadr queen))))
                       (or (= d-row 0)
                           (= d-row d-col)
                           (= d-row (- d-col)))))
                   rest-of-queens))))
\endtt
Notice that we don't need to use the first argument of the `safe?` procedure, because the position of the queen in column `k` is always the first element of the list of positions, for how we chose to implement the `adjoin-position` procedure.  

As an example, here is the sequence of all solutions to the queens puzzle on a board of size~5:
\begtt\scm
(queens 5)
;value: (((4 5) (2 4) (5 3) (3 2) (1 1))
;value:  ((3 5) (5 4) (2 3) (4 2) (1 1))
;value:  ((5 5) (3 4) (1 3) (4 2) (2 1))
;value:  ((4 5) (1 4) (3 3) (5 2) (2 1))
;value:  ((5 5) (2 4) (4 3) (1 2) (3 1))
;value:  ((1 5) (4 4) (2 3) (5 2) (3 1))
;value:  ((2 5) (5 4) (3 3) (1 2) (4 1))
;value:  ((1 5) (3 4) (5 3) (2 2) (4 1))
;value:  ((3 5) (1 4) (4 3) (2 2) (5 1))
;Value:  ((2 5) (4 4) (1 3) (3 2) (5 1)))
\endtt