lisp - Scheme，N-queens 优化策略 SICP 第 2 章

Question

SICP 包含 n 皇后解决方案的部分完整示例，通过遍历最后一行中每个可能的皇后位置的树，在下一行中生成更多可能的位置以组合到目前为止的结果，过滤保留的可能性只有最新的女王是安全的，并且递归地重复。

此策略在大约 n=11 后失败并出现最大递归错误。

我已经实现了一种替代策略，该策略从第一列开始进行更智能的树遍历，从未使用的行列表中生成可能的位置，将每个位置列表添加到尚未使用的行的更新列表中。过滤那些被认为安全的对，并递归映射下一列的这些对。这并没有爆炸(到目前为止)，但 n=12 需要一分钟，n=13 需要大约 10 分钟才能解决。

(define (queens board-size)
 (let loop ((k 1) (pp-pair (cons '() (enumerate-interval 1 board-size))))
   (let ((position (car pp-pair))
         (potential-rows (cdr pp-pair)))
    (if (> k board-size) 
        (list position)
        (flatmap (lambda (pp-pair) (loop (++ k) pp-pair)) 
         (filter (lambda (pp-pair) (safe? k (car pp-pair))) ;keep only safe
          (map (lambda (new-row) 
                (cons (adjoin-position new-row k position) 
                      (remove-row new-row potential-rows))) ;make pp-pair
           potential-rows))))))) 
;auxiliary functions not listed 

不是真正在寻找代码，而是对一两个策略的简单解释，它不那么天真，并且与功能性方法相得益彰。

Answer 1

我可以为您提供代码的简化，因此它可能会运行得更快一些。我们首先重命名一些变量以提高可读性 (YMMV)，

(define (queens board-size)
 (let loop ((k 1) 
            (pd (cons '() (enumerate-interval 1 board-size))))
   (let ((position (car pd))
         (domain   (cdr pd)))
    (if (> k board-size) 
        (list position)
        (flatmap (lambda (pd) (loop (1+ k) pd)) 
         (filter (lambda (pd) (safe? k (car pd))) ;keep only safe NewPositions
          (map (lambda (row) 
                (cons (adjoin-position row k position)  ;NewPosition
                      (remove-row row domain))) ;make new PD for each Row in D
               domain)))))))                            ; D

现在， filter f (map g d) == flatmap (\x->let {y=g x} in [y | f y]) d (在那里使用了一些 Haskell 语法)，即我们可以融合 map和 filter合二为一flatmap :

        (flatmap (lambda (pd) (loop (1+ k) pd)) 
         (flatmap (lambda (row)                   ;keep only safe NewPositions
               (let ( (p (adjoin-position row k position))
                      (d (remove-row row domain)))
                 (if (safe? k p) 
                     (list (cons p d)) 
                     '())))
            domain)) 

然后， flatmap h (flatmap g d) == flatmap (h <=< g) d (其中 <=< 是从右到左的 Kleisli 组合运算符，但谁在乎)，所以我们可以融合两个 flatmap s 变成一个，用

        (flatmap 
            (lambda (row)                         ;keep only safe NewPositions
                (let ((p (adjoin-position row k position)))
                  (if (safe? k p)
                    (loop (1+ k) (cons p (remove-row row domain)))
                    '())))
            domain)

所以简化的代码是

(define (queens board-size)
 (let loop ((k        1) 
            (position '())
            (domain   (enumerate-interval 1 board-size)))
    (if (> k board-size) 
        (list position)
        (flatmap 
            (lambda (row)                         ;use only the safe picks
              (if (safe_row? row k position)      ;better to test before consing
                (loop (1+ k) (adjoin-position row k position)
                             (remove-row row domain))
                '()))
            domain))))