如何解决计划中的N个皇后? [英] How to Solve N-Queens in Scheme?

问题描述

我被困在扩展的练习28.2如何设计程序.我使用的是真值或假值向量来表示板子，而不是使用列表.这是我无法使用的内容:

I'm stuck on the extended exercise 28.2 of How to Design Programs. I used a vector of true or false values to represent the board instead of using a list. This is what I've got which doesn't work:

#lang Scheme

(define-struct posn (i j))

;takes in a position in i, j form and a board and 
;  returns a natural number that represents the position in index form
;example for board xxx
;                  xxx
;                  xxx
;(0, 1) -> 1
;(2, 1) -> 7
(define (board-ref a-posn a-board)
  (+ (* (sqrt (vector-length a-board)) (posn-i a-posn))
     (posn-j a-posn)))

;reverse of the above function
;1 -> (0, 1)
;7 -> (2, 1)
(define (get-posn n a-board)
  (local ((define board-length (sqrt (vector-length a-board))))
    (make-posn (floor (/ n board-length)) 
               (remainder n board-length))))

;determines if posn1 threatens posn2
;true if they are on the same row/column/diagonal
(define (threatened? posn1 posn2)
  (cond
    ((= (posn-i posn1) (posn-i posn2)) #t)
    ((= (posn-j posn1) (posn-j posn2)) #t)
    ((= (abs (- (posn-i posn1)
                (posn-i posn2)))
        (abs (- (posn-j posn1)
                (posn-j posn2)))) #t)
    (else #f)))

;returns a list of positions that are not threatened or occupied by queens
;basically any position with the value true
(define (get-available-posn a-board)
  (local ((define (get-ava index)
            (cond
              ((= index (vector-length a-board)) '())
              ((vector-ref a-board index)
               (cons index (get-ava (add1 index))))
              (else (get-ava (add1 index))))))
    (get-ava 0)))

;consume a position in the form of a natural number and a board
;returns a board after placing a queen on the position of the board
(define (place n a-board)
  (local ((define (foo x)
            (cond
              ((not (board-ref (get-posn x a-board) a-board)) #f)
              ((threatened? (get-posn x a-board) (get-posn n a-board)) #f)
              (else #t))))
    (build-vector (vector-length a-board) foo)))

;consume a list of positions in the form of natural numbers, and a board
;returns a list of boards after placing queens on each of the positions
;                                                            on the board
(define (place/list alop a-board)
  (cond
    ((empty? alop) '())
    (else (cons (place (first alop) a-board)
                (place/list (rest alop) a-board)))))

;returns a possible board after placing n queens on a-board
;returns false if impossible
(define (placement n a-board)
  (cond
    ((zero? n) a-board)
    (else (local ((define available-posn (get-available-posn a-board)))
            (cond
              ((empty? available-posn) #f)
              (else (or (placement (sub1 n) 
                          (place (first available-posn) a-board))
                        (placement/list (sub1 n) 
                          (place/list (rest available-posn) a-board)))))))))

;returns a possible board after placing n queens on a list of boards
;returns false if all the boards are not valid
(define (placement/list n boards)
  (cond
    ((empty? boards) #f)
    ((zero? n) (first boards))
    ((not (boolean? (placement n (first boards)))) (first boards))
    (else (placement/list n (rest boards)))))

推荐答案

这不是最快的方案实现，但是非常简洁.我确实独立提出了这个建议，但是我怀疑它的独特性.它在PLT方案中，因此需要更改某些函数名称才能使其在R6RS中运行.解决方案列表和每个解决方案都具有缺点，因此它们是相反的.反向操作和最后映射将所有内容重新排序，并在解决方案中添加行以获得漂亮的输出.大多数语言都具有折叠类型功能，请参见:
http://en.wikipedia.org/wiki/Fold_%28higher-order_function% 29

This isn't the fastest scheme implementation possible, but it's pretty concise. I did come up with it independently, but I doubt it's unique. It's in PLT Scheme, so some function names need to be changed to get it running in R6RS. The list of solutions and each solution are built with cons, so they're reversed. The reverses and maps at the end reorder everything and add rows to the solutions for a pretty output. Most languages have a fold type function, see:
http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

#lang scheme/base
(define (N-Queens N)  

  (define (attacks? delta-row column solution)
    (and (not (null? solution))
         (or (= delta-row (abs (- column (car solution))))
             (attacks? (add1 delta-row) column (cdr solution)))))  

  (define (next-queen safe-columns solution solutions)
    (if (null? safe-columns)
        (cons solution solutions)
        (let move-queen ((columns safe-columns) (new-solutions solutions))
          (if (null? columns) new-solutions
              (move-queen
                (cdr columns)
                (if (attacks? 1 (car columns) solution) new-solutions
                    (next-queen (remq (car columns) safe-columns)  
                                (cons (car columns) solution)  
                                new-solutions)))))))

  (unless (exact-positive-integer? N)
    (raise-type-error 'N-Queens "exact-positive-integer" N))
  (let ((rows (build-list N (λ (row) (add1 row)))))
    (reverse (map (λ (columns) (map cons rows (reverse columns)))
                  (next-queen (build-list N (λ (i) (add1 i))) null null)))))

如果您考虑问题，列表实际上就是该问题的自然数据结构.由于每行只能放置一个皇后，因此只需将安全或未使用列的列表传递给迭代器的下一行即可.这是通过cond子句中对remq的调用完成的，该调用使对next-queen的回溯调用得以实现.

If you think about the problem, a list is really the natural data structure for this problem. Since only one queen can be placed on each row, all that needs to be done is pass a list of safe or unused columns to the iterator for the next row. This is done with the call to remq in the cond clause that makes the backtracking call to next-queen.

foldl函数可以重写为命名的let:

The foldl function can be rewritten as a named let:

(define (next-queen safe-columns solution solutions)
  (if (null? safe-columns)
      (cons solution solutions)
      (let move-queen ((columns safe-columns) (new-solutions solutions))
        (if (null? columns) new-solutions
            (move-queen

这是相当快的，因为它避免了参数检查内置在foldl中的开销.在查看PLT Scheme N-Queens基准测试时，我遇到了使用隐式行的想法.从1的增量行开始，并在检查解决方案时将其递增，这非常漂亮.出于某种原因，PLT方案中的Abs昂贵，因此有一种更快的攻击形式吗?

This is considerably faster, since it avoids the argument checking overhead built into foldl. I came across the idea of using implicit rows while looking at the PLT Scheme N-Queens benchmark. Starting with a delta-row of one and incrementing it as the solution is checked is pretty slick. For some reason, abs is expensive in PLT Scheme, so there is a faster form for attacks?

在PLT方案中，必须使用可变列表类型以实现最快的实现.除了初始列列表之外，无需创建任何缺点单元就可以编写对解决方案进行计数而不返回解决方案的基准.这样可以避免在N = 17之前收集垃圾，这时在gc中花费了618毫秒，而程序花费了1个小时51分钟来找到95,815,104个解决方案.

In PLT Scheme, you have to use the mutable list type for the fastest implementation. A benchmark that counts solutions without returning them can be written without creating any cons cells, other than the initial column list. This avoids collecting garbage until N = 17, when 618 milliseconds were spent in gc while the program spent 1 hour, 51 minutes finding the 95,815,104 solutions.

这篇关于如何解决计划中的N个皇后?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！