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