bet9九州登陆平台
  咨询电话:18543712719

博天娱乐918客户端

Scheme来实现八皇后问题(1)

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址  http://www.cnblogs.com/Colin-Cai/p/9768105.html   作者:窗户  QQ/微信:6679072  E-mail:6679072@qq.com 

  看到有人写八皇后,那我就也写写这个吧。

 

  八皇后问题

  

  这个问题大家应该都不陌生,很多计算机教程都以八皇后为例题。

  

 

  上面是一个国际象棋棋盘,总共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个解。

, 1, 0, 9);