4

SICP contains an partially complete example of the n-queens solutions, by walking a tree of every possible queen placement in the last row, generating more possible positions in the next row to combine the results so far, filtering the possibilities to keep only ones where the newest queen is safe, and repeating recursively.

This strategy blows up after about n=11 with a maximum recursion error.

I've implemented an alternate strategy that does a smarter tree-walk from the first column, generating possible positions from a list of unused rows, consing each position-list onto an updated list of yet-unused rows. Filtering those pairs considered safe, and recursively mapping over these pairs for the next column. This doesn't blow up (so far) but n=12 takes a minute and n=13 takes about 10 minutes to solve.

(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

Not really looking for code, but a simple explanation of a strategy or two that's less naive and that clicks well with a functional approach.

4

2 に答える 2

3

コードを簡素化することで、実行速度が少し速くなる可能性があります。読みやすくするためにいくつかの変数の名前を変更することから始めます (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 構文を少し使用して)、つまり、とを 1 つに融合できます。mapfilterflatmap

        (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 合成演算子ですが、気にしないでください)、2 つflatmapの s を 1 つに融合できます。

        (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))))
于 2013-06-12T08:25:52.580 に答える
1

二度目に思いついたのがこちら。ただし、それが非常に高速かどうかはわかりません。かなりきれいですが。

(define (n-queens n)
  (let loop ((k 1) (r 1) (dangers (starting-dangers n)) (res '()) (solutions '()))
    (cond ((> k n) (cons res solutions))
          ((> r n) solutions)
          ((safe? r k dangers) 
           (let ((this (loop (+ k 1) 1 (update-dangers r k dangers) 
                             (cons (cons r k) res) solutions)))
             (loop k (+ r 1) dangers res this)))
          (else (loop k (+ r 1) dangers res solutions)))))

重要なのは、let ステートメントを使用して再帰をシリアル化し、深さを n に制限することです。解は後方に出てきます (r と k で 1->n の代わりに n->1 にすることでおそらく修正できます) が、後方集合は前方集合と同じ集合です。

(define (starting-dangers n)
  (list (list)
        (list (- n))
        (list (+ (* 2 n) 1))))
;;instead of terminating in null list, terminate in term that cant threaten

小さな改善、危険は列、下向きの斜め、または上向きの斜めから来る可能性があり、ボードが進化するにつれてそれぞれを追跡します.

(define (safe? r k dangers)
   (and (let loop ((rdangers (rdang dangers)))
           (cond ((null? rdangers) #t)
                 ((= r (car rdangers))
                  #f)
                 (else (loop (cdr rdangers)))))
        (let ((ddiag (- k r)))
           (let loop ((ddangers (ddang dangers)))
              (if (<= (car ddangers) ddiag)
                  (if (= (car ddangers) ddiag)
                      #f
                      #t)
                  (loop (cdr ddangers)))))
        (let ((udiag (+ k r)))
           (let loop ((udangers (udang dangers)))
              (if (>= (car udangers) udiag)
                  (if (= (car udangers) udiag)
                      #f
                      #t)
                  (loop (cdr udangers)))))))

フォーマットの変更は中程度の改善で、以前の 2 つと比較してチェックする必要があるのは 1 つだけです。対角線をソートしておくことでコストがかからないとは思いませんが、時間の節約にもならないと思います。

(define (update-dangers r k dangers)
  (list
     (cons r (rdang dangers))
     (insert (- k r) (ddang dangers) >)
     (insert (+ k r) (udang dangers) <))) 

 (define (insert x sL pred)
   (let loop ((L sL))
      (cond ((null? L) (list x))
            ((pred x (car L))
             (cons x L))
            (else (cons (car L)
                        (loop (cdr L)))))))

(define (rdang dangers)
  (car dangers))
(define (ddang dangers)
  (cadr dangers))
(define (udang dangers)
  (caddr dangers))
于 2015-12-10T10:57:04.730 に答える