# 2.42

## 将这一解法实现为一个过程queens，令它返回在n x n棋盘上放n个皇后的所有解的序列。queens内部的过程queen-cols，返回在棋盘的前k列中放皇后的所有格局的序列。

(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)
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))


(define eight-by-eight
(list
(list 0 0 0 0 0 1 0 0)
(list 0 0 1 0 0 0 0 0)
(list 1 0 0 0 0 0 0 0)
(list 0 0 0 0 0 0 1 0)
(list 0 0 0 0 1 0 0 0)
(list 0 0 0 0 0 0 0 1)
(list 0 1 0 0 0 0 0 0)
(list 0 0 0 1 0 0 0 0)
)
)


(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))
)
)


(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))

(define (adjoin-position new-row k rest-of-queens)
(map
(lambda (i)
(map
(lambda (j)
(if (and (= new-row i) (= k j))
1
(list-ref (list-ref rest-of-queens (- i 1)) (- j 1))
)
)
(enumerate-interval 1 (max 1 (length rest-of-queens)))
)
)
(enumerate-interval 1 (max 1 (length rest-of-queens)))
)
)



(define
(make-empty-board board-size)
(map
(lambda (i)
(map
(lambda (j) 0)
(enumerate-interval 1 board-size)
)
)
(enumerate-interval 1 board-size)
)
)

(make-empty-board 2)


(define (row-safe? positions)
(=  1
(accumulate * 1
(map
(lambda (row)
(if (<= (accumulate + 0 row) 1)
1
0
)
)
positions
)
)
)
)

(row-safe? eight-by-eight)

(define (get-element positions i j)
(list-ref
(list-ref positions (- i 1))
(- j 1))
)

(get-element eight-by-eight 3 3 )

(define (upper-left-safe? k positions)
(accumulate (lambda (x y) (and x y)) #t (map
(lambda (i)
(<= (accumulate + 0 (map
(lambda (j)
(get-element positions (- (+ i j) k) j)
)
(reverse
(enumerate-interval
(max
1
(+ (- k i) 1)
)
k
)
)
)) 1 )
)

(enumerate-interval 1 (length positions))
))
)

(upper-left-safe? 2 eight-by-eight)

(define (lower-left-safe? k positions)
(accumulate (lambda (x y) (and x y)) #t (map
(lambda (i)
(<= (accumulate + 0 (map
(lambda (j) (get-element positions (+ i (- k j)) j))
(reverse (enumerate-interval
(max 1 (- k (- (length positions) i)))
k
))
)) 1)
)
(enumerate-interval 1 (length positions))
))
)

(lower-left-safe? 3 eight-by-eight)


safe? 定义如下：

(define (safe? k positions)
(and
(row-safe? positions)
(upper-left-safe? k positions)
(lower-left-safe? k positions)
)
)

(safe? 8 eight-by-eight)


(define (flatmap proc seq)
(accumulate append '()  (map proc seq)))

(define (queens board-size)
(define empty-board
(make-empty-board 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)