Eight queens 八皇后问题
Group Members 韩奇 刘源奇 鹿尧
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 ——《百度百科》
八皇后问题的一个解
作为例子，我们将8皇后问题简化为4皇后问题
这是一颗四叉树，树上每个结点表示一个局部布局或一个完整的布局，根结点表示棋盘的初始状态：棋盘上无任何棋子。没个棋子都有四个可选择的位置，但在任何时刻，棋盘的合法布局都必须满足3个约束条件，即任何两个棋子都不能处于同一行、同一列或同一斜线上
求所有布局的过程即为在上述条件下先根遍历状态树的过程。遍历中访问结点的操作为，判别棋盘上是否已经有一个完整的布局（即棋盘上是否已摆上4个棋子），若是，则输出该布局；否则依次先根遍历满足约束条件的各棵子树，即首先判断子树根的布局是否合法，若合法，则先根遍历该子树，否则剪去该子树分支。
2017/3/12
程序实现： 这里我们用递归法和非递归法并进行比较 程序实现： 这里我们用递归法和非递归法并进行比较
递归法 VS 非递归法
首先是两种方法都必须具有的两个函数： 判断函数（int check（int i）） 输出函数（void show（） ）
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;
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");
递递递递递递归法
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;//移走棋子 }
程序运行
非递归法
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--;
程序运行
以上两种算法都利用了回溯和试探的搜索技术求解。 回溯法的求解过程实质上是一个先序遍历一颗“状态树”的过程，只是这颗树不是预先建立的，而是隐含在遍历过程中。 空间代价一般为最长路径的长度， 如果要把整个树存储下来的话，那空间代价是惊人的 2017/3/12
以上