心辰·Dev

Scheme 编程实例 | 八皇后问题

发表于

问题描述

在 8 X 8 格的国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后不能处于同一行、同一列或同一斜线上，求这八皇后有多少种摆法。该问题可推广至 N X N 的棋盘。

解决思路

按一个方向处理棋盘，每次在每一列里放一个皇后。如果现在放好 k - 1 个皇后，第 k 个皇后就必须放在不会被已在棋盘上的任何皇后攻击的位置上。
即使用分治策略处理该问题。假定我们已经生成在棋盘的前 k - 1 列放置 k - 1 个皇后的所有可能方式，对其中每种方式，都生成将下一个皇后放在第 k 列中每一行的扩充集合。而后只留下那些符合条件的解。

Scheme实现

棋盘中皇后的摆放用列表表示，列表第一个元素表示第 8 列皇后所在行。

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
(define (accumulate op initial sequence)  ; 累计工作的实现
    (if (null? sequence)
        initial
        (op (car sequence)
            (accumulate op initial (cdr sequence)))))

(define (enumerate-interval low high)  ; 枚举数据序列
    (if (> low high)
        nil
        (cons low (enumerate-interval (+ low 1) high))))

(define (flatmap proc seq)
    (accumulate append nil (map proc seq)))

(define empty-board '())  ; 空棋盘用'()表示

(define (adjoin-position new-row rest-of-queens)  ; 添加皇后
    (cons new-row rest-of-queens))

(define (safe? k position)  ; 检查是否安全
    (iter-check (car position) 
                 (cdr position)
                 1))

(define (iter-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 (+ i row-of-current-queen))     ; 右下方碰撞
                     (= row-of-new-queen (- row-of-current-queen i)))    ; 左下方碰撞
                #f
                (iter-check row-of-new-queen 
                    (cdr rest-of-queens)    ; 检查剩余的皇后
                    (+ i 1))))))            ; 更新步进值

(define (queens board-size)
    (define (queen-cols k)
        (if (= k 0)
            (list empty-board)
            (filter  ; 过滤掉不安全的皇后位置
             (lambda (positions) (safe? k positions))  
             (flatmap  ; 列举所有放置第 k 个皇后之后的位置列表
              (lambda (rest-of-queens)
                (map (lambda (new-row) (adjoin-position new-row rest-of-queens))
                    (enumerate-interval 1 board-size)))
              (queen-cols (- k 1))))))
    (queen-cols board-size))

打印程序运算结果

1
2
3
4
5
(for-each (lambda (pos)
            (begin
                (display pos)
                (newline)))
          (queens 8))