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

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