八皇后问题的一个解作为例子.pptVIP

以上 八皇后问题 Eight queens 韩奇 刘源奇 鹿尧 Group?Members 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 ——《百度百科》 八皇后问题的一个解 作为例子，我们将8皇后问题简化为4皇后问题 这是一颗四叉树，树上每个结点表示一个局部布局或一个完整的布局，根结点表示棋盘的初始状态：棋盘上无任何棋子。没个棋子都有四个可选择的位置，但在任何时刻，棋盘的合法布局都必须满足3个约束条件，即任何两个棋子都不能处于同一行、同一列或同一斜线上 求所有布局的过程即为在上述条件下先根遍历状态树的过程。遍历中访问结点的操作为，判别棋盘上是否已经有一个完整的布局（即棋盘上是否已摆上4个棋子），若是，则输出该布局；否则依次先根遍历满足约束条件的各棵子树，即首先判断子树根的布局是否合法，若合法，则先根遍历该子树，否则剪去该子树分支。 * 程序实现： 这里我们用递归法和非递归法并进行比较 递归法 VS 非递归法 首先是两种方法都必须具有的两个函数： 判断函数（int check（int i）） 输出函数（void show（） ） int check(int i) { //判断当前状态是否合法 int j; for(j=1;ji;j++) { if(col[j]==col[i]||fabs(i-j)==fabs(col[j]-col[i])) return 0; } return 1; } 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); } printf(--------------\n); } 递递递递递递归法 void trial(int i) { //进入本函数时，在N×N的棋盘前i-1行已放置了i-1个互不攻击的棋子。 //现从第i行起继续为后续棋子选择合适位置。 //当i N时，求得一个合法布局，输出之。 int j; if(iN) show(); else { for(j=1;j=N;j++) { col[i]=j; if(check(i)) trial(i+1); col[i]=0;//移走棋子 } } } 程序运行 非递归法 * void trial() { //迭代回溯 int i=1; while(i0) { 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--; } } * 程序运行 * 以上两种算法都利用了回溯和试探的有哪些信誉好的足球投注网站技术求解。 回溯法的求解过程实质上是一个先序遍历一颗“状态树”的过