c++八皇后问题课程设计.docx

c++八皇后问题课程设计.docx

《c++八皇后问题课程设计.docx》由会员分享，可在线阅读，更多相关《c++八皇后问题课程设计.docx（17页珍藏版）》请在冰点文库上搜索。

c++八皇后问题课程设计

C++课程设计

课程设计题目：

八皇后问题

姓名：

xxx

专业：

xxx

班级：

xxxxxx

学号：

xxxxxxxx

指导教师：

xxx

日期：

2014年6月17日

2.3软件的需求...................................................................................................................................7

2.4功能需求.......................................................................................................................................7

1.课题综述

1.1课题的来源及意义

八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。

所以高斯提出了一个问题：

在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。

运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1.2预期目标

运用C++程序设计的编程思想编写代码，实现八皇后问题的所有（92种）摆放情况。

要求在DOS界面上显示出每一种方式。

1.3八皇后问题课题要求

输入后，显示X,Y以及共有多少种布局方案，并显示每一种方案的具体情况

77:

（0,2）（1,0）（2,6）（3,4）（4,7）（5,1）（6,3）（7,5）

78:

（0,7）（1,1）（2,4）（3,2）（4,0）（5,6）（6,3）（7,5）

输出样式实例

1.4面对的问题

需要用三种方法解决八皇后问题，在这里需要查阅大量资料并多加练习，才能成功编写程序。

主要要解决下面的问题：

冲突：

包括列、行、两条对角线；

1.列：

规定每一列放一个皇后，就不会造成列上的冲突；

2.行：

当第i行被某个皇后占据时，该行所有空格就都不能放置其他皇后；

3.对角线：

对角线有两个方向，在同一对角线上的所有点都不能有冲突。

2.需求分析

2.1涉及到的知识

在本次的课程设计中，用到的知识点主要有：

类、函数、选择结构里的条件语句、循环结构里的while语句以及for循环语句、控制语句里的break语句、以及字符串函数的运用等等,并且应用到递归、回溯及穷举等比较经典的算法。

2.1.1类

2.1.1.1类定义

类就是用户自定义的数据类型。

类定义的一般形式如下：

　　class类名

　　{

　　　细节；（数据成员，成员函数）

};

2.1.1.2类函数定义

类成员函数类的成员函数通常在类外定义，一般形式如下:

　返回类型类名:

:

函数名（形参表）

　{

　　　函数体;

　}

双冒号:

:

是域运算符，主要用于类的成员函数的定义。

2.1.2函数

2.1.2.1函数的定义

定义函数需要指明：

函数执行结果返回值的类型、函数名、形式参数（简称形参）和函数体。

一般形式为：

数据类型函数名（行参表）

{

语句序列；

Return合适类型数值

}

2.1.2.2数据类型

规定了函数返回值类型。

执行函数体中的语句后，通常会产生一个结果，这就是函数的返回值，它可以是任何有效的类型。

若函数执行后不返回值，数据类型习惯用void来表示。

如果在函数定义时没有数据类型出现，则默认为函数返回值为整型（int）。

2.1.2.3函数调用

调用一个函数之前必须对该函数进行说明。

函数调用由函数名和函数调用运算符（）组成，（）内有0个或多个逗号分隔的参数（称为实参）。

每一个参数是一个表达式，且参数的个数与参数的类型要与被调函数定义的参数（称为形参）个数和类型匹配。

当被调函数执行时，首先计算实参表达式，并将结果值传送给行参，然后执行函数体，返回的返回值被传送到调用函数。

如果函数调用后有返回值，调用表达是可以用在表达式中，而无参函数的调用是一个单独的语句。

2.1.3选择结构

2.1.3.1用if语句实现选择结构设计

if语句的基本形式可分为两种：

（1）if（表达式）语句

其执行过程是，首先计算表达式的值，若不为0，条件判断为真，则执行（）后面的语句，否则，if语句中止执行，即不执行（）后面的语句。

（2）if（表达式）语句1

else语句2

其执行过程是，首先计算表达式的值，若不为0，条件判断为真，则执行（）后面的语句，否则执行语句2。

2.1.3.2if语句嵌套

if语句中的任何一个子句可以是任意可执行语句，当然也可以是一条if语句，这种情况称为if语句嵌套。

当出现if语句的嵌套时，不管书写格式如何，else格式都将与它前面最靠近的未曾配对的if语句相配对，构成一条完整的if语句。

它的格式为：

if（表达式1）语句1；

elseif（表达式2）语句2；

……

elseif（表达式n）语句n；

else语句n＋1；

2.1.3.3while和do-while语句

while语句用来实现“当型”循环结构，即先判断表达式，然后判断循环条件是否成立。

其一般形式为：

do

{

语句；//循环体

}while（条件表达式）；

其中要注意的是while后面的括号理是表达式而不是语句，表达式是没有分号的；而do-while中最后结束时要有分号。

2.1.4循环结构

