数据结构课程设计-八皇后问题

//运行环境TC3.0#include<math.h> //调用数学函数库#include<stdio.h> //调用标准输入输出函数库#include<conio.h>#include<graphics.h> //调用图形函数库#include<stdlib.h>#define MAX 8 //定义棋盘格数（特别是横轴方向上）int board[MAX]; //纵轴方向格数void Drow() //画棋盘{int i;int Driver=VGA,Mode=VGAHI; //初始化显示器initgraph(&Driver,&Mode,"d:\\tc\\bgi");setfillstyle(SOLID_FILL,BLUE); //棋盘底色模式bar(5,15,600,500); //棋盘外框（二维）setcolor(YELLOW); //棋盘边框颜色for(i=0;i<=9;i++){line(10,20+50*i,460,20+50*i); //画行}for(i=0;i<=9;i++){line(10+50*i,20,10+50*i,470); //画列}line(460,20,560,20);line(10,470,560,470);line(560,470,560,20);setcolor(RED);outtextxy(465,30,"WuShangjie"); //版权注释outtextxy(465,45,"Eight Queue");outtextxy(465,60,"CopyRight2.0");outtextxy(415,440,"Start"); //屏幕输出文本坐标标记outtextxy(385,440,"0");outtextxy(335,440,"1");outtextxy(285,440,"2");outtextxy(235,440,"3");outtextxy(185,440,"4");outtextxy(135,440,"5");outtextxy(85,440,"6");outtextxy(35,440,"7");outtextxy(415,455,"Point");outtextxy(435,390,"0");outtextxy(435,340,"1");outtextxy(435,290,"2");outtextxy(435,240,"3");outtextxy(435,190,"4");outtextxy(435,140,"5");outtextxy(435,90,"6");outtextxy(435,40,"7");}void DrowCircle(int i,int j) //话棋子{char text[80];setfillstyle(SOLID_FILL,YELLOW);setcolor(YELLOW);circle(385-50*i,395-50*j,15);floodfill(385-50*i,395-50*j,YELLOW); //圆内颜色填充setcolor(RED);sprintf(text,"%d,%d",i,j); //棋子上坐标标记outtextxy(385-50*i-14,395-50*j,text);}void GiveDrowIn(int i,int j) //过去显示棋子清除{setfillstyle(SOLID_FILL,BLUE); //将填充颜色设置与底色相同setcolor(BLUE); //将画笔颜色设置与底色相同circle(385-50*i,395-50*j,15);floodfill(385-50*i,395-50*j,BLUE); //一定区域内填充outtextxy(385-50*i-14,395-50*j," ");}void show_result() //调度相关算法求出所有结果{int j=0;while(j<MAX){DrowCircle(j,board[j]);getch();j++;}getch();for(j=0;j<MAX;j++){GiveDrowIn(j,board[j]); //释放上回显示棋子区域}getch();}int check_cross(int n) //判断棋子是否冲突函数{int k;for(k=0;k<n;k++){if(board[k]==board[n]||(n-k)==abs(board[k]-board[n])) //是否同行，是否同对角线return 1;}return 0;}void put_chess(int n) //八皇后摆列方式逐个显示函数{for(int l=0;l<MAX;l++){board[n]=l;if(!check_cross(n)){if(n==MAX-1) {getch();show_result();}else put_chess(n+1);}}}void main() //主函数{Drow();put_chess(0);//to the end of the programgetch();exit(1);}免责声明：文档在线网（文档中国）中所有的文档资料均由文档在线网会员提供。

⼋皇后问题（经典算法-回溯法）问题描述：⼋皇后问题（eight queens problem）是⼗九世纪著名的数学家⾼斯于1850年提出的。

问题是：在8×8的棋盘上摆放⼋个皇后，使其不能互相攻击。

即任意两个皇后都不能处于同⼀⾏、同⼀列或同⼀斜线上。

可以把⼋皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能互相攻击。

思路：使⽤回溯法依次假设皇后的位置，当第⼀个皇后确定后，寻找下⼀⾏的皇后位置，当满⾜左上、右上和正上⽅向⽆皇后，即矩阵中对应位置都为0，则可以确定皇后位置，依次判断下⼀⾏的皇后位置。

当到达第8⾏时，说明⼋个皇后安置完毕。

代码如下：#include<iostream>using namespace std;#define N 8int a[N][N];int count=0;//判断是否可放bool search(int r,int c){int i,j;//左上+正上for(i=r,j=c; i>=0 && j>=0; i--,j--){if(a[i][j] || a[i][c]){return false;}}//右上for(i=r,j=c; i>=0 && j<N; i--,j++){if(a[i][j]){return false;}}return true;}//输出void print(){for(int i=0;i<N;i++){for(int j=0;j<N;j++){cout<<a[i][j]<<" ";}cout<<endl;}}//回溯法查找适合的放法void queen(int r){if(r == 8){count++;cout<<"第"<<count<<"种放法\n";print();cout<<endl;return;}int i;for(i=0; i<N; i++){if(search(r,i)){a[r][i] = 1;queen(r+1);a[r][i] = 0;}}}//⼊⼝int main(){queen(0);cout<<"⼀共有"<<count<<"放法\n"; return 0;}。

