SICP 全笔记

Exercise 2.42.

+---+---+---+---+---+---+---+---+
|   |   |   |   |   | o |   |   |
+---+---+---+---+---+---+---+---+
|   |   | o |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
| o |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | o |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | o |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | o |
+---+---+---+---+---+---+---+---+
|   | o |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | o |   |   |   |   |
+---+---+---+---+---+---+---+---+

Figure 2.8: A solution to the eight-queens puzzle.

The ‘‘eight-queens puzzle’’ asks how to place eight queens on a chessboard so that no queen is in check from any other (i.e., no two queens are in the same row, column, or diagonal). One possible solution is shown in figure 2.8. One way to solve the puzzle is to work across the board, placing a queen in each column. Once we have placed k - 1 queens, we must place the kth queen in a position where it does not check any of the queens already on the board. We can formulate this approach recursively: Assume that we have already generated the sequence of all possible ways to place k - 1 queens in the first k - 1 columns of the board. For each of these ways, generate an extended set of positions by placing a queen in each row of the kth column. Now filter these, keeping only the positions for which the queen in the kth column is safe with respect to the other queens. This produces the sequence of all ways to place k queens in the first k columns. By continuing this process, we will produce not only one solution, but all solutions to the puzzle.

We implement this solution as a procedure queens, which returns a sequence of all solutions to the problem of placing n queens on an n× n chessboard. Queens has an internal procedure queen-cols that returns the sequence of all ways to place queens in the first k columns of the board.

(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))

In this procedure rest-of-queens is a way to place k - 1 queens in the first k - 1 columns, and new-row is a proposed row in which to place the queen for the kth column. Complete the program by implementing the representation for sets of board positions, including the procedure adjoin-position, which adjoins a new row-column position to a set of positions, and empty-board, which represents an empty set of positions. You must also write the procedure safe?, which determines for a set of positions, whether the queen in the kth column is safe with respect to the others. (Note that we need only check whether the new queen is safe–the other queens are already guaranteed safe with respect to each other.)

棋盘的表示

要考虑 empty-board 的表示，就先考虑示例中的棋盘的表示方法。

它的表示方法可以是 (3 7 2 8 5 1 4 6) 。即第 n 个元素 x 构成棋盘上的 (x, n) 坐标（从 1 开始计数）。

因为 empty-board 是 k = 0 时候的棋盘，我们或许可以表示为 (0 0 0 0 0 0 0 0) 。但这个时候在 queen-cols 函数中是不知道 board-size 的，不能确定有多少个 0，所以 empty-board 就只能表示为 '() 。

