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? は、列上にほかのクイーンがないことはわかっているため、先におかれたクイーンが斜め方向と行方向とにないことを確認する戦略を実装した。手前の列のそれぞれに対して、斜め上と行、斜め下の行番号の三つ組みを更新しつつ、行の数字が一致しなければ安全と判断している。

(昨日の夕方には終えていたけれど清書できなかった)