八皇后问题实验报告

实验报告——八皇后问题求解（递归和非递归）学号：专业年级：姓名：一、需求分析（要实现的功能描述）1．问题描述八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n=1或n≥4时问题有解。八皇后问题最早是由国际囯际象棋棋手马克斯·贝瑟尔于1848年提出。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。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）。最后与编程求得的结果进行比较。如果这三组数据在最后编程求得的结果中，说明程序的编写基本没有什么问题。二、概要设计在进行概要设计的过程中，要清楚整个程序包含的功能模块及模块间的调用关系。对于八皇后问题，整个程序中应该包括主函数模块，摆放皇后的函数模块，以及判断皇后的位置是否摆放正确的判断模块。对于模块间的关系，在运行主函数的过程中会调用摆放皇后的函数模块，在摆放皇后的函数模块中，又会调用判断皇后位置是否摆放正确的判断模块。三、详细设计抽象数据类型中定义的各种操作算法实现（用N-S图描述）对于求解八皇后问题的非递归算法，N-S图如下：运行queens函数定义8个皇后，并且开辟9个空间（a[0]不用）初始化为0，初始化k为第一列,即k=1；当k0时候在a[k]的位置上摆放一个皇后，即皇后的位置用数组表示为（a[k],k）当摆放皇后没有到列的最底部，并且摆放不冲突的时候将皇后下移一位皇后位置到达底部？是否回溯到k-1步八列皇后全摆放完毕？是否打印出皇后摆放的情况继续摆放下一列初始化a[k]=0对于八皇后问题求解的递归算法，N-S图如下：调用queen函数，摆放第k个皇后(k从1开始)是否将最后一个皇后摆放完毕？是否打印摆放皇后的情况检测摆放的皇后是否冲突是否重新摆放继续摆放下一个皇后四、调试分析1．程序在调式过程中出现的问题及解决方法由于对于C语言编程问题掌握的并非十分熟练，因而在程序的调试过程中出现了一些问题。例如，在编写位置冲突算法的过程中，在解决对角线问题上，没有考虑对角线有两条，只考虑了其中的一条，因而在编写程序的过程中，没有使用绝对值，导致得到的满足要求的测试结果比实际的要多得多。再如，为了能够输出比较整齐的测试结果，开始的时候只是输出了皇后所在的列数，没有输出皇后的行数。后来，在添加了行数坐标后，两个程序输出了相同的比较整齐美观的测试结果。2．算法的时间复杂度分析在考虑算法的时间复杂度问题上，只需考虑每个函数的最大的时间复杂度即可，求得的最大的时间复杂度即为整个程序的时间复杂度。对于递归程序的时间复杂度：O(𝒏𝟑)对于非递归程序的时间复杂度：O(𝒏𝟐)因而，对于递归和非递归程序两个程序的时间复杂度，递归程序的时间复杂度要高。五、用户手册由于在程序编写的过程中，使用的环境为VisualC++6.0，因而在使用的过程中，最好使用VisualC++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，3）、（5，6）、（6，8）、（7，5）、（8，1）由于空间有限，所以92种测试结果用数组的形式表示如下：七、程序清单非递归问题的程序清单：#includestdio.h#includemath.h//位置冲突算法intChongtu(inta[],intn)//a[]位置数组，n皇后个数{inti=0,j=0;for(i=2;i=n;i++)//i：位置for(j=1;j=i-1;j++)//j：位置if((a[i]==a[j])||(abs(a[i]-a[j])==i-j))//在同一行或在同一对角线上return1;//不冲突return0;//冲突}//八皇后问题：回溯法（非递归）voidQueens8(){intn=8;//定义8个皇后intcount=0;//记录当前第几种情况inta[9]={0};//存放皇后位置，如：a[2]=4;表示第2列第4行有一个皇后（a[0]不用）inti=0,k=1;//初始化k为第一列a[1]=0;//初始化a[1]=0while(k0)//k==0时：表示摆放第1个皇后就超过了列底部（即已经找完所有情况）{a[k]+=1;//a[k]位置，摆放一个皇后while((a[k]=n)&&(Chongtu(a,k)))//如果a[k]（即皇后摆放位置）没有到列最底部，且摆放冲突。a[k]+=1;//将皇后列下移一位if(a[k]=n)//皇后摆放位置没有到达列最底部{if(k==n)//k==n表示，8列皇后全部摆放完毕{printf(第%d种情况：,++count);for(i=1;i=n;i++)//打印情况printf((%d,%d),i,a[i]);printf(\n);}else//皇后还未摆放完毕{k+=1;//继续摆放下一列a[k]=0;//此行初始化a[k]=0;表示第k列，从第一行开始摆放皇后}}else//回溯：当a[k]8进入else,表示在第k列中没有找到合适的摆放位置k-=1;//回溯到k-1步：k表示第几个皇后，a[k]表示第k个皇后摆放的位置}return;}//主函数intmain(){Queens8();return0;}递归问题的程序清单：#includestdio.h#includemath.hinta[9]={0};intn=8,count=0;//位置冲突算法intChongtu(inta[],intn)//a[]位置数组，n皇后个数{inti=0,j=0;for(i=2;i=n;i++)//i：位置for(j=1;j=i-1;j++)//j：位置if((a[i]==a[j])||(abs(a[i]-a[j])==i-j))//在同一行或者同一对角线上return0;//冲突return1;//不冲突}//八皇后问题：回溯算法（递归版）voidQueens8(intk)//参数k：递归摆放第k个皇后{inti=0;if(kn)//kn：即k8表示最后一个皇后摆放完毕{printf(第%d种情况：,++count);for(i=1;i=n;i++)printf((%d,%d),i,a[i]);//打印情况printf(\n);}else//8个皇后未全部摆放完毕{for(i=1;i=n;i++)//摆放第k个皇后时{//依次从列顶端开始搜索，一直到列底端，直到找到合适位置,如果未找到，自动返回上层递归a[k]=i;if(Chongtu(a,k))//不冲突Queens8(k+1);//递归摆放下一个皇后}}return;}//主函数intmain(){Queens8(1);//摆放第1个皇后return0;}