文档介绍：八皇后问题
八皇后背景知识
国际象棋中皇后威力很大,它可以象“车”一样沿直线上下或左右移动;也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么,在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢?这个问题是伟大数学家高斯在十九世纪中期提出来的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后,他还认为可能有76种不同的放法,这就是有名的“八皇后”问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗?如果你动手试试,就一定会发现开头几颗皇后很容易放置,越到后来就越困难。由于我们的记忆有限,很可能在某个位置放过子后来证明不行取消了,但是以后又重新放上子去试探,这样就会不断地走弯路,花费大量的精力。因此,必须找到一个简易有效、有条不紊的法则才行。
分析
问题描述:
八皇后问题是想把八个皇后放在一个棋盘上,并且她们之间不会相互攻击。按照国家象棋的规则,皇后可以吃掉任何一个和她处在同一行、同一列、或同一斜线(包括两条对角线)上的其他棋子。如图下所示,皇后所在的行、列及对角线(如图中斜线所示)对其他棋子都是不安全的,而其他地方的棋子则不会受到皇后的威胁。因此,一个皇后放好以后,它所在的列、行、两条对角线上的地方都不能放其他棋子。
危险
Q
危险
安全
上图为皇后放置规则示意图

根据这个规则,我们可以利用一个函数来判断某个位置是否安全,安全的位置说明它所在的同一行、同一列或两条线上都没有放置过皇后,因此不会出现皇后互相攻击的情况;否则该位置不安全。其具体实现过程是找出所有放置的皇后,将他们的位置与该位置进行比较判断。又注意到同一行只能放一个皇后,因此,只需要对前面的各行逐行扫描皇后,就可以找出所有皇后的位置。
下图是其中一种摆放皇后的方法:
Q
Q
Q
Q
Q
Q
Q
Q
基本要求:
编写实现八皇后问题的非递归解法,输出八皇后问题的中所有摆放皇后的方法,使它可以满足条件。
课程设计目的:
深入理解数据结构的基本理论,掌握数据存储结构的设计方法,掌握基于数据结构的各种操作的实现方法,训练对基础知识和基本方法的综合运用能力,增强对算法的理解能力,提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。
课程设计的要求:
能够熟练的运用C++语言、基本数据结构和算法的基础知识,独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程,不断地完善程序以提高程序的性能。
算法分析
简单的回溯算法分析:
根据前面对迷宫的分析,我们发现回溯法对于下述情况非常适合:从一个给定位置上出发有多种选择,但不知道那种选择才能解决问题。回溯法允许我们在尝试某些选择失败后,能系统的尝试完所有可能的选择。对于八皇后的问题,每放上一个皇后,便确定了后面放置的皇后的选择空间(实际上是通过减少后面放置的皇后的安全位置达到的)。越早放置的皇后,她的选择就越多;而越晚放置的皇后,她的选择就越少。这说明八皇后问题和迷宫问题是很相似的,因此,若采用回溯,将能很好很快而且高效率的解决问题。
我们试着先把第一个皇后放在棋盘上,然后再放第二个,使两个皇后不会互相攻击,再放第三个皇后,使得她与前面两个皇后都不会互相攻击,依此类推,直至所有的皇后都放上去。如果第七个皇后放上后,第八个皇后已经没有安全的位置可以放置,则试着调试第七个皇后的位置,再尝试第八个皇后有没有安全的位置;如果第七个皇后的所有安全位置都已尝试过了,第八个皇后还是没有安全的位置,则试着调试第六个皇后的位置,重新放置第七、八个皇后的尝试。如此类推,最糟糕的事情就是一直到将第一个皇后的位置进行调整。由此可见,采用回溯法,过程的实现形式非常简单自然,然而这一过程的工作量非常大。
下面给出八皇后问题回溯算法的伪代码(最后一行就是关于回溯的):
PlaceQueen(row)
for 第row行的各列col
If 位置(row,col)可以放置皇后
在位置(row,col)放置一个皇后
If(row<9)
PlaceQueen(row+1);
else
成功,打印棋盘
将位置(row,col)上的皇后取走,尝试下一列位置
算法设计与分析
这道题可以用递归循环的方法来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题。
(1)冲突(包括行、列、两条对角线)
①列:规定每一列放一个皇后,不会造成列上的冲突。
②行:当第i行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以i为下标的标记置为被占