八皇后问题课程设计报告

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

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

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

4、列放一个皇后，不会造成列上的冲突； 行：当第 I 行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要 把以 I 为下标的标记置为被占领状态； 对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角 线。在同一对角线上的所有点（设下标为（i,j）,要么（i+j）是常数，要么（i-j）是常数。 因此，当第I个皇后占领了第J列后，要同时把以（i+j）、（i-j）为下标的标记置为被占领 状态。 2）数据结构的实现 而对于数据结构的实现，学生则是着重于 : 数组aI: a I表示第I个皇后放置的列；I的范围：1.8; 对角线数组：bj（主对角线）,cj（从对角线），根据程序的运行，

5、去决定主从对 角线是否放入皇后； 3. 详细设计和实现 算法描述 A、数据初始化。 B、从 n 列开始摆放第 n 个皇后（因为这样便可以符合每一竖列一个皇后的要 求），先测试当前位置（n, m）是否等于0 （未被占领）。如果是，摆放第n个皇后， 并宣布占领（记得姚横列竖列斜列一起设置） ，接着进行递归；如果不是，测试下一 个位置（n，m+1），但是如果当n8时，便打印出结果。 E、输出函数我使用printf输出，运行形式为：第 m种方法为：* * * * * * * * 5. 代码编写及详细注释 #include using namespace std; int a8,b8,c30,d30; int i, k,X=0,Y=0; void print() int t,n; Y+; couttNo.Y ： 0 ?4： 0 0 0 Q 0 0 0 0 Q 0 0 a a a 0 0 0 0 0 0 Q 0 0 Q 0 0 0 0 0 0 0 0 0 0 0 0 0 Q 0 0 0 0 Q 0 0 0 Q 0 0 0 0 0 0 0 0 0 0 Q 0 0 0 0 0 Q- 0 0 0 0 0 0 0 0 0 0 0 0 Q 0 0 0 0 0 Q 0 0 0 0 0 0 0 0 Q 0 0 0 0 0 0 0 0 Q 0 0 0 0 Q 0 0 0 0 0 Q