八皇后问题课程设计报告
八皇后问题
设计程序完成如下
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
：在8×8的国际象棋棋盘上，放置8个皇后，使得这8个棋
子不能互相被对方吃掉。要求：(1)依次输出各种成功的放置方法。(2)最好能画出棋盘的图形形式，并在其上动态地标注行走的过程。(3)程序能方便地移植到其他规格的棋盘上。
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名
的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，根
据国际象棋的规定，皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子，即任意两
个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。在8!=40320种排列中共有92种解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。
本程序需要解决的问题有：
1、建立合适的数据类型
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示皇后在棋盘上所处的位置。
2、成功的输出全部正确的放置方法。
3、画出棋盘形式，在上面动态的标注其行走的过程。
1、为了简单易行的表示皇后在棋盘所处的位置，在此建立一个整型数组queen[i]来表
示，若queen[3]=2则表示皇后处在8×8棋盘的第三行和第二列。
2、表示好皇后以后，设计judge( )和check( )函数来检测第一个皇后的同列和同斜线上
有没有其他皇后（程序以行为基础，逐行试探每列和斜线上是否有皇后）。然后设计输出函
数show( )和print( )分别输出正确解法的排列形式和棋盘摆放形式。在输出棋盘的步骤中，
设计一个递归函数go( )实现棋盘的输出。
3、程序的流程图如下图所示：
Main
建立数组表示皇后在棋盘上的位置
在不同行的基础上检测某个皇后的同
列和同斜线上是否存在其他皇后
输出正确解法的排输出正确解法的棋盘
列形式 摆放形式
输出所有正确解法的个
数，程序结束
图1 程序流程图
1、首先定义整型数组queen[i]表示皇后的位置，i的取值由0到7表示八个皇后。然后定义一个整型变量count来统计所有正确解法的个数。
2、因为每行只能摆放一个皇后，所以在皇后不在同一行的基础上，设计检测函数检测
皇后的同列和同斜线上是否存在其他皇后。检测是否同列的时候，定义两个变量i和j表示
两个皇后所在的行数，则用queen[i]和queen[j]表示它们所在的列数，通过验证queen[i]和
queen[j]是否相等确定两个皇后是否处于同一列上。检测同斜线的时候，用到了求绝对值的
函数abs( )函数，用abs(p[j]-p[i])==j-i是否相等来验证任意两个皇后是否在同一斜线上。int
judge(int *p, int j) //检测皇后是否在同列或者同一斜线上
{int i;
for(i=0;i
queen[i];j--)//皇后后面输出"+"
{ printf(" +"); };
}
printf("press anykey to show next answer:");
getchar(); //接收字符 }
4、编写程序主函数，在main( )中调用各个功能函数实现八皇后问题的要求，其中运用
getchar( )函数接收字符，设置按任意键继续的功能。 5、注：本次课程设计主要运用Visual C++6.0的编译环境，无法使用清屏函数，在turboc
的编译环境中，使用clrscr( )清屏函数可以实现动态的输出皇后在棋盘上的摆放形式。详细
代码如下：
void print(int queen[]) //动态输出棋盘摆放形式 { int i,j;
clrscr(); //清屏函数
for(i=0;i<8;i++)
{for(j=0;jqueen[i];j--)
{ printf(" +");}; //每行中皇后后面的棋盘
printf("\n");
}
clrscr();
}
本次课程设计中遇到了许多的困难，产生了不少的问题。 1、刚开始使用结构体表示皇后的位置，构造了较多的变量，程序设计中产生了许多的
错误，判断同斜线情况不太方便，算法性能也不少很好。后来想到运用数组来表示皇后的位
置，不但数据结构简单，而且较容易的表示处皇后的位置，容易
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
皇后同列、同斜线的情
况（用到abs( )函数），所以建立整型数组来表示皇后在棋盘上的位置。
2、动态输出棋盘摆放形式的时候，自动输出的速度太快，无法观察清楚，后来只好运
用getchar( )函数接受一个空的字符手动控制棋盘的输出。
程序运行结果如下各图所示：
分析：本次课程设计完成之后，仍觉得有些不足之处，例如无法让电脑自动输出动态
的摆放皇后过程，必须手动操作完成。算法的时间复杂度也不是很好。
各函数的时间复杂度如下：
int judge(int *p, int j) 时间复杂度为O(n)
int check(int queen[], int i) 时间复杂度为O(n2)
9void show(int queen[]) 时间复杂度为O(n)
2void print(int queen[]) 时间复杂度为O(n)
void go(int queen[], int i) 时间复杂度为O(n)
图2 程序运行结果部分截图(1)
图3 程序运行结果部分截图(2)
图4 程序运行结果部分截图(3)
图5 程序运行结构部分截图(4)
执行.exe程序按照提示，按回车输出两种结果。
【1】王昆仑 李红. 数据结构与算法. 中国铁道出版社. 2007年6月第一版. 【2】何钦铭 颜晖. C语言程序设计. 高等教育出版社. 2008年4月第一版.
#include
#include
#include
int count=0; //定义一个整型变量count来统计正确解法的个数 int queen[8]; //定义数组表示皇后所处的位置（queen[3]=2表示皇后在第三行和第二列上）
int judge(int *p, int j) //检测皇后是否在同列或者同一斜线上 {
int i;
for(i=0;iqueen[i];j--)//皇后后面输出"+"
{
printf(" +");
};
printf("\n");
}
printf("press anykey to show next answer:");
getchar(); //接收字符 }
void go(int queen[], int i) //递归函数 {
if(i>=8) //一个棋盘上摆满8个皇后时
{
count++; //统计一次方法
print(queen); //输出一个正确的解法
}
else
{
int j;
for(j=0;j<8;j++)
{
queen[i]=j;
if(check(queen, i))
{
go(queen,i+1); //函数递归
}
}
}
}
void main() //程序主函数 {
printf("press anykey to show the answer:\n");
getchar();
show(queen);
printf("press anykey to show the chessboard:\n");//输出正确解法的棋盘形式
getchar();
go(queen,0); //从第一个皇后开始递归操作
printf("there is %d answer",count);
printf("\n");
getchar();
}
浙公网安备 33021202002483