Ex 2.42
(define empty-board nil) (define (adjoin-position new-row k rest-of-queens) (cons new-row rest-of-queens)) (define (safe? k ps) (define (next triple) (list (- (car triple) 1) (cadr triple) (+ (caddr triple) 1))) (define (check triple ps) (if (null? ps) true (and (let ((p (car ps))) (fold-right (lambda (x y) (and (not (= x p)) y)) true triple) (check (next triple) (cdr ps))))) (if (null? ps) true (check (next (list (car ps) (car ps) (car ps)) (cdr ps))))
各列のクイーンの行位置を逆順にリストにしたものを盤面とみたてて解いた。たとえば例の図のクイーンの位置を示すリストは (6 4 1 5 8 2 7 3)。
safe? は、列上にほかのクイーンがないことはわかっているため、先におかれたクイーンが斜め方向と行方向とにないことを確認する戦略を実装した。手前の列のそれぞれに対して、斜め上と行、斜め下の行番号の三つ組みを更新しつつ、行の数字が一致しなければ安全と判断している。
(昨日の夕方には終えていたけれど清書できなかった)