八皇后问题课程设计报告

for(queen[++j]=0;queen[j]<8;queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;queen[j]++)if(judge(queen,j))输出正确解法的 输出正确解法的 排列形式输出止确解法的棋盘摆放形式课程设计题目：名称：八皇后问题内容：设计程序完成如下要求：在8X8的国际象棋棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。要求：（1）依次输出各种成功的放置方法。（2）最好能画出棋盘的图形形式，并在其上动态地标注行走的过程。（3）程序能方便地移植到其他规格的棋盘上。一、问题分析和任务定义八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，根据国际象棋的规定，皇后可以攻击与它在同一行、同一列或者同一斜线上的棋子，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。在8!=40320种排列中共有92种解决方案。本程序需要解决的问题有：1、建立合适的数据类型表示皇后在棋盘上所处的位置。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是否相等来验证任意两个皇后是否在同一斜线上。intjudge(int*p,亚/检测皇后是否在同列或者同一斜线上{inti;for(i=0;i<j;i++) //皇后在同一列上的{if(p[j]==p[i])return0;情况if(abs(p[j]-p[i])==j-i)return0;}return1;intcheck(intqueen[],int〃检测棋盘布局是否合法{intj,k;for(j=0;j<=i;j++){for(k=0;k<=i;k++){if(j!=k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k)))皇//后不在同一行且在同一列或者同一斜线时{return0;}}}return1;3、设计输出函数输出八皇后问题的正确解法，首先 show()函数输出排列形编写 式，为了方便，将正确解法的判定条件编写在输出函数中，用多个案，执行之后输出所有正确方法的排列形式和正确解法的个数。然后编写print(函)数输出棋盘形式，按行扫描，用for循环条件语句判定条件之后，皇后输出“Q”，非皇后位置输出+”，在递归函数go(中)调用print(函)数可以完整的输出所有正确解法的棋盘形式。voidshow(intqueen[]){inti=0,j=0,amount=0;

for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按彳丁开始逐行试探每一^列上的皇后位置是否合法for(queen[++j]=0;queen[j]<8;j=l/queen[j]++)for(queen[++j]=0;queen[j]<8;j=2/queen[j]++)for(queen[++j]=0;queen[j]<8;j=3/queen[j]++)for(queen[++j]=0;queen[j]<8;j=4/queen[j]++)for(queen[++j]=0;queen[j]<8;j=5/queen[j]++)for(queen[++j]=0;queen[j]<8;j=6/queen[j]++)if0udge(queenj)ifQudgefqueenJ))if0udge(queenj)ifQudgefqueenJ))ifQudgefqueenJ)){for(i=0;i<8;i++)printf("%d",queen[i]);//输出正确解法的排列形式++amount; //统计所有正确解法的个数printf("\n");}printf("\nthereis%danswer\n",amount);voidprint(intqueen{[]) //输出皇后在棋盘上的摆放形式inti,j;for(i=0;i<8;i++){for(j=0;j<queen[i];j++)皇//后前输出"+"{printf("+");}printf("Q"); //输出Q表示皇后for(j=7;j>queen[i];j--)//皇后后面输出"+"{printf("+");};}printf("pressanykeytoshownextanswer:");getchar();//接收字符getchar();}4、编写程序主函数，在main（中）调用各个功能函数实现八皇后问题的要求，其中运用getchar（函）数接收字符，设置按任意键继续的功能。5、注：本次课程设计主要运用VisualC++6的编译环境，无法使用清屏函数，在turboc的编译环境中，使用clrscr（清）屏函数可以实现动态的输出皇后在棋盘上的摆放形式。详细代码如下：voidprint（int //动态输出棋盘摆放queen[]）{inti,j;形式clrscr（）;for(i=0;i<8;i++){for(j=0;j<queen[i];j+for(i=0;i<8;i++){for(j=0;j<queen[i];j++){printf("+");}printf("Q");for(j=7;j>queen[i];j--){printf("+");};printf("\n");//每行中皇后前面的棋盘//皇后clrscr（）;四、}上机调试本次课程设计中遇到了许多的困难，产生了不少的问题。1、刚开始使用结构体表示皇后的位置，构造了较多的变量，程序设计中产生了许多的错误，判断同斜线情况不太方便，算法性能也不少很好。后来想到运用数组来表示皇后的位置，不但数据结构简单，而且较容易的表示处皇后的位置，容易分析皇后同列、同斜线的情

况(用到abs(函)数)，所以建立整型数组来表示皇后在棋盘上的位置。2、动态输出棋盘摆放形式的时候，自动输出的速度太快，无法观察清楚，后来只好运用getchar(函)数接受一个空的字符手动控制棋盘的输出。五、测试结果及其分析程序运行结果如下各图所示：分析：本次课程设计完成之后，仍觉得有些不足之处，例如无法让电脑自动输出动态的摆放皇后过程，必须手动操作完成。算法的时间复杂度也不是很好。各函数的时间复杂度如下：in时间复杂度为in时间复杂度为O(n)时间复杂度为O(n2)时间复杂度为O(n9)时间复杂度为O(n2)时间复杂度为intjudge(int*p,intj)check(intqueen[],inti)voidshow(intqueen[])voidprint(intqueen[])voidgo(intqueen[],int图2程序运行结果部分截图(1)图3图3程序运行结果部分截图(2)XA图4程序运行结果部分截图(3)

54图5程六、用户使用说明54图5程六、用户使用说明pressanykeytoshownextanswer：执行.exe程序按照提示，按回车输出两种结果。七、参考文献【1】王昆仑李红.数据结构与算法.中国铁道出版社.2007年6月第一版.【2】何钦铭颜晖.语言程序设计.高等教育出版社.200年4月第一版.八、附录#include<stdio.h>#include<stdlib.h>#include<math.h>intcount=0;定//义一个整型变量count来统计正确解法的个数intqueen[8];定//义数组表示皇后所处的位置（queen[3]=2表示皇后在第三行和第二列上）intjudge(int*p,intj)//intjudge(int*p,intj)//检测皇后是否在同列或者同一斜线上{{inti;for(i=0;i<j;i++){if(p[j]==p[i])return0;if(abs(p[j]-p[i])==j-i)return0;//皇后在同一列上的情况return1;}}//皇后在同一斜线上的情况intcheck（intqueen[],in//检测棋盘布局是否合法intj,k;for(j=0;j<=i;j++){for(k=0;k<=i;k++){if(j!=k&&(queen[j]==queen[k]||abs(queen[j]-queen[k])==abs(j-k)))/皇/后不在同一{行且在同一列或者同一斜线时{return0;}}}return1;}voidshow(intqueen[]){inti=0,j=0,amount=0;for(queen[0]=0;queen[0]<8;j=0,queen[j]++)//按行开始逐行试探每一列上的皇后位置是否合法for(queen[++j]=0;queen[j]<8;j=1,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=2,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=3,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=4,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=5,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;j=6,queen[j]++)if(judge(queen,j))for(queen[++j]=0;queen[j]<8;queen[j]++)if(judge(queen,j)){for(i=0;i<8;i++)printf("%d",queen[i]);//输出正确解法的排列形式++amount;/统/计所有正确解法的个数printf("\n");}printf("\nthereis%danswer\n",amount);}voidprint(intqueen[])//输出皇后在棋盘上的摆放形式{inti,j;for(i=0;i<8;i++)for(j=0;j<queen[i];j++)/皇/后前输出"+"{printf("+");}printf("Q");//输出Q表示皇后

for(j=7;j>queen[i];j--)//皇后后面输出"+"{printf("+");};printf("\n");printf("pressanykeytoshownextanswer:");玄心接0收字符}voidgo(intqueen[],int//递归函数if(i>=8) //一个棋盘上摆满8个皇{count++; 〃统计一次方法print(queen); 〃输出一个正确的解法}else{intj;for(j=0;j<8;j++){queen[i]=j;if(check(queen,i))go(que