sicp - SICP 第 2 版中的练习 2.42。我的解决方案不自然吗？我的解决方案好吗？

Question

我正在阅读 SICP 第 2 版。
我解决了练习 2.42（八皇后拼图）。
但是我的adjoin-position根本safe?不用k。
我想我的解决方案没有错，但我介意我的解决方案是否不自然。
我的解决方案好吗？

“八皇后之谜”询问如何在棋盘上放置八个皇后，以使没有皇后与其他皇后相互制衡（即，没有两个皇后在同一行、同一列或对角线）。图 2.8 显示了一种可能的解决方案。解决难题的一种方法是全面工作，在每列中放置一个女王。一旦我们放置了 k - 1 个皇后，我们必须将第 k 个皇后放在一个不会检查任何已经在棋盘上的皇后的位置。我们可以递归地制定这种方法：假设我们已经生成了将 k - 1 个皇后放置在棋盘的前 k - 1 列中的所有可能方式的序列。对于这些方式中的每一种，通过在第 k 列的每一行放置一个皇后来生成一组扩展的位置。现在过滤这些，只保留第 k 列中的皇后相对于其他皇后安全的位置。这产生了在前 k 列中放置 k 个皇后的所有方式的序列。通过继续这个过程，我们不仅会产生一个解决方案，而且会产生所有解决方案。

我们将这个解决方案实现为一个过程queries，它返回所有解决方案的序列，以解决在n×n 棋盘上放置n 个皇后的问题。Queens 有一个内部过程queen-cols，它返回将皇后放置在棋盘前k 列的所有方式的序列。

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

在这个过程中，rest-of-queens 是一种将 k - 1 个皇后放置在前 k - 1 列中的方法，而 new-row 是一个提议的行，用于将第 k 列的皇后放置在其中。通过实现棋盘位置集的表示来完成程序，包括将新行列位置与一组位置邻接的过程 adjoin-position 和表示空位置集的 empty-board。你还必须编写过程 safe?，它为一组位置确定第 k 列中的皇后相对于其他位置是否安全。（请注意，我们只需要检查新皇后是否安全——其他皇后已经保证彼此安全。）

---

我的解决方案在这里：

(define empty-board nil)

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size))) ;for each row of the kth column
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(define (adjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

(define (safe? k positions)
  (and (horizontally-safe? positions) (diagonally-safe1? positions) (diagonally-safe2? positions)))

(define (horizontally-safe? positions)
  (define (in? i items)
    (cond ((null? items) #t)
          ((= i (car items)) #f)
          (else (in? i (cdr items)))))
  (in? (car positions) (cdr positions)))

(define (diagonally-safe1? positions)
  (define (internal-diagonally-safe1? i items)
    (cond ((null? items) #t)
          ((= i 0) #t)
          ((= (- i 1) (car items)) #f)
          (else (internal-diagonally-safe1? (- i 1) (cdr items)))))
  (internal-diagonally-safe1? (car positions) (cdr positions)))

(define (diagonally-safe2? positions)
  (define (internal-diagonally-safe2? i items)
    (cond ((null? items) #t)
          ((= (+ i 1) (car items)) #f)
          (else (internal-diagonally-safe2? (+ i 1) (cdr items)))))
  (internal-diagonally-safe2? (car positions) (cdr positions)))

(length (queens 8))
  

标签： sicp