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

用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在打印时我们可以交替使用这两个函数。可以先用printDigit把所有的解都打出来，然后用printGraphic打印特定的用户选择的解。4.3运行环境本程序在Windows XP系统VC+6.0环境下调试、运行4.4运行结果程序运行开始，进入提示界面，按任意键进入数据计算功能如图411图4.1按任意键进行 操作输出问题的各种解，如图4.2，图4.2 输出92种解5结束语 这次课程设计，主要是解决了八皇后问题，得出该问题的92种可能。该课题是一个十分有趣项目。通过这次设计我从中了解到无论是在上个世纪还是现在，软件开发所涉及的工作基本都没有变化，它们都起始于一个实际需要或某个灵感，然后就是分析，设计，编码，调试，维护。这些任务以某种方式动态地结合起来就构成了软件开发的整个过程，这就是所谓的“软件开发周期”。但对于这些工作，具体怎样做，什么时候做，每个人都有自己的一套方式，甚至有的人有几套方式。数据结构是计算机专业很重要的一门课程，也是必须要熟练掌握的课程，这次的课程设计对我的数据结构知识进行了一次全面的综合训练，加深了对数据结构基本概念和基本知识的理解，巩固了课堂上学的知识，掌握了数据结构的一些基本方法，深刻理解了算法，锻炼了自己分析问题解决问题的能力。在本课程设计完成之际，最先要感谢的就是我的导师曾爱群老师。曾老师有着丰富的经验、对知识的追求孜孜不倦、精益求精的治学态度、给我留下了深刻的印象。我很庆幸我在此次课程设计中选择曾老师做我的导师，能与曾老师这样的学识渊博，有实践经验的老师做课题，对我今后的学习工作将有很大益处。我深深的感受到自己在课程设计期间，在曾老师的指导下受益匪浅。 在本次课程设计过程中，曾老师为我提出了很多建议和意见，在这个学期中，我们随时都能与他取得联系询问相关问题，我的这次设计顺利完成离不开曾老师的帮助，曾老师为我的论文的顺利完成提供了极大的支持。在做课题的这段时间里，我不仅跟曾老师学会了怎样做学问，更从曾老师身上学到了许多做人的道理。曾老师严于律己、宽以待人的崇高品质更将是我一生的榜样。无论在学习上，还是在生活中，我从曾老师身上学到了很多东西，这些将成为我一笔宝贵的财富。在此，我衷心的感谢曾老师为我所做的一切，感谢曾老师对我的关心、指导和教诲。参考文献1 Richard F. Gilberg, Behrouz A. Forouzan. Data Structure. Brooks/Cole, Thomson Asia Pte Ltd, USA, 2000.2 严蔚敏, 吴伟民. 数据结构（第二版）. 北京：清华大学出版社, 1992.3 朱晓冬, 段延娥. 数据结构Web动画算法. 软件评论, 2008，1：1-54http:/10.98.61.198/computer_web/syllabus/data_structure/course%20home,%20summer%202003.htm5王红梅，胡明，王涛 数据结构C+版 北京清华大学出版社，2005.7附录1 源程序清单#include "stdio.h"int a8,b24,c24,d24;int i, k,g1=0,g2=0;void print1() g1+;printf("t第%2d种情况: ",g1); for (k=1;k<9;k+) printf("%4d",ak);/ getch(); printf("n");void print2() int t,n;g2+; printf("t第%2d种情况: nt",g2); for (k=1;k<9;k+) n=ak; for(t=1;t<n;t+) printf("0 "); printf("1 "); t+; for(t;t<9;t+) printf("0 "); printf("nt");printf("n");getch();void try1(int i) int j; for (j=1;j<9;j+) /*每个皇后都有8种可能位置*/ if (bj=0) &&(ci+j=0)&& (di-j=0)/*判断位置是否冲突*/ ai=j; /*摆放皇后*/ bj=1; /*宣布占领第J行*/ ci+j=1; /*占领两个对角线*/ di-j=1; if (i<8) try1(i+1); /*8个皇后没有摆完，递归摆放下一皇后*/ else print1(); /*完成任务，打印结果*/ bj=0; /*回溯*/ ci+j=0; di-j=0; void try2(int i) int j; for (j=1;j<9;j+) /*每个皇后都有8种可能位置*/ if (bj=0) &&(ci+j=0)&& (di-j=0)/*判断位置是否冲突*/ ai=j; /*摆放皇后*/ bj=1; /*宣布占领第J行*/ ci+j=1; /*占领两个对角线*/ di-j=1; if (i<8) try2(i+1); /*8个皇后没有摆完，递归摆放下一皇后*/ else print2(); /*完成任务，打印结果*/ bj=0; /*回溯*/ ci+j=0; di-j=0; void main()int choice;char ch; printf("nntt 欢迎使用8皇后迷题情况查询 nn"); for( k=0;k<24;k+) /*数据初始化*/ bk=0; ck=0; dk=0; ch='y'while(ch='y'|ch='Y') printf("ntt 八 皇 后 查 询 菜 单n"); printf("ntt*"); printf("ntt* 1-位置标明法 *"); printf("ntt* 2-视图显示法 *"); printf("ntt* 0-退 出 *"); printf("ntt*"); printf("nntt请选择菜单号(0-2)："); scanf("%d",&choice); switch(choice) case 1: printf("nt每一列皇后的放置的行数的情况nn"); try1(1); /*从第1个皇后开始放置*/ break; case 2: printf("nt使用回车查看下一种情况（共92种）nn"); try2(1); /*从第1个皇后开始放置*/ break; case 0: ch='n'break; default:printf("ntt菜单选择错误！请重输n"); 19