数据结构课程设计-用c++语言解决八皇后问题

《数据结构课程设计-用c++语言解决八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《用C++语言解决八皇后问题》1引言在程序设计中，可以用两种方法解决问题：一是传统的结构化程序设计方法，二是更先进的面向对象程序设计方法。在结构化程序设计中关键是如何将问题域中的行为（即操作）抽取出来，作为C++程序中的函数。由于多个函数均需要访问某些数据，这些数据常被设计为全局变量。而在面向对象程序设计中关键是如何将问题域中的实体（即日常所见的概念）抽取出来，作为C++程序中的类，而属性与行为作为类的两类要素通常是必不可少的，甚至还应考虑类必须满足的约束[1]。1.1课程设计目的深入理解数据结构的基本理

2、论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序[2]。1.2课程设计内容国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最

3、多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗？如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法

4、则才行[3]。19《用C++语言解决八皇后问题》2问题描述和分析2.1问题描述在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。一个合适的解应是在每列、每行确实有一个皇后，且在一条对角线上最多只有一个皇后2.2分析问题分析：(1)满足上述条件的八个皇后，必然是每行一个，每列一个。(2)棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。如果我们把8×8的棋盘看成是一个平面直角坐标系，则八皇后问题就可以用数学语言来描述了，任意两个皇后在平面上的坐标应该

5、同时满足以下三个条件：①两个皇后不在同一行：两个皇后的横坐标不相等；②两个皇后不在同一列：两个皇后的纵坐标不相等；③两个皇后不在同一条斜线上：两个皇后的横坐标之差的绝对值不等于两个皇后的纵坐标之差的绝对值。依据“分而治之”的思想，先讨论4皇后的问题。也就是说在4×4的盘内放4个后。8皇后的问题实际上是4皇后问题的衍生。如图2.1所示。图2.1模拟棋盘图首先清理棋盘，把所有的坐标值都归零，，如图2.2所示。19《用C++语言解决八皇后问题》图2.2棋盘坐标清零然后放第一个Q1到（1，1）的位置，。即Q1.r

6、ow=1，Q1.col=1，如图2.3所示。图2.3放入第一颗棋子Q1会占据它所在的所有横，竖，斜的位置。调用seize（1,1）函数来实现这个功能。让Q1所在的横竖斜线上所在的坐标都置1，如图2.4所示。图2.4继续探索接着放Q2。放Q2的过程可以看作是在4×3的棋格里放Q2-Q4的过程。其中3×3的棋格中间斜线被Q1占据，因此Q2放在（2，3）的位置。即Q2.row=2，Q2.col=3。放完Q2后，调用seize（2，3）函数来实现Q2的占据坐标，如图2.5所示。图2.5划出下一颗棋子可能的区间接下

7、来要放Q3，可以看作是一个在4×2的棋格里放Q3、Q4。但是我们看到第3行已经没有空位放Q3了。因此回退到Q2的时刻，把Q2往后放，寻找第2个适合Q2的位置。若没有位置可放，则退回到Q1改变Q1的位置19《用C++语言解决八皇后问题》，如图2.6所示。图2.6放入第二颗棋子Q2从（2，3）的位置出来后，可以放在（2，4）的位置。即Q2.row=2，Q2.col=4。如此Q3便可放到（3，2）的位置，如图2.7所示。图2.7继续探索但是如此一来，Q3放在（3，2）的位置会占据Q4（4，3）的位置使Q4无法安

8、放。所以应该回退到Q1。使Q1放在（1，2）的位置，如图2.8所示。图2.8无解退回Q1Q2因为（2，1）（2，2）（2，3）都被Q1占据，因此只能放在（2，4）的位置，如图2.9所示。图2.9得出一个解至此，我们已经得到4皇后的一个解，判断是否已解出的条件是Q4是否被安放成功。此时Q4被安置，得出一个解，因此应该输出4个Q的位置调用函数print（）输出此时的4个Q的位置。19《用C++语言解决八皇后问题》输出以后程序还没有