SICP 読み (222) 4.3.2 非決定性プログラムの例

8queen が動いたっぽいのでコードを控えておきます。

(define (require p) (if (not p) (amb)))
(define (distinct? items)
  (let ((last (tailend items)))
    (cond ((null? (cdr items)) true)
	  ((eq? last (car items)) false)
	  (else
	   (distinct? (cdr items))))))

(define (tailend seq)
  (define (tailend-iter seq ret)
    (if (null? seq)
	ret
	(tailend-iter (cdr seq) (car seq))))
  (tailend-iter seq '()))

(define (safe? k seq)
  (let ((last (tailend seq)))
    (define (safe-iter p k seq)
      (cond ((= (- k p) 0) true)
	    ((= (abs (- (car seq) last)) (- k p)) false)
	    ((= (car seq) last) false)
	    (else
	     (safe-iter (+ p 1) k (cdr seq)))))
    (safe-iter 1 k seq)))

(define (enumerate-seq n)
  (define (enum-seq-iter seq)
    (if (> seq n)
	'()
	(cons seq
	      (enum-seq-iter (+ seq 1)))))
  (enum-seq-iter 1))

(define (n-queens board-size)
  (define (n-queens-iter n ret)
    (cond ((> n board-size) ret)
	  (else
	   (let ((l (append ret (list (list-amb (enumerate-seq board-size))))))
	     (require (distinct? l))
	     (require (safe? n l))
	     (n-queens-iter (+ n 1) l)))))
  (n-queens-iter 1 '()))

(define (list-amb l)
  (if (null? l)
      (amb)
      (amb (car l)
	   (list-amb (cdr l)))))

がしかし、遅い。