2-42.scm

(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))

(define empty-board '())

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

(define (safe? k positions)
  (cond ((not (line-safe? k positions same-row?)) #f)
        ((not (line-safe? k positions same-diagonal?)) #f)
        (else #t)))

(define (line-safe? k positions same?)
  (let ((new (list-ref positions (- k 1))))
    (every (lambda (pos) (not (same? pos new)))
           (take positions (- k 1)))))

(define (same-row? pos-a pos-b)
  (= (car pos-a) (car pos-b)))

(define (same-diagonal? pos-a pos-b)
  (let ((diff (abs (- (cdr pos-a) (cdr pos-b)))))
    (or
     (= (car pos-a) (- (car pos-b) diff))
     (= (car pos-a) (+ (car pos-b) diff)))))

(test-section "ex 2.42")
(test* "adjoin-position" '((1 . 1) (3 . 2) (4 . 3))
       (adjoin-position 4 3 '((1 . 1) (3 . 2))))

(test* "same-row?" #t (same-row? '(1 . 1) '(1 . 2)))
(test* "same-row?" #f (same-row? '(1 . 1) '(3 . 2)))
(test* "same-diagonal?" #t (same-diagonal? '(2 . 2) '(3 . 1)))
(test* "same-diagonal?" #t (same-diagonal? '(2 . 2) '(3 . 3)))
(test* "column-safe?" #t
       (line-safe? 3 '((1 . 1) (3 . 2) (4 . 3)) same-row?))
(test* "column-safe?" #f
       (line-safe? 3 '((1 . 1) (3 . 2) (3 . 3)) same-row?))

(test* "diagonal-safe?" #f
       (line-safe? 3 '((1 . 1) (3 . 2) (3 . 3)) same-diagonal?))
(test* "diagonal-safe?" #t
       (line-safe? 3 '((3 . 1) (7 . 2) (2 . 3)) same-diagonal?))

(test* "safe?" #t (safe? 1 '((1 . 1))))
(test* "safe?" #t (safe? 3 '((2 . 1) (4 . 2) (1 . 3) (3 . 4))))

(define sample-ans-queen '((3 . 1) (7 . 2) (2 . 3) (8 . 4) (5 . 5) (1 . 6) (4 . 7) (6 . 8)))
(test* "queens" #t (not (null? (member sample-ans-queen (queens 8)))))