4八皇后问题Word文件下载.docx
- 文档编号:7891402
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:15
- 大小:128.81KB
4八皇后问题Word文件下载.docx
《4八皇后问题Word文件下载.docx》由会员分享,可在线阅读,更多相关《4八皇后问题Word文件下载.docx(15页珍藏版)》请在冰点文库上搜索。
目录
1引言1
1.1问题的提出1
1.2任务与分析1
2程序的主要功能1
2.1回溯功能1
2.2检查功能1
3程序运行平台2
4总体设计2
4.1算法设计2
4.2流程设计3
5模块分析4
5.1回溯模块4
5.2检查模块5
6系统测试6
7结论8
8致谢9
9参考文献10
附录11
摘要
本论文主要采用回溯法和递归法,求解著名的8皇后问题。
即在8×
8格的国际象棋上摆放8个皇后,使其不能互相攻击,也就是任意两个皇后都不能处于同一行、同一列或同一斜线上,求可行方案的总数。
问题的提出者高斯当时认为有76种方案,后来有人用图论的方法解出92种结果。
本论文采用回溯法和递归法,在放置皇后之前,预先判断当前棋盘格子的所在行,列和主从对角线是否已存在皇后,如果存在,则右移一列进行相同判断,若右移至最后一列仍不可放,则行数加一列数回到第一列继续判断;
如果不存在,则在当前格放置一个皇后,同时同行剩下的格子不再进行判断,行数加一列数回到第一列,如此递归进行,直至八个皇后全部符合要求地摆放完毕。
当判断完最后一个格子后,皇后数仍小于8,则回溯到摆放上一个皇后的格子,将上一个皇后摆放在其下一列格子上,再继续上述相同的操作,直至8个皇后摆放完毕。
此程序不仅能求解八皇后问题,还能解决相同类型的N皇后问题。
此外,代码简洁易懂,界面友好,便于操作。
关键词:
n皇后,回溯,递归
1引言
1.1问题的提出
问题由十九世纪著名的数学家高斯提出:
在8×
8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯当时认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。
试编写一个算法,求解并输出此问题的所有合法布局。
1.2任务与分析
求出在一个8×
8的棋盘上,放置8个不能互相捕捉的国际象棋“皇后”的所有布局。
皇后可以沿着纵横和两条斜线4个方向相互捕捉。
输出所有符合要求的解。
分析:
采用回溯法。
例如:
当前棋盘格子所在行数、列数分别为i,j,在放置皇后之前需判断i行,所有小于j的列是否存在皇后;
i-1行j-1列和i-1行j+1列是否已存在皇后。
若都不存在,则当前布局合法,可放置皇后;
否则不可放置,以相同的方法继续判断i行j+1列是否为合法布局,当列数大于8时,行数加1,列数从1自增到8重新开始递归判断,若所有棋盘格子遍历完一次摆放的皇后数小于8,则回溯到上一个皇后的位置,将其移至下一列,再对剩余格子进行同上判断;
若皇后数等于8,则说明找到一种可行方案,再继续使用回溯法寻找其他可行方案。
2程序的主要功能
2.1回溯功能
若当前棋盘格子满足条件,则放置一个皇后,同时同行剩余的格子不再进行判断,即行数加一,列数从一到八递增,重新开始判断,进行下一个皇后的放置。
如果所有的棋盘格子都遍历了完毕,但已放置的皇后数仍小于8,则回溯到上一个已放置的皇后,将其移至同行的下一列,再递归对剩余的皇后进行放置,直至八个皇后放完为止。
2.2检查功能
放置皇后之前对该格做预判断处理,即判断当前格子的所在行,所在列是否已存在皇后,如果不存在,再判断上一行同列的左右两列,即从对角线和主对角线上是否已存在皇后,如果都不存在则可以放置,反之则不可放置。
3程序运行平台
WINDOWSXP/WIN7
VC++6.0。
具体操作如下:
进入VisualC++6.0开发环境,在开发环境的主窗口中选择File|New菜单项,在弹出的对话框中单击Project选项卡,选择C++SourceFile,命名为“八皇后问题”,再制定保存路径,单击OK键完成新建。
再在编辑窗口中编辑代码,编译,链接,执行,最后对其进行调试。
4总体设计
4.1算法设计
check(introw,intline)//检验当前格是否可放
{//row代表行,line代表列
if(Queen[i][line]==queen)//同列已存在queen
returnfalse;
if(Queen[row][i]==queen)//同行已存在queen
if(Queen[i][j]==queen)//左上方已存在queen
if(Queen[i][j]==queen)//右上方已存在queen
returntrue;
//同行同列,主从对角线都不存在queen}
backtrack(intn1,intn2)//回溯法,n1代表棋盘格数,n2代表王后数
{if(n1>
=n*n||n2==n)//棋盘是否放满或王后是否放完
{if(n2==n)//王后放完
{printf("
%c"
Queen[i][j]);
}}
else
{introw=n1/n,line=n1%n;
//得到当前格子的所在行和列
if(check(row,line))//如果可放,则放
{Queen[row][line]=queen;
//当前格置为queen
backtrack(n1+1,n2+1);
//放下一个queen
Queen[row][line]=blank;
//还原状态}
backtrack(n1+1,n2);
//不可放,则检查下一格}}
4.2流程设计
总体设计的流程图如图4.1所示:
图4.1总体流程图
5模块分析
5.1回溯模块
代码分析:
{charch;
if(n1>
{if(n2==n)//王后放完
{printf("
\t\tNo.%d:
\n\n\t\t"
++total);
for(inti=0;
i<
n;
i++)
{for(intj=0;
j<
j++)
printf("
printf("
\n\t\t"
);
}
ch=getchar();
printf("
\n\n"
}
}
else
{introw=n1/n,line=n1%n;
if(check(row,line))//如果可放,则放
{Queen[row][line]=queen;
backtrack(n1+1,n2+1);
Queen[row][line]=blank;
//还原状态
backtrack(n1+1,n2);
//不可放,则检查下一格
}
5.2检查模块
检查模块流程图如图5.1所示:
图5.1检查模块流程图
check(introw,intline)//检验当前格是否可放
{
inti,j;
for(i=row-1;
i>
=0;
i--)
if(Queen[i][line]==queen)//同列已存在queen
for(i=line-1;
if(Queen[row][i]==queen)//同行已存在queen
returnfalse;
for(i=row-1,j=line-1;
(i>
=0)&
&
(j>
=0);
i--,j--)
if(Queen[i][j]==queen)//左上方已存在queen
returnfalse;
for(i=row-1,j=line+1;
(j<
n);
i--,j++)
if(Queen[i][j]==queen)//右上方已存在queen
returnfalse;
returntrue;
//同行同列,主从对角线都不存在queen
6系统测试
运行结果:
图1摆放方案
图2摆放方案
图3摆放方案
图4摆放方案
从上述结果可知,此程序能够很好地解决八皇后问题,以至于解决n皇后问题,并能够将运行结果以友好的界面呈现在用户面前,能够方便用户的使用,所以说此次设计还是比较成功的。
7结论
回溯法号称算法中“通用的解题方法”。
此次课程设计通过回溯法不仅能成功地解决八皇后问题,还能解决n皇后问题。
经过此次对八皇后问题的解决,再次加深了我对这种思想的理解。
刚开始拿到题的时候,虽然对题早有耳闻,但不曾亲自解决过,同时也无从下手。
通过查阅资料,总结了几种较为常见的算法,在递归与非递归中,最后选择了较为通用的递归算法。
在程序设计时,在该用一维数组还是二维数组问题上困惑了很久,但最终选择了较容易让人理解的二维数组进行解题。
此程序有以下几大优点:
1、代码简练易懂;
2、界面友好,方便用户使用;
3、不仅能成功地解决八皇后问题,还能解决同类型的N皇后问题。
8致谢
首先需要感谢的是指导老师谢春芝老师,在她的督促下才能按时完成这个课程设计,并且对于各种提出的问题很热情的解答。
再者需要感谢的是交过我C语言的王秀华老师,没有她的教导自然就不可能有基础来完成课程设计了。
整个完成的过程中周围的同学给了不少帮助,而且帮忙解决了很多想不通的问题,在此真的非常感激每个人!
有进步是因为有帮助!
9参考文献
[1]严蔚敏吴伟民著.《数据结构》(C语言版)(第三版).北京:
清华大学出版社2007.4
[2]谭浩强著.《C程序设计》(第三版).北京:
清华大学出版社;
2006.9
[3]AnanyLevitin著.潘彦译《算法设计与分析基础》(第二版).北京:
2010.1
[4][美]S巴斯著.计算机算法:
设计和分析引论.朱洪等译上海:
复旦大学出版社;
1985.1
附录
#include<
stdio.h>
#defineMAX20
charQueen[MAX][MAX];
enum{blank='
.'
queen='
Q'
};
intn;
inttotal=0;
intcheck(introw,intline)//检验当前格是否可放
{
inti,j;
for(i=row-1;
returnfalse;
for(i=line-1;
if(Queen[row][i]==queen)//同行已存在queen
for(i=row-1,j=line-1;
if(Queen[i][j]==queen)//左上方已存在queen
for(i=row-1,j=line+1;
if(Queen[i][j]==queen)//右上方已存在queen
returntrue;
//同行同列,主从对角线都不存在queen
voidbacktrack(intn1,intn2)//回溯法,n1代表棋盘格数,n2代表王后数
charch;
{
if(n2==n)//王后放完
{
{
for(intj=0;
introw=n1/n,line=n1%n;
Queen[row][line]=queen;
voidmain()
printf("
Pleaseinsertthenumberofqueen:
"
scanf("
%d"
&
for(inti=0;
for(intj=0;
Queen[i][j]=blank;
backtrack(0,0);
printf("
关于%d王后的求解方法有%d种!
\n"
n,total);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题