关于八皇后问题的c++课程设计

关于八皇后问题的c++课程设计

ID:2073813

大小:118.50 KB

页数:10页

时间:2017-11-14

关于八皇后问题的c++课程设计_第1页
关于八皇后问题的c++课程设计_第2页
关于八皇后问题的c++课程设计_第3页
关于八皇后问题的c++课程设计_第4页
关于八皇后问题的c++课程设计_第5页
资源描述:

《关于八皇后问题的c++课程设计》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、课程设计报告学院、系:专业名称:课程设计科目VC++程序课程设计学生姓名:指导教师:完成时间:八皇后问题一、设计任务与目标1.用c++语言平台将一个8*8的棋盘上放上8个皇后,使得每一个皇后既攻击不到另外七个皇后,也不被另外七个皇后所攻击的92种结构予以实现。2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程序开发打基础。二、方案设计与论证在8*8的格的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面。我的主要思路以及思想如下:1.解决冲突问题:这个问题包括了行,列,两条对角线;列:规定每一列放一个皇后,不会造成列上的冲

2、突;行:当第I行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以I为下标的标记置为被占领状态;对角线:对角线有两个方向。在这我把这两条对角线称为:主对角线和从对角线。在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。因此,当第I个皇后占领了第J列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。2.数据结构的实现:数组a[I]:a[I]表示第I个皇后放置的列;I的范围:1..8;对角线数组:b[j](主对角线),c[j](从对角线),根据程序的运行,去决定主从对角线是否放入皇后;算法描述A、数据初始化。B、从n列开始摆放第n个皇

3、后(因为这样便可以符合每一竖列一个皇后的要求),先测试当前位置(n,m)是否等于0(未被占领)。如果是,摆放第n个皇后,并宣布占领(记得要横列竖列斜列一起设置),接着进行递归;如果不是,测试下一个位置(n,m+1),但是如果当n<=8,m=8时,发现此时已无法摆放时,便要进行回溯。从问题的某一种可能出发,搜索从这种情况能出发,继续搜索,这种不断“回溯”的寻找解的方法,称为“回溯法”。C、使用数组实现回溯法的思想。D、当n>8时,便打印出结果。E、输出函数我使用printf输出,运行形式为:第m种方法为:********三、程序框图或流程图,程序清单与调用关系四、全部源程序清单#include<

4、conio.h>#include#include#include#include#defineQUEENS8intiCount=0;//!记录解的序号的全局变量。intSite[QUEENS];//!记录皇后在各行上的放置位置的全局数组。voidQueen(intn);//!递归求解的函数。voidOutput();//!输出一个解。intIsValid(intn);//!判断第n个皇后放上去之后,是否有〉冲突。voidmain()/*----------------------------Main:主函数。----

5、------------------------*/{system("title递归算法八皇后问题");cout<<""<<"八皇后的解法:"<

6、{Output();return;}for(i=1;i<=QUEENS;i++)//!n还没到8,在第n行的各个行上依次试探。{Site[n]=i;//!在该行的第i行上放置皇后。if(IsValid(n))//!如果放置没有冲突,就开始下一行的试探。Queen(n+1);}}intIsValid(intn)/*------IsValid:判断第n个皇后放上去之后,是否合法,即是否无冲突。------*/{inti;for(i=0;i

7、;if(abs(Site[i]-Site[n])==(n-i))//!两个皇后在同一对角线上,返回0。return0;}return1;//!没有冲突,返回1。}voidOutput()/*------------Output:输出一个解,即一种没有冲突的放置方案。------------*/{inti;printf("No.%-5d",++iCount);//!输出序号。for(i=0;i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。