八皇后问题_实验报告_源程序.doc

八皇后问题 实验报告需求分析八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出的。八皇后问题要求在一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子，问有多少种不同的摆法？并找出所有的摆法。因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过C语言平台将一个的棋盘上放上个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现最终将其问题变得一目了然，更加易懂。概要分析本课件学生是用递归来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，学生的主要思路以及思想是这样的： 1.解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；对角线：对角线有两个方向。在这学生把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。(1) 满足上述条件的八个皇后，必然是每行一个，每列一个。(2) 棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。如果我们把88 的棋盘看成是一个平面直角坐标系，则八皇后问题就可以用数学语言来描述了，任意两个皇后在平面上的坐标应该同时满足以下三个条件： 两个皇后不在同一行：两个皇后的横坐标不相等； 两个皇后不在同一列：两个皇后的纵坐标不相等； 两个皇后不在同一条斜线上：两个皇后的横坐标之差的绝对值不等于两个皇后的纵坐标之差的绝对值。2.数据结构的实现对于数据结构的实现，则是着重于:（1） 数组chessi：chess i表示第i个皇后放置的列；i的范围：1-8;对角线数组：bj(主对角线),cj（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；（2）数据初始化。（3）从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先用check函数测试当前位置是否未被占领:如果是，摆放第n个皇后，并宣布占领(切记要横列竖列斜列一起来)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当n8时，便一一打印出结果。详细设计3.设计思想：本程序通过对关键函数putchess的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的数组和回溯的方法。通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是，则继续放置下一个皇后。 4.源代码分析： 数组chess8记录了每个可行结果中，每行皇后的位置，以数字1-8表示。子函数check检查对于每个i,新的皇后是否与第i行冲突。子函数showchess将每个符合要求的chess8输出到文件8QANS.txt。子函数putchess用递归放置每行的皇后，并调用函数check检查可行性。如果此棋盘已排满，则调用showchess函数输出布局。主函数中调用putchess函数做主要工作。5.可改进处：输出到文件的形式可以优化为棋盘模式，甚至优化过的图形模式。代码展示/八皇后问题，结果输出到同目录下的8Qans.txt。#include int result = 1;int chess8;int check(int n)/依次检查新的皇后是否与第i行冲突int i;for(i=1; i=n-1;i+)if(chessn=chessi+(n-i)|chessn=chessi-(n-i)|chessn=chessi)return 0;return 1;void showchess()/将结果输出到8Qans.txt，“(a):b” 表示第a行第b列放置皇后int i;FILE *fp;fp=fopen(8Qans.txt,a);fprintf(fp,Result - %dn,result);for(i=1; i=8;i+)fprintf(fp,(%d): %dn,i,chessi);+result;fclose(fp);void putchess(int n)/逐行放置皇后int i;if(n=8)for(i=1;i=8;i+)chessn=i;/调用 check函数检查可行性if(check(n)=1)if(n=8)/全部填完则输出结果showchess();else/否则继续放置下一个皇后，递归调用putchess(n + 1);int main()/主函数调用pu