这是一个用 amb 解决的 n-皇后问题。
(define (debug e) #f) (define (n-queens n) (call/cc (lambda (return) (let place-queens ((i 0) (rows '())) (when (< i n) (let ((try-place (number-between 1 n))) ;start to place queen No.i (debug `("considering queen " ,i " on row " ,try-place "\n")) (do ((placed-idx 0 (+ 1 placed-idx))) ;ensure no two queens conflict ((>= placed-idx (length rows))) (debug `("checking queen on column " ,placed-idx)) (let* ((r (list-ref rows placed-idx)) (condition (and (not (= r try-place)) (not (or (= (+ placed-idx r) (+ i try-place)) (= (- placed-idx r) (- i try-place))))))) (if condition (debug " ... OK!\n") (debug " ... conflict!\n")) (assert condition))) (debug `("putting queen " ,i " on row " ,try-place "\n")) (debug `("places: " ,(append rows (list try-place)) "\n")) (place-queens (+ 1 i) (append rows (list try-place)))) ) (return rows)))))
其实程序的大部分回溯都由 number-between 包办了。在放置第 i 个皇后时,你需要做的只是:让 number-between 帮你取一个数,作 为第 i 列皇后放置的行数。然后说:“ *这个皇后不能与已经放好 的任何一个皇后在同一条横线上,或者在同一条对角线上。* ” amb 就会自动帮你找到答案。魔法!
我在代码里加入了一些 debug 语句,但是 debug 先被定义为什么也 不干。这样处理 8 个皇后的时候会快一些。执行:
(n-queens 8)
就得到一个结果。再执行 (amb) 就得到下一个结果,再下一个结果……
执行
(bag-of (n-queens 8))
就得到了“八皇后问题”的所有 92 个解。
如果你把 debug 重新定义为
(define debug (lambda (e) (cond ((list? e) (for-each display e)) ((string? e) (display e)))))
就能显示这个过程中,amb 为你考虑了什么。不过显示 debug 信息 时,最好使用 4 个皇后,因为 8 个皇后的信息量实在太大了,会看 头晕的 :P
n-皇后其实不大能展示 amb 的威力。你可能觉得用 C 实现 n-皇后 也挺容易?那么就看看下面几个……