2.1.4.1for语句

这种循环语句不仅用于循环次数已知的情况，还能用于循环次数预先不能确定只给出循环结束条件的情况下。

for语句的一般形式：

for（表达式1；表达式2；表达式3）

{

语句；//循环体

}

其执行的过程有以下几个步骤：

求解表达式1；

求解表达式2，若其值为真，则执行for语句中指定的循环体语句，然后执行下面的第3）步。

若为假，则结束循环；

求解表达式3；

转回上面第2）步继续执行；

循环结束，执行for语句后面的其他语句。

2.2总体方案

显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在\斜线上的行列值之和相同；如果同在/斜线上的行列值之差相同；如果斜线不分方向，则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。

下图是一个范例（是棋盘中八皇后位置显示）

将把皇后问题用三种方法表示出来,三种方法用switch语句连接.

●○○○○○○○

○○○○●○○○

○○○○○○○●

○○○○○●○○

○○●○○○○○

○○○○○○●○

○●○○○○○○

○○○●○○○○

棋盘中的八皇后位置显示

2.3软硬件的需求

1）系统要求：

win98以上操作系统；

2）语言平台：

tc++或vc++6.0；

2.4功能需求

当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界面显示。

3.模块及算法设计

3.1算法描述

3.1.2回溯法

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。

按选优条件向前搜索，以达到目标。

但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

可用回溯法求解的问题P，通常要能表达为：

对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）|xi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。

其中Si是分量xi的定义域，且|Si|有限，i=1，2，…，n。

我们称E中满足D

的全部约束条件的任一n元组为问题P的一个解。

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。

树T类似于检索树，它可以这样构造：

设Si中的元素可排成xi

（1），xi

（2），…，xi（mi-1），|Si|=mi，i=1，2，…，n。

从根开始，让T的第I层的每一个结点都有mi个儿子。

这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1

（1），xi+1

（2），…，xi+1（mi），i=0，1，2，…，n-1。

照这种构造方式，E中的一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，xn，反之亦然。

另外，对于任意的0≤i≤n-1，E中n元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。

特别，E中的任意一个n元组的空前缀（），对应于T的根。

因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。

在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，xi），…，直到i=n为止。

在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。

3.2．详细流程图

解决八皇后问题的基本流程图

4.程序代码

#include//数据流输入/输出

#include//参数化输入/输出

#include//定义杂项函数及内存分配函数

#include//定义输入/输出函数

//自定义一个类：

CQueen

classcQueen{

intaQueen[8];//可以在类外访问的私有成员（默认）

intsum;

public:

//只能被该类的成员函数所访问的公有成员

cQueen（）;//构造函数：

确保每个对象正确地初始化

intjudge（intx,inty）;

voidshow（）;

voidstep（）;

};

cQueen:

:

cQueen（）//通过构造函数对aQueen[1---8]初始化

{

sum=0;

for（inti=0;i<8;i++）

aQueen[i]=0;

}

intcQueen:

:

judge（intx,inty）//判断皇后摆放位置是否有冲突，如果没有冲突，则返回1；如果有冲突，则返回0；

{

for（inti=0;i

if（aQueen[i]==y||aQueen[i]+x-i==y||aQueen[i]-x+i==y）

return0;

return1;

}

voidcQueen:

:

step（）//一步一步进行查找摆放

{

intx=0,y=0;//标记皇后所在键盘位置，x代表行，y代表列

while（aQueen[0]<8）

{

while（y<8）

{

if（judge（x,y））//调用类函数judge（x,y）,如果aQueen[1---8]都已经标记，则执行该语句

{

aQueen[x]=y;//摆放皇后

x++;//进行下一行时

y=0;//y进行重置

}

else//否则，进入下一列

y++;

}//当执行到最后一列时，继续执行下一个if语句

if（y==8&&x!

=8）//最后一列，从第一行开始

{

if（aQueen[--x]!

=7）

y=++aQueen[x];

elseif（aQueen[0]!

=7）

y=++aQueen[--x];

else

aQueen[0]=8;

}

if（x==8）//最后一行

{

show（）;//x,y从至结束,大循环结束

if（aQueen[--x]!

=7）

y=++aQueen[x];

else

y=++aQueen[--x];

}

}

}

voidcQueen:

:

show（）//输出棋盘状态

{

cout<<"（非递归法）皇后摆放方式的第"<<++sum<<"种情况：

"<

for（inti=0;i<8;i++）//输出八皇后的各种状态，有皇后的位置用@表示，没有皇后的位置用*表示

{

for（intj=0;j

cout<

（2）<<"*";

cout<

（2）<<"@";

for（j++;j<8;j++）

cout<

（2）<<"*";

cout<

}

cout<

";

for（intk=0;k<8;k++）

cout<<'（'<

cout<

system（"pause"）;//从程序里调用pause命令,一个结果一个结果看

}

voidmain（）

{

cQueena;

a.step（）;

}