(define empty-board '())

adjoin-position

(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 的功能

要了解 adjoin-position 就要去了解 rest-of-queens。要了解 rest-of-queens，就需要了解 queen-cols 会返回什么。因为我们已经知道棋盘的表示方法了，所以当 k = 1 的时候，对 (enumerate-interval 1 board-size) 的 map 实际就是对一个空棋盘 '() 作插入行的操作（列的信息已经由 list 的位置决定了），得到结果 '((1) (2) (3) ...) 表示第一个 queen 所有可能在的位置。最后这些位置再由 safe? 来决定是否符合我们的要求，最后就返回 (queen-cols 1) 的值。

得到 adjoin-position

(define (adjoin-position row col positions)
  (append positions (list row)))

这里没有使用到 col 的值。

safe?

最后一个是 safe? 过程。这个过程将去判断 positions 中第 k 个元素是否和 positions 的 1~k-1 个皇后的位置发生冲突。

其中的关键是在于如何判断两个皇后的位置冲突。可以使用如下函数进行判断：

(define (safe-pos? row1 col1 row2 col2)
  (cond ((= row1 row2) #f)
        ((= (- col1 row1) (- col2 row2)) #f)
        ((= (+ col1 row1) (+ col2 row2)) #f)
        (else #t)))

即：

  • row 相等时表示冲突。比如 (safe? 4 (3 7 2 2))

  • 两个皇后在同一条斜线上。这里的斜线可以使用下面两个公式表示：

    1. y = x + b ，即去判断这两个点是否在斜率为 1 的一条直线上
    2. y = -x + b，即去判断这两个点是否在斜率为 -1 的一条直线上

最终得到

(define (safe? k positions)
  (define (safe-pos? row1 col1 row2 col2)
    (cond ((= row1 row2) #f)
          ((= (- col1 row1) (- col2 row2)) #f)
          ((= (+ col1 row1) (+ col2 row2)) #f)
          (else #t)))
  (define (safe/rec? row col rows col1)
    (cond ((null? (cdr rows)) #t)
          ((safe-pos? row col (car rows) col1)
           (safe/rec? row col (cdr rows) (+ 1 col1)))
          (else #f)))
  (let ((c k)
        (r (list-ref positions (- k 1))))
    (safe/rec? r c positions 1)))

结果

共 92 个解。

(1 5 8 6 3 7 2 4)
(1 6 8 3 7 4 2 5)
(1 7 4 6 8 2 5 3)
(1 7 5 8 2 4 6 3)
(2 4 6 8 3 1 7 5)
(2 5 7 1 3 8 6 4)
(2 5 7 4 1 8 6 3)
(2 6 1 7 4 8 3 5)
(2 6 8 3 1 4 7 5)
(2 7 3 6 8 5 1 4)
(2 7 5 8 1 4 6 3)
(2 8 6 1 3 5 7 4)
(3 1 7 5 8 2 4 6)
(3 5 2 8 1 7 4 6)
(3 5 2 8 6 4 7 1)
(3 5 7 1 4 2 8 6)
(3 5 8 4 1 7 2 6)
(3 6 2 5 8 1 7 4)
(3 6 2 7 1 4 8 5)
(3 6 2 7 5 1 8 4)
(3 6 4 1 8 5 7 2)
(3 6 4 2 8 5 7 1)
(3 6 8 1 4 7 5 2)
(3 6 8 1 5 7 2 4)
(3 6 8 2 4 1 7 5)
(3 7 2 8 5 1 4 6)
(3 7 2 8 6 4 1 5)
(3 8 4 7 1 6 2 5)
(4 1 5 8 2 7 3 6)
(4 1 5 8 6 3 7 2)
(4 2 5 8 6 1 3 7)
(4 2 7 3 6 8 1 5)
(4 2 7 3 6 8 5 1)
(4 2 7 5 1 8 6 3)
(4 2 8 5 7 1 3 6)
(4 2 8 6 1 3 5 7)
(4 6 1 5 2 8 3 7)
(4 6 8 2 7 1 3 5)
(4 6 8 3 1 7 5 2)
(4 7 1 8 5 2 6 3)
(4 7 3 8 2 5 1 6)
(4 7 5 2 6 1 3 8)
(4 7 5 3 1 6 8 2)
(4 8 1 3 6 2 7 5)
(4 8 1 5 7 2 6 3)
(4 8 5 3 1 7 2 6)
(5 1 4 6 8 2 7 3)
(5 1 8 4 2 7 3 6)
(5 1 8 6 3 7 2 4)
(5 2 4 6 8 3 1 7)
(5 2 4 7 3 8 6 1)
(5 2 6 1 7 4 8 3)
(5 2 8 1 4 7 3 6)
(5 3 1 6 8 2 4 7)
(5 3 1 7 2 8 6 4)
(5 3 8 4 7 1 6 2)
(5 7 1 3 8 6 4 2)
(5 7 1 4 2 8 6 3)
(5 7 2 4 8 1 3 6)
(5 7 2 6 3 1 4 8)
(5 7 2 6 3 1 8 4)
(5 7 4 1 3 8 6 2)
(5 8 4 1 3 6 2 7)
(5 8 4 1 7 2 6 3)
(6 1 5 2 8 3 7 4)
(6 2 7 1 3 5 8 4)
(6 2 7 1 4 8 5 3)
(6 3 1 7 5 8 2 4)
(6 3 1 8 4 2 7 5)
(6 3 1 8 5 2 4 7)
(6 3 5 7 1 4 2 8)
(6 3 5 8 1 4 2 7)
(6 3 7 2 4 8 1 5)
(6 3 7 2 8 5 1 4)
(6 3 7 4 1 8 2 5)
(6 4 1 5 8 2 7 3)
(6 4 2 8 5 7 1 3)
(6 4 7 1 3 5 2 8)
(6 4 7 1 8 2 5 3)
(6 8 2 4 1 7 5 3)
(7 1 3 8 6 4 2 5)
(7 2 4 1 8 5 3 6)
(7 2 6 3 1 4 8 5)
(7 3 1 6 8 5 2 4)
(7 3 8 2 5 1 6 4)
(7 4 2 5 8 1 3 6)
(7 4 2 8 6 1 3 5)
(7 5 3 1 6 8 2 4)
(8 2 4 1 7 5 3 6)
(8 2 5 3 1 7 4 6)
(8 3 1 6 2 5 7 4)
(8 4 1 3 6 2 7 5)