八皇后问答教学规划报告

1、数据结构课程设计报告八皇后问题（院）: 数学学院业：信息与计算科学级:02班学生姓名 王天宇 学号:20096390 指导教师：设计任务书课题名称1.用C+语言平台将一个8*8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实设计现.目的2.通过这次课程设计，提高自己的编程能力，熟悉C+的编程坏境，为以后的程序开发打下基础.实验1)语言平台：tc+ 或VC+6.0 ；环境2) 执行文件：八皇后.exe试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并任务给出所有的解。要求1.课题综述1. 1课题的来源及意义八皇后问题是一个古

2、老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课

3、题。1. 2面对的问题1） 解决冲突问题: 这个问题包括了行，列，两条对角线;列：规定每一列放一个皇后，不会造成列上的冲突;行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态;2）使用数据结构的知识，用递归法解决问题。2概要设计本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的:1 ）解决冲突问题: 这个问题包括了行，列，两条对角线;列：规定每一列放一个皇后，不会造成列上的冲突;行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的

4、标记置为被占领状态;对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为（i,j）,要么（i+j）是常数，要么（i-j）是常数。因此，当第I个皇后占领了第J列后，要同时把以（i+j）、（i-j）为下标的标记置为被占领状态。2）数据结构的实现 而对于数据结构的实现，学生则是着重于 数组aI : a I表示第I个皇后放置的列；I的范围：1.8;对角线数组：bj（主对角线）,cj（从对角线），根据程序的运行，去决定主从对角线是否放入皇后;3.详细设计和实现4.1.1算法描述数据初始化。B、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后

5、的要求）,先测试当前位置（n , m）是否等于0 （未被占领）。如果是，摆放第n个皇后, 并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一 个位置（n，m+1 ），但是如果当nv=8，m=8时，发现此时已无法摆放时，便要 进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不 断“回溯”的寻找解的方法，称为“回溯法”C、使用数组实现回溯法的思想。D、当n>8时，便打印出结果。E、输出函数我使用printf输出，运行形式为：第 m种方法为：*5.代码编写及详细注释 #includeviostream> using names pace st

6、d;int a8,b8,c30,d30;int i, k,X=0,Y=0;void p rintOint t,n;Y+;coutvv"tNo."vvYvv": nt"/矩阵形式的第丫种情况for (k=1;kv9;k+)n=ak;for(t=1;tvn;t+)coutvv"x "coutvv"Q "t+;for(t;tv9;t+)coutvv"x "coutvv"nt"coutvv"n"void PI aceQueen(int i)int j ,e=1;f

7、or (j=1;jv9;j+)if (bj=0) &&( ci+j=0)&& (di-j=O)ai=j;bj=1;ci+j=1;di-j=1;if (i<8)PlaceQueen(i+1);elseprintO;II打印结果bj=0；/回溯ci+j=0;di-j=0;e+;int main()int choice,e=1;char ch;coutvv"nnt*Welcometo EightQueeninquiries software p roblems *nn"for( k=0;kv24;k+)/数据初始化bk=0;ck=0;dk=0

8、;ch='y'while(ch='y'|ch='Y')coutvv"ntcoutvv"nt* coutvv"nt*No.1视图矩阵形式显示皇后的位置*MNo.0coutvv"nt*coutvv"nt* coutvv"nt请选择菜单号(No.0-No.1)M.cin>>choice;switch(choice)case 1:coutvv"nt使用回车查看下一种情况nn"P laceQueen(l);/从第1个皇后开始放break;case 0:ch=' n'break;default:coutvv"ntt菜单选择错误，请重新输入!n"7.运行与测试7.1运行演示（以下只是少部分