乐正

Actions speak louder than words.

Sicp-ex2-42

问题

“八皇后谜题”问得是怎样将八个皇后摆在国际象棋盘上,使得任意一个皇后都不能攻击另一 个皇后(也就是说,任意两个皇后都不在同一行、同一列或者同一对角线上)。一个可能的 解如图2-8所示。解决这一谜题的一种方法按一个方向处理棋盘,每次在每一列里放一个皇 后。如果现在已经放好了$k-1$个皇后,第$k$个皇后就必须放在不会被已在棋盘上的任何皇 后攻击的位置上。我们可以递归地描述这一过程:假定我们已经生成了在棋盘的前$k-1$列 中放置$k-1$个皇后的所有可能方式,现在需要的就是对于其中的每种方式,生成出将下一 个皇后放在第$k$列中每一行的扩充集合。而后过滤它们,只留下能使位于第$k$列的皇后与 其他皇后相安无事的扩充。这样就能产生出将$k$个皇后放置在前$k$列的所有格局的序列。 继续这一过程,我们将能产生出这一谜题的所有解,而不是一个解。

将这一解法实现为一个过程queens,令它返回在$n \times n$棋盘上放$n$个皇后的所有 解的序列。queens内部的过程queen-cols,返回在棋盘的前$k$列中放皇后的所有格局 的序列。

八皇后谜题的一个解

八皇后问题 (p85-queens.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
;; Happy hacking, Yuez - Emacs ♥ you!

(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$列的皇 后相对于其他列的皇后是否为安全的(请注意,我们只需检查新皇后是否安全——其他皇后已 经保证相安无事了)。

解答

将一个解表示为形如(4 2 7 3 6 8 5 1)这样的列表。实际上插入新列的操作是由过程adjoin-position 完成的,其可以定义为:

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

empty-board是:

1
(define empty-board '())

而检查新插入列是否是安全列的过程的基本思路是:依次比较新列与其余列中元素的行位置, 新列行号记为$m$,检查列行号记为$n$,被检查两列列差记为$i$,则$m$应该满足:

$$ \begin{cases} m \neq n \\ m \neq n + i \\ m \neq n - i \end{cases} $$

所以,解如下:

练习2.42 (ex2-42.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
;; Happy hacking, Yuez - Emacs ♥ you!

(define (queens board-size)
  (define empty-board '())

  (define (safe? k positions)
    (define (item-check row-of-new-queen rest-of-queens i)
      (if (null? rest-of-queens)
          #t
          (let ((row-of-current-queen (car rest-of-queens)))
            (if (or (= row-of-new-queen row-of-current-queen)
                    (= row-of-new-queen (+ row-of-current-queen i))
                    (= row-of-new-queen (- row-of-current-queen i)))
                #f
                (item-check row-of-new-queen
                            (cdr rest-of-queens)
                            (+ i 1))))))
    (item-check (car positions)
                (cdr positions)
                1))

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

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

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
(for-each (lambda (pos)
      (begin
        (display pos)
        (newline)))
    (queens 8))
(4 2 7 3 6 8 5 1)
(5 2 4 7 3 8 6 1)
(3 5 2 8 6 4 7 1)
(3 6 4 2 8 5 7 1)
(5 7 1 3 8 6 4 2)
(4 6 8 3 1 7 5 2)
(3 6 8 1 4 7 5 2)
(5 3 8 4 7 1 6 2)
(5 7 4 1 3 8 6 2)
(4 1 5 8 6 3 7 2)
(3 6 4 1 8 5 7 2)
(4 7 5 3 1 6 8 2)
(6 4 2 8 5 7 1 3)
(6 4 7 1 8 2 5 3)
(1 7 4 6 8 2 5 3)
(6 8 2 4 1 7 5 3)
(6 2 7 1 4 8 5 3)
(4 7 1 8 5 2 6 3)
(5 8 4 1 7 2 6 3)
(4 8 1 5 7 2 6 3)
(2 7 5 8 1 4 6 3)
(1 7 5 8 2 4 6 3)
(2 5 7 4 1 8 6 3)
(4 2 7 5 1 8 6 3)
(5 7 1 4 2 8 6 3)
(6 4 1 5 8 2 7 3)
(5 1 4 6 8 2 7 3)
(5 2 6 1 7 4 8 3)
(6 3 7 2 8 5 1 4)
(2 7 3 6 8 5 1 4)
(7 3 1 6 8 5 2 4)
(5 1 8 6 3 7 2 4)
(1 5 8 6 3 7 2 4)
(3 6 8 1 5 7 2 4)
(6 3 1 7 5 8 2 4)
(7 5 3 1 6 8 2 4)
(7 3 8 2 5 1 6 4)
(5 3 1 7 2 8 6 4)
(2 5 7 1 3 8 6 4)
(3 6 2 5 8 1 7 4)
(6 1 5 2 8 3 7 4)
(8 3 1 6 2 5 7 4)
(2 8 6 1 3 5 7 4)
(5 7 2 6 3 1 8 4)
(3 6 2 7 5 1 8 4)
(6 2 7 1 3 5 8 4)
(3 7 2 8 6 4 1 5)
(6 3 7 2 4 8 1 5)
(4 2 7 3 6 8 1 5)
(7 1 3 8 6 4 2 5)
(1 6 8 3 7 4 2 5)
(3 8 4 7 1 6 2 5)
(6 3 7 4 1 8 2 5)
(7 4 2 8 6 1 3 5)
(4 6 8 2 7 1 3 5)
(2 6 1 7 4 8 3 5)
(2 4 6 8 3 1 7 5)
(3 6 8 2 4 1 7 5)
(6 3 1 8 4 2 7 5)
(8 4 1 3 6 2 7 5)
(4 8 1 3 6 2 7 5)
(2 6 8 3 1 4 7 5)
(7 2 6 3 1 4 8 5)
(3 6 2 7 1 4 8 5)
(4 7 3 8 2 5 1 6)
(4 8 5 3 1 7 2 6)
(3 5 8 4 1 7 2 6)
(4 2 8 5 7 1 3 6)
(5 7 2 4 8 1 3 6)
(7 4 2 5 8 1 3 6)
(8 2 4 1 7 5 3 6)
(7 2 4 1 8 5 3 6)
(5 1 8 4 2 7 3 6)
(4 1 5 8 2 7 3 6)
(5 2 8 1 4 7 3 6)
(3 7 2 8 5 1 4 6)
(3 1 7 5 8 2 4 6)
(8 2 5 3 1 7 4 6)
(3 5 2 8 1 7 4 6)
(3 5 7 1 4 2 8 6)
(5 2 4 6 8 3 1 7)
(6 3 5 8 1 4 2 7)
(5 8 4 1 3 6 2 7)
(4 2 5 8 6 1 3 7)
(4 6 1 5 2 8 3 7)
(6 3 1 8 5 2 4 7)
(5 3 1 6 8 2 4 7)
(4 2 8 6 1 3 5 7)
(6 3 5 7 1 4 2 8)
(6 4 7 1 3 5 2 8)
(4 7 5 2 6 1 3 8)
(5 7 2 6 3 1 4 8)
;Unspecified return value

draft

« sicp-ex2-41 sicp-ex2-43 »

Comments