八皇后实验报告.doc

实验项目： 八皇后问题 实验目的：通过求解皇后问题，熟悉深度优先搜索法DFS（回溯法（Backtracking Algorithms）技术。 实验内容：由n2个方块排成n行n列的正方形称为n元棋盘。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现要找出使棋盘上n个皇后互不攻击的布局。编制程序解决上述问题，以n=6运行程序，输出结果。 程序简介：将n个皇后放到一个n*n的方阵中，要求每个皇后不在同一行同一列及同一对角线，我的程序是先把每个皇后放在了第零列，然后再按行检查，不符合要求继续下一列，若已经到这一行的最后一列，还没找到符合要求的位置，则回到上一行。 算法设计介绍： 定义一个一维数组，数组的下标是皇后所在位置的行数，数组存的值是皇后所在位置的列数，现将A[0]-A[n-1]都赋成零，然后随着检查的进行，皇后的位置也在不断地变化，最后找到一个符合要求的方阵时，本质上就是一个存放整数的一维数组，数组的下标是行数，存放的值是列数。 5.困难及解答 我很久以前就听说过八皇后问题，没想到现在轮到自己编了，一开始还真是特别糊涂呢，后来老师上课把算法大概讲了一遍，就清楚很多了，要说问题，就是一开始纠结怎么存放皇后，我开始想用二维数组着，后来老师说用一维数组比较好做，我看了一下老师的算法，就明白了大概，经过一段时间就编出来了 心得 我编程变得还是很少，天天下决心说以后多编，也没践行，心想着吧，不挂在嘴上了，努力！ 程序清单 /* // 我真诚地保证： // 我独立完成了整个程序从分析、设计到编码的所有工作。 // 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中 // 详细地列举我所遇到的问题，以及别人给我的提示。 // 我的程序里中凡是引用到其他程序或文档之处， // 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, // 我都已经在程序的注释里很清楚地注明了引用的出处。 // 我从未没抄袭过别人的程序，也没有盗用别人的程序， // 不管是修改式的抄袭还是原封不动的抄袭。 // 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转 文件名称： 创建者： 创建时间：2011.4.14 最后修改时间：2011.4.17 功能：不同个数皇后的排列问题，各个皇后不再同一行同一列以及同一对角线 文件中的函数名称和简单功能描述：bool unguarded(int A[],int m)，检查A[]-1列和第m-1行的皇后有没有设防 文件中定义的全局变量和简单功能描述：无 文件中用到的他处定义的全局变量及其出处：无 与其他文件的依赖关系：独立 2.关于类的说明： 类名称：无 定义该类的目的： 类属性： 类中函数及功能： 与其他类的关系（调用/被调用哪类对象中的什么函数）： 3. 关于函数的说明 (1) 函数名称：bool unguarded(int A[],int m) 函数功能描述：检查A[]-1列和第m-1的皇后是否设防 函数调用之前的预备条件：一位数组和整数m 返回后的处理：返回一个bool型的变量，若true，则下一个进入方阵的皇后可以放在这，反之，则不能； 返回值（如果有的话）：true or false 函数的输入参数：无 函数的输出参数：无 */ #include "iostream" #define max 100 using namespace std; bool unguarded(int A[],int m) { int n; for(n=0;n<m;n++)//从第零行开始检查 { if((A[n]==A[m])||((A[n]+n)==(A[m]+m))||((A[n]-n)==(A[m]-m))||((n-A[n])==(m-A[m]))) //这种检查方法不包含同一行的情况，因为m不可能等于n return false; } return true; } int main() { int n,i,A[max],s=1; //用一维数组表示皇后的位置的思想来自课堂笔记 cout<<"请输入皇后的个数"<<endl; cin>>n; if((n<=3)||(n>=100)) cout<<"请不要输入1、2、3或者大于100的数！"<<endl;//一个没有意义，两个和三个不管怎么放都会在同一行和同一列 else{ for(i=0;i<n;i++) A[i]=0;//先把每个皇后放在第一列，然后按行检察 i=0;//然后从第零行开始 while(i>=0) //回溯结束的条件 { if(A[i]<=n-1) //当前行数的前