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

用C+语言解决八皇后问题 1 引 言在程序设计中，可以用两种方法解决问题：一是传统的结构化程序设计方法，二是更先进的面向对象程序设计方法。在结构化程序设计中关键是如何将问题域中的行为（即操作）抽取出来，作为C+程序中的函数。由于多个函数均需要访问某些数据，这些数据常被设计为全局变量。而在面向对象程序设计中关键是如何将问题域中的实体（即日常所见的概念）抽取出来，作为C+程序中的类，而属性与行为作为类的两类要素通常是必不可少的，甚至还应考虑类必须满足的约束1。1.1课程设计目的深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C+语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序2。1.2课程设计内容国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗？如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行3。 2问题描述和分析2.1问题描述在一个×的棋盘里放置个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。一个合适的解应是在每列、每行确实有一个皇后，且在一条对角线上最多只有一个皇后2.2分析问题分析：(1) 满足上述条件的八个皇后，必然是每行一个，每列一个。(2)棋盘上任意一行、任意一列、任意一条斜线上都不能有两个皇后。如果我们把8×8的棋盘看成是一个平面直角坐标系，则八皇后问题就可以用数学语言来描述了，任意两个皇后在平面上的坐标应该同时满足以下三个条件：两个皇后不在同一行：两个皇后的横坐标不相等；两个皇后不在同一列：两个皇后的纵坐标不相等；两个皇后不在同一条斜线上：两个皇后的横坐标之差的绝对值不等于两个皇后的纵坐标之差的绝对值。依据“分而治之”的思想，先讨论4皇后的问题。也就是说在4×4的盘内放4个后。8皇后的问题实际上是4皇后问题的衍生。如图2.1所示。图2.1 模拟棋盘图首先清理棋盘，把所有的坐标值都归零，如图2.2所示。 图 2.2 棋盘坐标清零然后放第一个Q1到（1，1）的位置，。即Q1.row=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 划出下一颗棋子可能的区间接下来要放Q3，可以看作是一个在4×2的棋格里放Q3、Q4。但是我们看到第3行已经没有空位放Q3了。因此回退到Q2的时刻，把Q2往后放，寻找第2个适合Q2的位置。若没有位置可放，则退回到Q1改变Q1的位置，如图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无法安放。所以应该回退到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的位置。输出以后程序还没有完，因为我们还没有把所有的棋盘都遍历完毕。Q1只是到了（1，2）。要到（1，4）以后程序才算结束。所以我们应该把Q1往后移动一位到（1，3）继续找解。Q1在（1，3）的时候重复上边的过程可以得到Q4的另一组解。我们可以看到，四皇后的两个解是相对的（对称）。实际上皇后问题的任何一个解都有另外一个解和它相对应。因此皇后问题的解一定是一个偶数。最后Q4到了（1，4）以后全部棋盘遍历完毕。输出所有的解。程序结束。我们可以设计一个函数Queen（int i）来模拟4Q的递归调用。另外需要一个seize(i,j)函数判断坐标（i,j）是否被占据。一个print（）函数来打印解。因为整个函数调用是一个递归的过程，递归结束后一切解都被析构了，所以print()函数必须被安置在Queen(int k)函数里。seize（i,j）函数作用是判断坐标（i,j）是否被占据，如占据则返回1，如没占据则返回0。我们往（3，2）中放Q3。在判断是否占据的时候，需要考虑3中情况：1.列上是否被占据了。即图中的（2，2）（1，2）两点，注意，在这里只需要判断i（既3）以上的坐标就行了，因为第3行以下不可能有Q，我们还没有放。因此不用判断（4，2）这个点。（2，2）（1，2）两点的坐标用算法表示可以写成k=i-1 to 1;if(k,j)=Q) retrun 1; return 02.左斜线上是否被占据了。即图中的（2，1）。算法可以写成：k=i-1 to 1if(k,j-i+k)=Q) return1;return 03.右斜线上是否被占据了。即图中的（2，3）（1，4）。算法可以写成：k=i-1 to 1if(k,j+i-k)=Q) return1;return 0后把三种情况进行逻辑或运算以后返回给主函数。换句话说就是行，左斜，右斜只要有一个有Q存在的话，就返回1给主函数，否则返回0。 3数据结构设计3.1数据结构设计考虑我们用Q1-Q4四个整型数组来表示4个Q。Qi的数值表示Q所在的位置。比如Q1=3表示Q1放在（1，3）的位置。4×4的棋盘我们用一个整型变量size来表示。要改变棋盘的大小只需要改变size的数值即可。最主要的是Queen（int i）函数的设计。Queen（int i）函数负责主要的棋盘遍历，从第一个Q放入到遍历结束。另外Queen（int i）函数也是一个递归函数，当Q8没有被放置时，不断的调用自己。直到Q8成功放置，输出解。3.2流程图 图3.1流程图主程序比较简单，只需要调用一个Queen(1)的函数把1传给函数中的变量。Queen函数负责解决解法问题。这是一个递归的过程，当放下第1个Q后，接着自己调用自己放第2个Q。直到4和Q放完。如果放完后则输出组合。然后移动第1个Q的位置继续进行。直到所有的棋盘都被遍历结束4。4算法设计4.1主要设计思想回溯的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进，如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止5。4.2算法的伪码描述主程序较简单，只需要进行一些参数赋值，并执行Queen函数即可。algorithm main ()1input size2Queen(1)3returnend mainQueen函数：程序的核心部分，解皇后问题的全部过程由该函数完成。依据流程图写出算法。Algorithm Queen(val k<integer>)1 i=12 loop (i<=size)1if(seize(k,i)1i=i+12if(i>size)1break2else1Q(k)=i2if(k=size)1print()3Queen(k+1)3end loop4returnend Queenseize函数：函数作用是判断坐标（i,j）是否被占据，如占据则返回1，如没占据则返回0。Algorithm seize(val i <integer>,val j <integer>)1k=i-1;2loop (k>=0)1if (Qk=j|Qk=j+i-k|Qk=j-i+k)1return 12k=k-13end loop4return 0end seizeprint函数：函数作用是打印已经的出的一组解。在调用函数的时候，Q1-Q4里存的分别是四个Q的纵坐标。用两个循环嵌套打印。Algorithm printDigit()1i=02loop(i<size)1print Qi3printcount+4i+5returnendprintDigit 以上是打印数据的一组解。每个数字分别代表相应的Q的纵坐标。这样打印的优点是简单，快捷。但是没有图形输出，不方便用户查看。下边我们定义一个图形打印printGraphic函数algorithm printGraphic()1i=1;j=12loop(i<=size)1printcount+“is:”2loop(j<=size)1if(Qi=j)1print“Q”i2else print“”3end loop3end loop4returnend printGraphic这个函数会直接打印出一组解的图形表达形式。如像图的4Q问题解会如下打印：QQQQ在打印时我们可以交替使用这两个函数。可以先用