5.程序调试分析

1）运行时有些函数的头文件未定义，导致无法进行编译；而且在调试时有些头文件的使用范畴弄混淆了；

2）在统计方法的个数时，未将累加的那个整型变量进行初始化，导致无法显示，八皇后摆放的是“第X种情况”，也无法统计出八皇后的排列方式是否一定是92种情况。

3）未用setw（）函数时，显示的结果相当难看，所定义的标志符都紧靠在一起；多加了一个换行符后，各种情况的间距增大，阅读时舒服多了；

4）如果将92种情形全部打印，则前面的几十种情况将无法显示出，要想看到前面的状态，必须添加一个控制语句，使其能一个一个的输出。

6.运行与测试

（这是把X，Y以及皇后第一种方法运行后显示的界面，其中*是棋盘中棋子的位置，@是棋盘中皇后的位置，坐标表示在当前情况下皇后所处位置）

（这是把X，Y以及皇后第二种方法运行后显示的界面，其中*是棋盘中棋子的位置，@是棋盘中皇后的位置，坐标表示在当前情况下皇后所处位置）

（这是把X，Y以及皇后第三种方法运行后显示的界面，其中*是棋盘中棋子的位置，@是棋盘中皇后的位置，坐标表示在当前情况下皇后所处位置）

（这是把X，Y以及皇后第九十二种方法运行后显示的界面，其中*是棋盘中棋子的位置，@是棋盘中皇后的位置，坐标表示在当前情况下皇后所处位置，此时，按任意键便可以退出八皇后的运行界面）

7.总结

就编写的程序而言，虽然能达到预期的结果，但在运行时所需的时间比较长，而且总体结构还不够简洁，不太容易去理解。

许多问题还需要继续研究，许多技术还需要更多的改进。

去图书馆借了不少书，也去网上看了些资料，只是对大概的知识有了点了解，但还是很难着手于写代码，后来就按照老师说的，先搞清楚原理，再考虑如何去实现！

后来又去上网查看相关资料，又到图书馆借了很多书看，总算有头绪了。

但在调试过程中，还是遇到了很多困难，后来通过了很多同的帮助才把问题解决了。

通过这次的课程设计，让我了解了八皇后这一经典的问题。

同时让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的帮助。

这次课程设计虽然花了我很多时间和精力，但很值得,因为它对我能力提高起到很大帮助。

这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己基础的不扎实.当然这次实验还是有很多问题的。

比如程序设计的界面不够好，一些程序并非自己所写,而是修改某些程序而成,但这些不该,在下次课程设计时不会再发生.

在编写代码时，我希望能随机选择一数X（1～92）后，能输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置，但想了好久，就是无法实现。

而且，当92种情况都输出时，前面的几十种情况无法看到，要想让摆放皇后的图形和所在具体的位置一起输出，就得修改程序让使她们一个一个地输出，这样显然比较麻烦。

针对八皇后这个课题，也许表层只局限于对八个皇后的摆放，但还可以对更多的情况进行探讨分析，比如九皇后，十皇后等等。

在报告正文中已经多次提到关于N皇后的设计方法，但只是一带而过，有些问题很难通过一个报告设计就轻而易举的得到解决，还需要花费更多的时间。

也许随着皇后个数的增多，程序运行的时间将变得很长，我们能否将运行的时间缩短呢？

8.致谢

课程设计终于告一段落了，一周的努力过后，也算是颇有收获，很多以前不清楚、不熟悉的内容都在这一周的努力中得到了锻炼，感谢老师给予的大量帮助及指导，感谢同学们的帮助，才让我顺利完成了这次的课程设计！

通过他们们的帮助，我深刻体会到：

做程序设计需要团队共同努力，共同贡献自己的力量，才能编写出一段好的程序，谢谢你们！

在此，由衷的感谢指导教师王蕾的辛勤指导，让我认识这个课题、熟悉这个课题并且最后完成这个课题；感谢同组同学的互帮互助，提供那么多经典程序供我参考并且指出了许多我的编程过程中出现的问题；感谢我的导师，在我遇到困难难以完成时，他总会给我宝贵的建议，帮助我战胜困难；感谢参考文献的原作者，以及给过我帮助的所有人员！

可以说本次的实验并不是仅仅有我一个人在努力，是通过的大家的帮助，和我个人的劳动共同得出的，我不会忘记你们给我的支持，谢谢你们！

感谢帮助过我的每一个人！

谢谢！

！

参考文献

1郑莉，董渊.C++语言程序设计.第四版.清华大学出版社

2求是科技.C&C++实效编程百例.人民邮电出版社，2004

3蒋爱军，李师贤，梅骁勇.C++Primer习题解答.第四版.人民邮电出版社

4於春景.实用C++调试指南.华中理工大学出版社，2006

5徐惠民.C++大学基础教程.人民邮电出版社，2004

6於春景.实用C++调试指南.华中理工大学出版社，2006