(load "2.40.txt") ; for flatmap and enumerate-interval

(define (queens board-size)
  (define empty-board '())
  (define (make-position row column)
    (cons row column))
  (define (position-row position)
    (car position))
  (define (position-column position)
    (cdr position))
  (define (adjoin-position row column positions)
    (cons (make-position row column) positions))
  (define (can-attack? a b)
    (let ((ar (position-row a))
          (ac (position-column a))
          (br (position-row b))
          (bc (position-column b)))
      (or (= ar br)
          (= ac bc)
          (= (abs (- ar br)) (abs (- ac bc))))))

  ; Is the queen in the kth column safe?
  ; Requires there is a queen in the kth column
  (define (safe? k positions)
    (define (find-kth positions)
      (cond ((null? positions)
             (error "could not queen in kth column" k))
            ((= (position-column (car positions)) k)
             (car positions))
            (else (find-kth (cdr positions)))))
    (let ((kth-queen (find-kth positions)))
      (not (any (lambda (p) (can-attack? kth-queen p))
                (filter (lambda (p) (not (equal? p kth-queen)))
                        positions)))))
  (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))