算法设计与分析实验报告—八皇后问题

《算法设计与分析实验报告—八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析实验报告—八皇后问题-姓名：崔明鑫学号：08208012班级：软件83【问题描述】在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。【问题分析&算法设计】用8元组x[1:n]表示8后问题。其中x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在一列，所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。故若2个皇后放置的位置分别是（i，j）和（k，l），且i–j=k–l或i+j=k+l，则说明这2个皇后处于同一

2、斜线上。这两个方程分别等价于i–k=j–l和i–k=l–j。由此可知，只要

3、i-k

4、=

5、j-l

6、成立，就表明2个皇后位于同一条斜线上。问题的隐约束化成了显约束。用回溯法解决8皇后问题时，用完全8叉树表示解空间。【算法实现】#include"stdio.h"#include"math.h"#include"iostream.h"#defineN8/*定义棋盘大小*/staticintsum;/*当前已找到解的个数*/staticintx[N];/*记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i

7、]列*//*每找到一个解,打印当前棋盘状态*/voidShow(){sum++;cout<<"第"<

8、ut<<"*

9、";else//printf("*");cout<<"

10、";cout<<"---------------------------------";}}/*确定某一位置皇后放置与否，放置则返回1，反之返回0*/intJudge(intk){//测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。x[j]==//x[k]时，两皇后在同一列上；abs(k-j)==abs(x[j]-x[k])时，两皇//后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。for(i

11、ntj=0;j

12、

13、(x[j]==x[k]))return0;return1;}/*主递归函数，搜索解空间中第i层子树*/voidBacktrack(intt){/*t==N时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案*/if(t==N)Show();elsefor(inti=0;i

14、endl;return0;}【运行结果】可知在考虑对称的情况下，8皇后问题共有92种解。