解决方案中的八皇后

Question

我开始写一个函数来查看棋盘上其他位置的皇后是否为'safe'，棋盘的形式为(row col)且索引为1。这是我到目前为止所拥有的：

(define (get-row p) (car p))
(define (get-col p) (cadr p))
(define (is-equal p1 p2)
  (and (= (car p1) (car p2)) (= (cadr p1) (cadr p2))))

(define (safe? k positions)
  (filter
     (lambda (p) (not (and (is-equal p
                               (list (get-row p) k))
                     (is-equal p
                               (list (+ (get-row p) (- k (get-col p)))
                                     k
                                     ))
                     (is-equal p
                               (list (- (get-row p) (- k (get-col p)))
                                     k
                                     )))))
   positions))

我想这样称呼它：

(safe? 4 '((3 1) (1 2) (4 3) (2 4)))

看棋盘上位置(2 4)的第四个皇后（第四列）是否安全

但是，我目前所拥有的内容太离谱了，returns 基本上是所有 'other' 列，而不是我想要的那一列。执行此操作的更好方法是什么？

Answer 1

有很多方法可以解决这个问题。对于初学者，我建议对董事会进行更简单的表示，我选择使用数字列表。列表中的索引从1开始，表示皇后所在的列及其所在行的值（坐标原点在左上角，新位置在列表末尾相连）；所有其他位置都假定为空。例如下面的板子：

(. Q)
(Q .)

将由列表 '(2 1) 表示。根据我的表述，safe? 过程看起来像这样 - 请注意 diagonals? 检查的实现有点棘手：

; a new queen is safe iff there are no other queens in the same
; row nor in any of the diagonals preceding its current position
; we don't need to check the column, this is the only queen on it

(define (safe? col board)
  (let ((row (list-ref board (- col 1))))
    (and (<= (number-occurrences row board) 1)
         (diagonals? row board))))

; counts how many times an element appears on a list

(define (number-occurrences e lst)
  (count (curry equal? e) lst))

; traverses the board looking for other queens
; located in one of the diagonals, going backwards
; starting from the location of the newest queen

(define (diagonals? row board)
  (let loop ((lst   (cdr (reverse board)))
             (upper (sub1 row))
             (lower (add1 row)))
    (or (null? lst)
        (and (not (= (car lst) upper))
             (not (= (car lst) lower))
             (loop (cdr lst) (sub1 upper) (add1 lower))))))

结果符合预期：

(safe? 4 '(2 4 1 3))
=> #t

如果您愿意，您可以调整以上代码以使用不同的坐标原点，或者使用成对的坐标来表示皇后区。

解决方案中的八皇后

Solving Eight-queens in scheme

scheme

lisp

sicp

n-queens