(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (filter condition seq)
(accumulate (lambda (x y) (if (condition x) (cons x y) y))
null
seq))
(define (flatmap proc seq)
(accumulate append null (map proc seq)))
(define (enumerate-interval x n)
(if (> x n) null (cons x (enumerate-interval (+ x 1) n))))
(define (queens board-size)
(define empty-board null)
(define (adjoin-position new-row k rest-of-queens)
(filter (lambda (x) (not (null? x)))
(accumulate cons rest-of-queens (list (list new-row k)))))
(define (safe? k positions)
(define (all-safe? x y)
(cond ((null? y) #t)
((not (= x (car y))) (all-safe? x (cdr y)))
(else #f)))
(define (vertical-points i) (map (lambda (x) (car x)) i))
(define (diagonal-points i x)
(if (null? i) null
(append (list (- (car (car i)) x) (+ (car (car i)) x))
(diagonal-points (cdr i) (+ x 1)))))
(if (<= k 1) #t
(all-safe?
(car (car positions))
(append (vertical-points (cdr positions))
(diagonal-points (cdr positions) 1)))))
(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 (display-queens q)
(define size (length (car q)))
(define (outer-iter q0)
(define (iter q1 n)
(define (inner-iter q2 x)
(if (= x 0) "\n"
(string-append (if (= (car q2) x) "[Q]" "[ ]")
(inner-iter q2 (- x 1)))))
(if (= n 0) "\n\n\n"
(string-append (inner-iter (car q1) size)
(iter (cdr q1) (- n 1)))))
(if (null? q0) "end\n"
(string-append (iter (car q0) size)
(outer-iter (cdr q0)))))
(display (outer-iter q)))
(display-queens (queens 8))
#|
...延々と在るので省略
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][Q][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][Q][ ][ ][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][Q][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][ ][Q][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][Q][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][ ][ ][ ][Q][ ][ ][ ]
[Q][ ][ ][ ][ ][ ][ ][ ]
end
|#