看到有人写八皇后, 那我就也写写这个吧.
八皇后问题
这个问题大家应该都不陌生, 很多计算机教程都以八皇后为例题.
上面是一个国际象棋棋盘, 总共 8X8 个格子.
皇后是国际象棋里杀力最强的子, 它可以吃掉同一条横线, 竖线上其他棋子, 也可以吃掉所在的两条斜线上的其他棋子(当然在角上只有一条斜线).
能否在棋盘上放更多的皇后, 让彼此之间不能互相吃到? 基于很显然一行或者一列最多只有一个皇后, 那么这个 8X8 的棋盘是否可以放 8 个皇后?
解的表示
8 个皇后的表示可以用坐标, 那么就是 8 个坐标的集合, 其中行, 列都是范围 1~8 的数字.
考虑到每一行都只有一个, 我们完全可以用让 8 个皇后按照行坐标进行从小到大排序, 那么必然 8 个皇后的行坐标分别是 1,2,3,4,5,6,7,8, 于是这都是无用的信息. 又因为只有 8 列, 而且任意两个皇后都不能同列, 从而每一列也有且只有一个, 从而刚才排序之后的 8 个皇后的纵坐标序列是 1,2,3,4,5,6,7,8 的一个排列. 于是每一种可行的解对应着 1,2,3,4,5,6,7,8 的一个排列.
考虑更一般的情况, n 皇后问题: nXn 的棋盘上放 n 个皇后, 要求彼此之间不互相吃. 那么它的每一个解对应着 1~n 的一个排列.
解法框架
一种做法就是先找到 1~n 的所有排列, 然后筛选符合条件的结果.
那么利用 filter 算子最终代码很容易给出:
- (define (queen n)
- (filter
- valid?
- (P n)
- )
- )
这里的 (P n) 是所有的 1~n 排列的集合, 这里排列当然用 list 来表示, 集合也用 list 来表示.
集合的每个元素是没有序的关系, 所以逻辑上表示集合的 list 我们应该忽略其各个元素的序的差别.
比如 (P 2) 表示的是'((1 2) (2 1)), 或者是'((2 1) (1 2)), 无论哪种实现, 都是可行的.
valid? 是个谓词函数(返回 bool 值的函数), 它的作用是对于某个具体排列, 判断其表示的 n 个皇后有没有互相吃的情况:
如果有两个皇后互相吃, 那么这个排列不可以作为最后的解, 应当返回假, Scheme 里也就是 #f;
如果不存在两个皇后互相吃, 那么这个排列可以作为最后的皆, 从而应当返回真, Scheme 里也就是 #t.
filter 算子就是使用 valid? 这样的谓词函数来过滤后面的集合,
比如 (filter even? '(1 2 3 4 5 6 7 8 9 10)) 就是抓取其中为偶数的元素组成的集合, 那么当然返回'(2 4 6 8 10).
filter 这么常用的算子似乎并未出现在 r5rs 中, 很奇怪, 我在这里就给出一个实现如下:
- (define (filter boolf set)
- (cond
- ((null? set) '())
- ((boolf (car set)) (cons (car set) (filter boolf (cdr set))))
- (else (filter boolf (cdr set)))
- )
- )
接下去就是 P 函数和 valid? 函数的实现.
全排列
第一个问题就是要解决 1~n 的所有排列, 可能会有人考虑将所有的排列用字典排序依次输出.
不过这一般是迭代的思想, 而对于一种 Lisp, 我们第一反应一般是递归.
假设我们已经有 1~n-1 的全排列了, 那么我们怎么得到 1~n 的全排列呢?
我们可以取 1~n-1 的一个排列, 不妨用字母标注
a1 a2 ... an-1
我们希望找个位置插入 n, 得到新的 1~n 的排列.
这个插入点一共有 n 个, 分别为:
a1 之前
a1 和 a2 之间
a2 和 a3 之间
...
an-2 和 an-1 之间
an-1 之后
从而可以得到 n 个 1~n 的排列.
而对 1~n-1 的所有排列都这么做, 则构成了 1~n 的所有排列, 且不存在重复.
比如 1~2 的所有排列组成的集合为
((1 2) (2 1))
现在我们要用它生成 1~3 的全排列
对于(1 2), 有 3 个插入点, 插入 3, 得到三个排列
(3 1 2) (1 3 2) (1 2 3)
对于(2 1), 有 3 个插入点, 插入 3, 得到三个排列
(3 2 1) (2 3 1) (2 1 3)
以上 6 个排列组成的集合就是我们所需要的结果.
首先, 当然要建立一个往列表某个位置插值的函数 list-insert, 带三个参数, 将列表 lst 的位置 pos 插入 v. 而对于位置的解释是, 列表头之前的位置称为 0, 然后依次增加. 比如 (1 2 3) 的位置 1 插入 4, 得到列表(1 4 2 3). 这个很容易用递归设计出来, 如下:
- (define (list-insert lst pos v)
- (if (zero? pos) (cons v lst)
- (cons (car lst) (list-insert (cdr lst) (- pos 1) v))
- )
- )
上述(list-insert '(1 2 3) 1 4), 运算返回'(1 4 2 3)
按照上面的递归思想, 我们使用 map 算子先写一点测试测试, 我们希望从 1~2 的全排列推到 1~3 的全排列
- (map
- (lambda (x) (map (lambda (m) (list-insert x m 3)) '(0 1 2))) ; 对于每个排列, 给出 0,1,2 三个位置插入 3'((1 2)(2 1))
- )
结果为
'(((3 1 2) (1 3 2) (1 2 3)) ((3 2 1) (2 3 1) (2 1 3)))
这很像我们所要的, 但似乎又不是, 因为我们需要应该是'((3 1 2) (1 3 2) (1 2 3) (3 2 1) (2 3 1) (2 1 3))
实际上,(apply append '(((3 1 2) (1 3 2) (1 2 3)) ((3 2 1) (2 3 1) (2 1 3))))就是我们需要的结果了.
而 apply 是把最后一个参数 (这个参数一定要是 i 列表) 展开.
于是上述就成了(append '((3 1 2) (1 3 2) (1 2 3))'((3 2 1) (2 3 1) (2 1 3)) ), 当然就是我们需要的结果了.
而只有 1 个元 1 的全排列集合就是'((1)), 这是递归的边界,
结合上述, 全排列的函数定义应该如下:
- (define (P n)
- (if (= n 1) '((1))
- (apply append
- (map
- (lambda (x) (map (lambda (m) (list-insert x m n)) (range 0 n)))
- (P (- n 1))
- )
- )
- )
- )
判断合法
目前只剩下 valid? 函数的实现了. 实际上, 在我们开始采用用 1~n 排序来作为最后的解的时候, 已经把棋盘中同行同列的情况给排除了. 于是, valid? 函数实际上是要判断是否有两个棋子在同一个斜线上.
比如'(1 3 6 4 2 5 8 7)表示如图的八个皇后, 皇后的位置被打了红圈
其中存在着皇后互吃,
在数据上看,'(1 3 6 4 2 5 8 7), 其中
1 和 4 相差 3, 距离也为 3(1 在列表的第 0 个位置, 4 在列表的第 3 个位置, 所以距离为 3);
3 和 8 相差 5, 距离也为 5;
8 和 7 相差 1, 距离也为 1.
对应着上面三对互吃的皇后.
我们这里可以用迭代来完成, 这有点类似于过程式语言的循环了.
从左到右先距离为 1 的, 看看有没有值也相差 1 的, 如果有, 那么 valid? 返回假, 也就是 #f
然后从左到右再扫距离为 2 的....
...
最后当距离到 n 的时候, 直接返回真, 也就是 #f(因为最左边和最右边距离达到, 也就是 n-1, 此时代表所有可能都已扫过)
- (define (_valid? x left-pos distance)
- (cond
; 当距离以及达到列表长度了, 扫完了, 返回真
((= distance (length x)) #t)
; 如果发现差值等于距离, 这一对皇后互吃, 返回假
((= distance (abs (- (list-ref x left-pos) (list-ref x (+ left-pos distance))))) #f)
; 如果这个距离还没扫完, 那么往后推一个扫
((< (+ left-pos distance) (- (length x) 1)) (_valid? x (+ left-pos 1) distance))
; 否则, 这个距离的已经扫完, 距离加 1, 从最左边开始扫
- (else (_valid? x 0 (+ distance 1)))
- )
- )
用它实现 valid?, 初始的时候, 从 left-pos 为 0,distance 为 1 的一对皇后开始扫起
- (define (valid? x)
- (_valid? x 0 1)
- )
运行
我们就拿 8 个皇后来测试一下, 计算(queen 8)
得到
((4 7 3 8 2 5 1 6) (3 6 4 2 8 5 7 1) (3 5 2 8 6 4 7 1) (6 3 7 2 4 8 1 5) (3 6 8 2 4 1 7 5) (3 7 2 8 6 4 1 5) (3 5 2 8 1 7 4 6) (6 3 7 2 8 5 1 4) (3 6 2 7 5 1 8 4) (3 6 2 5 8 1 7 4) (7 3 8 2 5 1 6 4) (3 7 2 8 5 1 4 6) (3 6 2 7 1 4 8 5) (4 2 7 3 6 8 5 1) (4 2 7 3 6 8 1 5) (5 2 4 6 8 3 1 7) (5 2 4 7 3 8 6 1) (2 4 6 8 3 1 7 5) (5 7 2 6 3 1 8 4) (5 7 2 6 3 1 4 8) (8 2 5 3 1 7 4 6) (2 7 3 6 8 5 1 4) (7 2 6 3 1 4 8 5) (2 6 8 3 1 4 7 5) (4 7 5 2 6 1 3 8) (6 4 2 8 5 7 1 3) (4 2 5 8 6 1 3 7) (4 2 7 5 1 8 6 3) (7 4 2 5 8 1 3 6) (4 2 8 5 7 1 3 6) (4 6 8 2 7 1 3 5) (7 4 2 8 6 1 3 5) (4 2 8 6 1 3 5 7) (5 7 2 4 8 1 3 6) (2 5 7 4 1 8 6 3) (6 8 2 4 1 7 5 3) (7 2 4 1 8 5 3 6) (8 2 4 1 7 5 3 6) (5 2 6 1 7 4 8 3) (5 2 8 1 4 7 3 6) (2 7 5 8 1 4 6 3) (6 2 7 1 4 8 5 3) (2 6 1 7 4 8 3 5) (2 5 7 1 3 8 6 4) (6 2 7 1 3 5 8 4) (2 8 6 1 3 5 7 4) (4 7 5 3 1 6 8 2) (4 8 5 3 1 7 2 6) (4 6 8 3 1 7 5 2) (5 3 8 4 7 1 6 2) (3 5 8 4 1 7 2 6) (3 6 4 1 8 5 7 2) (6 3 7 4 1 8 2 5) (3 8 4 7 1 6 2 5) (6 3 5 7 1 4 2 8) (6 3 5 8 1 4 2 7) (3 5 7 1 4 2 8 6) (3 6 8 1 4 7 5 2) (6 3 1 8 4 2 7 5) (7 5 3 1 6 8 2 4) (5 3 1 6 8 2 4 7) (5 3 1 7 2 8 6 4) (6 3 1 7 5 8 2 4) (6 3 1 8 5 2 4 7) (3 6 8 1 5 7 2 4) (7 3 1 6 8 5 2 4) (3 1 7 5 8 2 4 6) (8 3 1 6 2 5 7 4) (5 7 4 1 3 8 6 2) (5 8 4 1 3 6 2 7) (4 1 5 8 6 3 7 2) (6 4 7 1 3 5 2 8) (8 4 1 3 6 2 7 5) (4 8 1 3 6 2 7 5) (5 7 1 3 8 6 4 2) (1 6 8 3 7 4 2 5) (7 1 3 8 6 4 2 5) (5 1 8 6 3 7 2 4) (1 5 8 6 3 7 2 4) (5 8 4 1 7 2 6 3) (6 4 1 5 8 2 7 3) (4 6 1 5 2 8 3 7) (4 7 1 8 5 2 6 3) (4 8 1 5 7 2 6 3) (4 1 5 8 2 7 3 6) (6 4 7 1 8 2 5 3) (5 1 4 6 8 2 7 3) (5 7 1 4 2 8 6 3) (5 1 8 4 2 7 3 6) (1 7 4 6 8 2 5 3) (1 7 5 8 2 4 6 3) (6 1 5 2 8 3 7 4))
一共 92 个解.
来源: https://www.cnblogs.com/Colin-Cai/p/9768105.html