(define (queens board-size)
(letrec ((queen-cols
(lambda (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 (adjoin-position new-row k rest-of-queens)
(cons (list new-row k) rest-of-queens))
(define empty-board '())
(define (safe? k positions)
(letrec ((not-found-row (lambda (row positions)
(cond [(null? positions) #t]
[(= row (caar positions)) #f]
[else (not-found-row row (cdr positions))])))
(not-found-diag (lambda (row col positions)
(cond [(null? positions) #t]
[(or (= row (+ (caar positions)
(- col (cadar positions))))
(= row (- (caar positions)
(- col (cadar positions)))))
#f]
[else (not-found-diag row col (cdr positions))]))))
(if (= k 1)
#t
(let ((row (caar positions))
(col k))
(and (not-found-row row (cdr positions))
(not-found-diag row col (cdr positions)))))))
(define (enumerate-interval i j)
(letrec ((iter (lambda (x result)
(if (< x i)
result
(iter (- x 1) (cons x result))))))
(iter j '())))
(define (flatmap proc seq)
(fold-right append '() (map proc seq)))
(define (fold-right op initial sequence)
(if (null? sequence)
initial
(op (car sequence) (fold-right op initial (cdr sequence)))))
