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

《关于八皇后问题的c++课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告学院、系：专业名称：课程设计科目VC++程序课程设计学生姓名：指导教师：完成时间：八皇后问题一、设计任务与目标1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的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的范围

3、：1..8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；算法描述A、数据初始化。B、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得要横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”

4、的寻找解的方法，称为“回溯法”。C、使用数组实现回溯法的思想。D、当n>8时，便打印出结果。E、输出函数我使用printf输出，运行形式为：第m种方法为：********三、程序框图或流程图，程序清单与调用关系四、全部源程序清单#include#include#include#include#include#defineQUEENS8intiCount=0;//!记录解的序号的全局变量。intSite[QUEENS];

5、//!记录皇后在各行上的放置位置的全局数组。voidQueen(intn);//!递归求解的函数。voidOutput();//!输出一个解。intIsValid(intn);//!判断第n个皇后放上去之后，是否有〉冲突。voidmain()/*----------------------------Main：主函数。----------------------------*/{system("title递归算法八皇后问题");cout<<""<<"八皇后的解法："<

6、-------------------------------"<

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

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