Exercise 2.42 · 习题

Exercise 2.42: 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 k

th 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 k

th column. Now filter these, keeping
only the positions for which the queen in the k

th 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.

SVG

Figure 2.8: A solution to the eight-queens 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 k

th 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 k

th 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.)

练习 2.42："八皇后谜题"要求将八个皇后放置在国际象棋棋盘上，使得没有任何一个皇后被其他皇后将军（即没有两个皇后处于同一行、同一列或同一对角线上）。图 2.8 展示了一种可能的解法。解决这道谜题的一种方式是逐列放置皇后，每列放一个。一旦已放好 k - 1 个皇后，就必须将第 k 个皇后放在一个不与已有任何皇后产生攻击的位置。我们可以递归地表述这一方法：假设我们已经生成了在棋盘前 k - 1 列中放置 k - 1 个皇后的所有可能方案的序列。对其中每种方案，在第 k 列的每一行各放一个皇后，生成一组扩展后的位置集合。然后对这些集合进行过滤，只保留第 k 列的皇后相对于其他皇后安全的位置。这样就产生了在前 k 列中放置 k 个皇后的所有方案的序列。持续这一过程，将产生谜题的所有解，而不仅仅是一个解。

SVG

图 2.8：八皇后谜题的一个解。

我们将这一解法实现为过程 queens，它返回在 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 列的皇后是否相对于其他皇后安全。（注意，我们只需检验新皇后是否安全——其他皇后彼此之间已保证安全。）