八皇后问题实验报告

1、实验报告八皇后问题求解（递归和非递归）学号： 专业年级： 姓名：一、需求分析（要实现的功能描述）1问题描述八皇后问题是一个以国际象棋为背景的问题：如何能够在88的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为nn，而皇后个数也变成n。当且仅当n = 1或n 4时问题有解。八皇后问题最早是由国际囯际象棋棋手马克斯贝瑟尔于1848年提出。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。2实现功能八皇后问题实现了在棋盘上摆放八个皇后的功能，这八个

2、皇后任意两个皇后都不能处于同一条横行、纵行或斜线上。3测试数据测试数据可以通过手工寻找三组满足需要的值，测试数组（M，N），其中M代表皇后所在的行，N代表皇后所在的列。例如，第一组测试数据：（1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6）；第二组测试数据（1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）；第三组测试数据：（1，4）、（2，2）、（3，7）、（4，3）、（5，6）、（6，8）、（7，5）、（8，1）。最后与编程求得的结果进行比较。如果这三组数据在最后编程求得的结果中，说明程序的编写基本没有什

3、么问题。二、概要设计在进行概要设计的过程中，要清楚整个程序包含的功能模块及模块间的调用关系。对于八皇后问题，整个程序中应该包括主函数模块，摆放皇后的函数模块，以及判断皇后的位置是否摆放正确的判断模块。对于模块间的关系，在运行主函数的过程中会调用摆放皇后的函数模块，在摆放皇后的函数模块中，又会调用判断皇后位置是否摆放正确的判断模块。三、详细设计抽象数据类型中定义的各种操作算法实现（用N-S图描述）对于求解八皇后问题的非递归算法，N-S图如下：运行queens函数定义8个皇后，并且开辟9个空间（a0不用）初始化为0，初始化k为第一列,即k=1；当k0时候在ak的位置上摆放一个皇后，即皇后的位置用数

4、组表示为（ak,k）当摆放皇后没有到列的最底部，并且摆放不冲突的时候将皇后下移一位皇后位置到达底部？是否回溯到k-1步八列皇后全摆放完毕？是 否打印出皇后摆放的情况继续摆放下一列初始化ak=0对于八皇后问题求解的递归算法，N-S图如下：调用queen函数，摆放第k个皇后(k从1开始)是否将最后一个皇后摆放完毕？是 否打印摆放皇后的情况检测摆放的皇后是否冲突是 否重新摆放继续摆放下一个皇后四、调试分析1程序在调式过程中出现的问题及解决方法由于对于C语言编程问题掌握的并非十分熟练，因而在程序的调试过程中出现了一些问题。例如，在编写位置冲突算法的过程中，在解决对角线问题上，没有考虑对角线有两条，只考

5、虑了其中的一条，因而在编写程序的过程中，没有使用绝对值，导致得到的满足要求的测试结果比实际的要多得多。再如，为了能够输出比较整齐的测试结果，开始的时候只是输出了皇后所在的列数，没有输出皇后的行数。后来，在添加了行数坐标后，两个程序输出了相同的比较整齐美观的测试结果。2算法的时间复杂度分析在考虑算法的时间复杂度问题上，只需考虑每个函数的最大的时间复杂度即可，求得的最大的时间复杂度即为整个程序的时间复杂度。对于递归程序的时间复杂度：O(n3)对于非递归程序的时间复杂度：O(n2)因而，对于递归和非递归程序两个程序的时间复杂度，递归程序的时间复杂度要高。五、用户手册由于在程序编写的过程中，使用的环境

6、为Visual C+ 6.0，因而在使用的过程中，最好使用Visual C+ 6.0，以免在程序运行错误。本程序的操作过程十分简单，不需要操作者有C语言基础。六、测试结果通过对于问题的编程求解，共得到了92种结果。从中任意选择三组数据进行测试。数组的第一个数值为皇后所在的行，第二个值为皇后所在的列。第一组测试数据：（1，4）、（2，7）、（3，3）、（4、8）、（5，2）、（6，5）、（7，1）、（8，6）用图像形象表示为：再如，第二组测试数据：（1，5）、（2，2）、（3，4）、（4，7）、（5，3）、（6，8）、（7，6）、（8，1）第三组测试数据：（1，4）、（2，2）、（3，7）、（4

7、，3）、（5，6）、（6，8）、（7，5）、（8，1）由于空间有限，所以92种测试结果用数组的形式表示如下：七、程序清单非递归问题的程序清单：#include #include /位置冲突算法 int Chongtu(int a, int n)/a位置数组，n皇后个数 int i = 0, j = 0; for (i = 2; i = n; i+)/i：位置 for (j = 1; j 0) /k=0时：表示摆放第1个皇后就超过了列底部（即已经找完所有情况） ak += 1; /ak位置，摆放一个皇后 while (ak = n) & (Chongtu(a,k)/如果ak（即皇后摆放位置）没有

8、到列最底部，且摆放冲突。 ak += 1;/将皇后列下移一位 if (ak = n)/皇后摆放位置没有到达列最底部 if (k = n)/k=n表示，8列皇后全部摆放完毕 printf(第%d种情况：,+count); for (i = 1; i 8进入else,表示在第k列中没有找到合适的摆放位置 k -= 1;/回溯到k-1步：k表示第几个皇后，ak表示第k个皇后摆放的位置 return; /主函数 int main() Queens8(); return 0; 递归问题的程序清单：#include #include int a9 = 0; int n = 8, count = 0; /位置冲突算法 int Chongtu(int a, int n)/a位置数组，n皇后个数 int i = 0, j = 0; for (i = 2; i = n; i+)/i：位置 for (j = 1; j n) /kn：即k8表示最后一个皇后摆放完毕 printf(第%d种情况：,+count); for (i = 1; i = n; i+) printf(%d,%d) ,i,ai);/打印情况 printf(n); else /8个皇后未全部摆放完毕 for (i = 1; i = n; i+)/摆放第k个皇后时 /依次从列顶端开始搜