计算机科学与技术专业数据结构课程设计报告设计题目：八皇后问题目录1需求分析 (2)1.1功能分析 (2)1.2设计平台 (3)2概要设计 (3)2.1算法描述 (4)2.2算法思想 (5)2.3数据类型的定义 (5)3详细设计和实现 (6)3.1算法流程图 (6)3.2 主程序 (6)3.3 回溯算法程序 (7)4调试与操作说明 (9)4.1调试情况 (9)4.2操作说明 (9)5设计总结 (11)参考文献 (12)附录 (12)1需求分析1.1功能分析八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。

高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

现在我们已经知道八皇后问题有92个解答。

1、本演示程序中，利用选择进行。

程序运行后，首先要求用户选择模式，然后进入模式。

皇后个数设0<n<11。

选择皇后个数后，进入子菜单，菜单中有两个模式可以选择。

2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令：相应的输入数据和运算结果显示在其后。

3、程序执行的命令包括：1）进入主菜单。

2）选择皇后问题，输入是几皇后。

3）进入子菜单。

4)选择皇后显示模式。

5）选择结束4、测试数据1）N的输入为4；2）共有2个解答。

3）分别是○●○○○○●○○○○●●○○○●○○○○○○●○○●○○●○○1.2设计平台Windows2000以上操作系统；Microsoft Visual C++ 6.02概要设计问题：N后问题问题描述：国际象棋中皇后可以攻击所在行，列，斜线上的每一个位置，按照此规则要在一个n*n的棋盘上放n个皇后使每一个皇后都不互相攻击问题分析：引入1个数组模拟棋盘上皇后的位置引入3个工作数组行数组[k]=1,表示第k行没有皇后右高左低数组[k]=1,表示第k条右高左低的斜线上没有皇后左高右低数组[k]=1,表示第k条左高右低的斜线上没有皇后观察棋盘找到规律同一右高左低的斜线上的方格，它们的行号和列号之和相等；同一左高右低的斜线上的方格，它们的行号和列号只差相等；开始时，所有行和斜线上都没有皇后，从第一列的第一行配置第一个皇后开始，在第m列的皇后位置数组[m]行放置了一个合理的皇后之后，准备考察第m+1列时，在数组行数组[]，右高左低数组[]，左高右低数组[]中为第m列，皇后位置数组[m]的位置设定有皇后标志如果按此放置位置得不到结果，则把当前列中的有皇后标记改为无皇后标记。

目录一需求分析 (1)1.1程序的功能： (1)1.2程序的输入输出要求： (1)二概要设计 (3)2.1程序的主要模块： (3)2.2程序涉及： (3)三详细设计 (3)3.1相关代码及算法 (4)3.1.1 定义相关的数据类型如下：....................... 错误!未定义书签。

3.1.2 主模块类C码算法： (4)3.1.3 画棋盘模块类C码算法 (5)3.1.4 画皇后模块类C码算法： (5)3.1.5 八皇后摆法模块（递归法）： (6)3.1.6 初始化模块 (7)3.1.7 输出摆放好的八皇后图形（动态演示）： (7)3.2相关流程图 (9)四调试分析 (12)五设计体会 (13)六附录 (13)七参考文献 (17)一需求分析1.1 程序功能：八皇后问题是一个古老而著名的问题。

该问题是十九世纪著名的数学家高斯1850年提出的。

八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。

因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。

虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。

即可完成。

如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。

如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。

这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。

安徽建筑工业学院数据结构设计报告书院系数理系专业信息与计算科学班级11信息专升本学号11207210138姓名李晓光题目八皇后指导教师王鑫1．程序功能介绍答：这个程序是用于解决八皇后问题的。

八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。

做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。

我的程序进入时会让使用者选择程序的功能，选【1】将会通过使用者自己手动输入第一个皇后的坐标后获得答案；选【2】将会让程序自动运算出固定每一个皇后后所有的排列结果。

2．课程设计要求答：（1）增加函数，完成每输入一组解，暂停屏幕，显示“按任意键继续！”。

（2）完善程序，编程计算八皇后问题共有集中排列方案。

（3）增加输入，显示在第一个皇后确定后，共有几组排列。

（4）将每组解的期盼横向排列输出在屏幕上，将五个棋盘并排排列，即一次8行同时输出5个棋盘，同样完成一组解后屏幕暂停，按任意键继续。

（5）求出在什么位置固定一个皇后后，解的数量最多，在什么位置固定皇后后，解的数量最少，最多的解是多少，最少的解是多少，并将最多，最少解的皇后位置及所有的解求出，同样5个一组显示。

3．对课程题目的分析与注释答：众所周知的八皇后问题是一个非常古老的问题，问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。

按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。

因此，本课程设计的目的也是通过用C++语言平台在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。

使用递归方法最终将其问题变得一目了然，更加易懂。

首先要用到类，将程序合理化：我编辑了一个盘棋8*8的类：class Board，还有个回溯法的类：class Stack，关键的类好了，然后编辑好类的成员，然后编辑主函数利用好这些类的成员，让其运算出结果。

