第五章

n-皇后问题

这是一个用 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-皇后 也挺容易?那么就看看下面几个……