画鸵萌宠网
实践教学
*******************
兰州理工大学
计算机与通信学院
2012年春季学期
算法与数据结构 课程设计
题 目： N皇后问题 专业班级：计算机科学与技术二班 * 名： *** 学 号： ******** 指导教师： **
成 绩：
1
目 录
摘 要 ....................................................................................... 错误!未定义书签。 前 言 ....................................................................................... 错误!未定义书签。 正 文 ....................................................................................... 错误!未定义书签。 1. 采用类C语言定义相关的数据类型 .......................................................... 3 2. 各模块的伪码算法 ...................................................................................... 4 3. 函数的调用关系图 ...................................................................................... 5 4. 调试分析 ...................................................................................................... 6 5. 测试结果 ...................................................................................................... 7 6. 源程序（带注释） .................................................................................... 10 总 结 .................................................................................................................... 14 参考文献 ................................................................................................................ 15 致 谢 .................................................................................................................... 16
2
摘要
N皇后问题要求在一个N*N的棋盘上放上N个皇后，使得每一个皇后既攻击不到另外N-1个皇后，也不被另外N-1个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，N皇后问题等于要求N个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。
而本课程设计本人的目的也是通过用c语言平台将一个N*N的棋盘上放上N个皇后，使得每一个皇后既攻击不到另外N-1个皇后，也不被另外N-1个皇后所攻击的X种结构予以实现．
关键词：八皇后；攻击；规则；
数据结构课程设计
前言
八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。
在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。本课设探求了N皇后的解法。
2
数据结构课程设计
正文
1.采用类c语言定义相关的数据类型
1.1涉及到的知识点
本次课程设计中，用到的主要知识有：递归法、回溯法的应用。 抽象数据类型的定义
void Print(int N,int x[]//印出结果
int Judge(int k,int x[]) //递归寻找摆放皇后位子 void main() //主函数调用 int SUM=0;//统计有多少种可能 1.2数据初始化
1.3从i列开始摆放第i个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（i，j）是否等于0（未被占领）。如果是，摆放第i个皇后，并宣布占领（记得要横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（i，j+1），但是如果当i<=MAX，j=MAX时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。
3
数据结构课程设计
2.各模块的伪码算法
2.1定义数组x，x[i]表示第i个皇后放置的列，范围为1-8。 2.2行冲突标记数组j，j=x[i]=0 表示第j行空闲， j=1 表示第j行被占领，范围为1-8。
2.3if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函数名: abs; 功能: 求整数的绝对值 ;
2.4当n>8时，便打印出结果。
2.5int x[8] //表示第i个皇后放置的列，范围为1-8。
2.6void backtrack(int t,int N,int x[]) // 把棋子放到棋盘上
2.7Print(MAX,x); // 找到其中一种放法，印出結果 else backtrack(t+1,N,x);
4
数据结构课程设计
3.函数的调用关系图
开始开始 数据初始化 从n列开始摆放第n个皇后 从第i列开始摆放第i个皇后 2 1
当前位置（i，j） 是否被占领 摆放皇后，并 宣布占领 测试下个位置 i=i+1 j=j+1 0
i<=MAX&&j=MAX 进行回溯 5 打印 结果 数据结构课程设计
4.调试分析
4.1 遇到的问题及解决方法
1)由于对八个皇后放置的位置不能一次确定，而且前一个皇后的放置位置直接影响着后面的放置位置，使程序调试时要花费不少时间。
2)本程序有些代码重复出现，显得程序的有些代码看起来很杂乱。但其中最主要的问题是逻辑错误导致程序死循环或不循环或循环一小部分,但是编译时却没有错误,就是没有正确的输出答案。比如说，在void Print(int N,int x[])中有for(int i=0;i 本程序模块划分比较合理，且利用指数组存储棋盘，操作方便。至于整体的系统架构，为了简单起见，这样的系统可以分成两个模块，第一个模块是负责模拟问题、提供算法，而另外一个模块则致力于窗口演示，是一个窗体应用程序 4.4 算法的改进 这道题可以用非递归循环也可以用递归循环的方法来做，这里我用了后者，其方法是分别一一测试每一种皇后摆法，直到得出正确的答案即所谓的回溯法。 4.5 程序使用说明 （1） 本程序的运行环境为DOS操作系统 （2） 进入演示程序后即显示文本方式的用户界面 （3） 进入界面后，就会提示输入字符串的输入形式，在八皇后求解程序中，只要你按照提示选择输出解的格式，即可输出N皇后问题的解。此处N过大会出现数据溢出，所以最好以N=8或N=9实验。并统计出结果。 6 数据结构课程设计 5.测试结果 5.1 初步运行界面 5.2选择八皇后作为实例并输出排布结果 7 数据结构课程设计 5.3八皇后排布结果部分截图（●为皇后位置） 5.4统计八皇后棋局排布总数 8 数据结构课程设计 5.5输出八皇后棋局统计总数结果（92种） 5.6输出十皇后棋局排布部分截图 9 数据结构课程设计 6.源程序 #include #include void Print(int N,int x[]) //印出結果 { int MAX=N; } int Judge(int k,int x[]) //判断是否在同一直、橫、斜线上有其它棋子 { int i; for(i=0;i for(int i=0;i for(int j=0;j printf(\"○\"); printf(\"●\"); int N; printf(\"这是一个N皇后问题...\\n请输入N=\"); scanf(\"%d\return N; int shezhi(){ //设置为N皇后问题 printf(\"\\n\"); 数据结构课程设计 } if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函数名: abs; 功能: 求整数的绝对值 ; return 0; return 1; void backtrack(int t,int N,int x[]) // 把棋子放到棋盘上 { int MAX=N; int i; for(i=0;i printf(\"* * * * * * * * * * * * * * * * * *\\n\"); printf(\"* 数据结构课程设计 *\\n\"); printf(\"* N-皇后问题 *\\n\"); } } else backtrack(t+1,N,x); } { if(t==MAX-1){ Print(MAX,x); // 找到其中一种放法，印出結果 printf(\"* 学生：胡江文 *\\n\"); printf(\"* 学号：10240104 *\\n\"); } 11 printf(\"* *\\n\"); printf(\"* * * * * * * * * * * * * * * * * *\\n\"); printf(\"\\n\\n\"); printf(\"1.设置为N皇后问题。\\n\"); printf(\"2.输出棋局排布结果。\\n\"); printf(\"3.统计棋局排布总数。\\n\"); printf(\"4.清屏。\\n\"); printf(\"\\n\\n\"); 数据结构课程设计 void main() { int N; int x[10]; printf(\"\\n\\n\\n\"); char flag=1; while(flag){ int n; Introduce(); char a; printf(\"您确定要进行上述操作吗?(Y/N):\"); a=getchar(); while(a=='Y'||a=='y'){ printf(\"请选择：\"); scanf(\"%d\ switch(n){ case 1: N=shezhi(); break; case 2: backtrack(0,N,x); printf(\"按任意键返回...\"); getch(); system(\"cls\"); Introduce(); break; case 3: printf(\"统计结果:%d\\n\ printf(\"按任意键返回...\"); getch(); system(\"cls\"); Introduce(); break; 12 数据结构课程设计 case 4: printf(\"按任意键返回...\"); getch(); system(\"cls\"); Introduce(); break; default: printf(\"输入错误...\\n\"); printf(\"按任意键返回...\"); getch(); system(\"cls\"); Introduce(); break; } } } } 13 数据结构课程设计 总结 在本次课程设计的学习过程中,我在其中的最大的收获,就是得到了许多的经验以及软件设计的一些新的思路. 迈着时间的步伐，这次的课程设计也即将结束，但这个学期数据结构的学习还是具有相当大的意义，特别是这次的课程设计,它从一个程度上改变了我们的编程思想，如何将一个程序快速而又准备的进行编写，进行编译，都成为了我思考的重点，也通过这一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，并且通过修改，加入新的算法去尝试改变自己的一些编程思想。保持更新算法的速度，这才是关键。 比如说, N皇后在变成初期,由于不自觉的采用了非递归的算法,结果大大增加了程序的复杂程度,并且也让整个程序的时间复杂度变得更大. 在这次的八皇后问题中可以用概率算法,也可以采用传统的递归算法,这里我用了后者.而且还用到了回溯法. 回溯法是允许我们在尝试某些选择失败后，能系统的尝试完所有可能的选择。在八皇后问题中越早放置的皇后，她的选择就越多；而越晚放置的皇后，她的选择就越少。八皇后问题和迷宫问题是很相似的，因此，若采用回溯，将能很好很快而且高效率的解决问题。这便是在这次的一些创新之处!当然设计N皇后问题，基本思想不变 通过这次的课程设计，我从中得到了许多经验和软件设计的一些新思路；从这个八皇后问题设计以及分析中，本人从中理解到了数据结构对于软件设计的重要性，它的使用，可以改变软件的运行周期，思路从繁化简，并且都能够通过其相关引导，将本身以前编程思想进行扩充，发展.这也是在这次课程设计中我所掌握得到的。 14 数据结构课程设计 参考文献 1 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社. 2 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社. 3 《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.《c语言程序设计》. 清华大学出版社. 5．数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译 电子工业出版社 2001 年1月 15 因篇幅问题不能全部显示，请点此查看更多更全内容