⼋皇后以及N皇后问题分析⼋皇后是⼀个经典问题，在8*8的棋盘上放置8个皇后，每⼀⾏不能互相攻击。

因此拓展出 N皇后问题。

下⾯慢慢了解解决这些问题的⽅法：回溯法：回溯算法也叫试探法，它是⼀种系统地搜索问题的解的⽅法。

回溯算法的基本思想是：从⼀条路往前⾛，能进则进，不能进则退回来，换⼀条路再试。

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满⾜某种要求的可能或最优的情况，从⽽得到整个问题的解。

回溯算法就是解决这种问题的“通⽤算法”，有“万能算法”之称。

N皇后问题在N增⼤时就是这样⼀个解空间很⼤的问题，所以⽐较适合⽤这种⽅法求解。

这也是N皇后问题的传统解法，很经典。

算法描述：1. 算法开始，清空棋盘。

当前⾏设为第⼀⾏，当前列设为第⼀列。

2. 在当前⾏，当前列的判断放置皇后是否安全，若不安全，则跳到第四步。

3. 在当前位置上满⾜条件的情况： 在当前位置放⼀个皇后，若当前⾏是最后⼀⾏，记录⼀个解； 若当前⾏不是最后⼀⾏，当前⾏设为下⼀⾏，当前列设为当前⾏的第⼀个待测位置； 若当前⾏是最后⼀⾏，当前列不是最后⼀列，当前列设为下⼀列； 若当前⾏是最后⼀⾏，当前列是最后⼀列，回溯，即清空当前⾏以及以下各⾏的棋盘，然后当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置； 以上返回第⼆步。

4.在当前位置上不满⾜条件： 若当前列不是最后⼀列，当前列设为下⼀列，返回到第⼆步； 若当前列是最后⼀列，回溯，即，若当前⾏已经是第⼀⾏了，算法退出，否则，清空当前⾏以及以下各⾏的棋盘，然后，当前⾏设为上⼀⾏，当前列设为当前⾏的下⼀个待测位置，返回第⼆步。

如何判断是否安全：把棋盘存储为⼀个N维数组a[N]，数组中第i个元素的值代表第i⾏的皇后位置，这样便可以把问题的空间规模压缩为⼀维O(N)，在判断是否冲突时也很简单， ⾸先每⾏只有⼀个皇后，且在数组中只占据⼀个元素的位置，⾏冲突就不存在了， 其次是列冲突，判断⼀下是否有a[i]与当前要放置皇后的列j相等即可。

数据结构课程设计报告八皇后问题设计任务书指导教师（签章）：年月日摘要：众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。

要求编写实现八皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。

本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。

在实践中培养独立分析问题和解决问题的作风和能力。

要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。

通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。

递归是一种比较简单的且比较古老的算法。

回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。

而枚举法，更是一种基础易懂简洁的方法。

把它们综合起来，就构成了今天的算法。

不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。

关键词：八皇后；递归法；回溯法；数组；枚举法…….目录1 课题综述…………………………………………………………………………………1.1 八皇后问题概述---------------------------------------------------1.2 预期目标---------------------------------------------------------1.3 八皇后问题课题要求-----------------------------------------------1.4 面对的问题-------------------------------------------------------2 需求分析…………………………………………………………………………………2.1 涉及到的知识基础--------------------------------------------------2.2 总体方案----------------------------------------------------------3 模块及算法设计……………………………………………………………………………………3.1 算法描述----------------------------------------------------------3.2．详细流程图-------------------------------------------------------4.代码编写…………………………………………………………………………5 程序调试分析……………………………………………………………………………………6 运行与测试……………………………………………………………………………………总结…………………………………………………………………………1 课题综述1.1 八皇后问题概述八皇后问题是一个古老而著名的问题。

数据结构课程设计题目1．八皇后问题设计要求：在棋盘上摆放八个皇后，使任意两个不在同一行，同一列，及同一对斜线上。

皇后的摆位任意，由用户设定，程序给出剩余皇后的摆位。

2.哈夫曼编/译码器；设计要求：针对字符集A及其各字符的频率值（可统计获得）给出其中给字符哈夫曼编码，并针对一段文本（定义在A上）进行编码和译码，实现一个哈夫曼编码/译码系统。

3.关键路径设计要求：对于任何大型工程项目（由若干小工程组成），求其关键路径。

4.最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

5.最短路径问题设计要求：对给定有向图，设计图的存储结构，求出各顶点之间最短路径。

5.校园导航问题设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

6.一元多项式的代数运算设计要求：计算任意两个一元多项式的加法、减法以及乘法。

7.算术表达式求值设计要求：将任意一个算术表达式转化为逆波兰表示，并根据逆波兰表示计算表达是的值。

8、运动会分数统计任务：参加运动会有n个学校，学校编号为1……n。

比赛分成m个男子项目，和w个女子项目。

项目编号为男子1……m，女子m+1……m+w。

不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。

（m<=20,n<=20）要求：1).可以输入各个项目的前三名或前五名的成绩；2)．能统计各学校总分，3)．可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。

9、订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。