Eight queens 八皇后问题.

Presentation on theme: "Eight queens 八皇后问题."— Presentation transcript:

1 Eight queens 八皇后问题

2 Group Members 韩奇 刘源奇 鹿尧

3 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 ——《百度百科》

4 八皇后问题的一个解

5 作为例子，我们将8皇后问题简化为4皇后问题

6 这是一颗四叉树，树上每个结点表示一个局部布局或一个完整的布局，根结点表示棋盘的初始状态：棋盘上无任何棋子。没个棋子都有四个可选择的位置，但在任何时刻，棋盘的合法布局都必须满足3个约束条件，即任何两个棋子都不能处于同一行、同一列或同一斜线上

7 求所有布局的过程即为在上述条件下先根遍历状态树的过程。遍历中访问结点的操作为，判别棋盘上是否已经有一个完整的布局（即棋盘上是否已摆上4个棋子），若是，则输出该布局；否则依次先根遍历满足约束条件的各棵子树，即首先判断子树根的布局是否合法，若合法，则先根遍历该子树，否则剪去该子树分支。

8 2017/3/12

9 程序实现： 这里我们用递归法和非递归法并进行比较
程序实现： 这里我们用递归法和非递归法并进行比较

10 递归法 VS 非递归法

11 首先是两种方法都必须具有的两个函数： 判断函数（int check（int i）） 输出函数（void show（） ）

12 int check(int i) { //判断当前状态是否合法 int j; for(j=1;j<i;j++) if(col[j]==col[i]||fabs(i-j)==fabs(col[j]-col[i])) return 0; } return 1;

13 void show() { //输出 int i; int p,q; int board[N+1][N+1]={0}; //初始化棋盘 static t=1; printf("第%d个解为: ",t++); for(i=1;i<=N;i++) { board[i][col[i]]=1; printf("(%d,%d) ",i,col[i]); } printf("\n"); for(p=1;p<=N;p++) for(q=1;q<=N;q++) if(board[p][q]==1) printf("●"); else printf("○"); printf(" \n");

14 递递递递递递归法

15 void trial(int i) { //进入本函数时，在N×N的棋盘前i-1行已放置了i-1个互不攻击的棋子。 //现从第i行起继续为后续棋子选择合适位置。 //当i > N时，求得一个合法布局，输出之。 int j; if(i>N) show(); else for(j=1;j<=N;j++) col[i]=j; if(check(i)) trial(i+1); col[i]=0;//移走棋子 }

16 程序运行

17 非递归法

18 void trial() { //迭代回溯 int i=1; while(i>0) { col[i]+=1;//当前列加1的位置开始搜索 while(col[i]<=N && !check(i)) {//当前列位置是否满足条件 //不满足条件，继续搜索下一个位置 col[i]+=1; } if(col[i]<=N) {//存在满足条件的列 if(i==N)//是最后一个皇后，完成搜索 show(); else {//不是，处理下一个皇后 i++; col[i]=0; else //回溯 i--;

19 程序运行

20 以上两种算法都利用了回溯和试探的搜索技术求解。
回溯法的求解过程实质上是一个先序遍历一颗“状态树”的过程，只是这颗树不是预先建立的，而是隐含在遍历过程中。 空间代价一般为最长路径的长度，„ 如果要把整个树存储下来的话，那空间代价是惊人的 2017/3/12

21 以上