八皇后问题实验报告.pdf

该【八皇后问题实验报告 】是由【小sjj】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【八皇后问题实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验报告
——八皇后问题求解(递归和非递归)
学号:专业年级:姓名:
一、需求分析(要实现的功能描述)

八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置
八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都
不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这
时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当n=1或n≥4时问题有解。八皇
后问题最早是由国际囯际象棋棋手马克斯·贝瑟尔于1848年提出。诺克也是首先将问题推
广到更一般的n皇后摆放问题的人之一。

八皇后问题实现了在棋盘上摆放八个皇后的功能,这八个皇后任意两个皇后都不能处于
同一条横行、纵行或斜线上。

测试数据可以通过手工寻找三组满足需要的值,测试数组(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;
当k>0时候
在a[k]的位置上摆放一个皇后,即皇后的位置用数组表示为(a[k],k)
当摆放皇后没有到列的最底部,并且摆放不冲突的时候
将皇后下移一位
皇后位置到达底部?
是否
八列皇后全摆放完毕?
是否
回溯到k-1步
打印出皇后摆继续摆放一列下
放的情况初始化a[k]=0
对于八皇后问题求解的递归算法,N-S图如下:
调用queen函数,摆放第k个皇后(k从1开始)
是否将最后一个皇后摆放完毕?
是否
检测摆放的皇后是否冲突
打印摆放皇后的情况是否
重新摆放继续摆放下一个皇后
四、调试分析

由于对于C语言编程问题掌握的并非十分熟练,因而在程序的调试过程中出现了一些
问题。例如,在编写位置冲突算法的过程中,在解决对角线问题上,没有考虑对角线有两条,
只考虑了其中的一条,因而在编写程序的过程中,没有使用绝对值,导致得到的满足要求的
测试结果比实际的要多得多。
再如,为了能够输出比较整齐的测试结果,开始的时候只是输出了皇后所在的列数,没
有输出皇后的行数。后来,在添加了行数坐后,标两个程序输出了相同的比较整齐美观的测
试结果。

在考虑算法的时间复杂度问题上,只需考虑每个函数的最大的时间复杂度即可,求得的
最大的时间复杂度即为整个程序的时间复杂度。
对于递归程序的时间复杂度:
O(ᵈᵽ
)
对于非递归程序的时间复杂度:
O(ᵈᵽ
)
因而,对于递归和非递归程序两个程序的时间复杂度,递归程序的时间复杂度要高。
五、用户手册
由于在程序编写的过程中,使用的环境为VisualC++,因而在使用的过程中,最好
使用VisualC++,以免在程序运行错误。
本程序的操作过程十分简单,不需要操作者有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种测试结果用数组的形式表示如下:
七、程序清单
非递归问题的程序清单:
#include<>
#include<>
//位置冲突算法
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]=0
while(k>0)//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;
}
递归问题的程序清单:
#include<>
#include<>
inta[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(k>n)//k>n:即k>8表示最后一个皇后摆放完毕
{
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;
}