八个皇后问题.doc

数据结构课程设计八皇后数据结构课程设计题 目 8个皇后问题 学生姓名 指导教师 学 院 专业班级 完成时间 目 录第一章 课程设计目的3第二章 课程设计内容和要求3第三章 课程设计分析4第四章 算法描述5第五章 源代码12 第六章 运行结果分析19第七章 结束语33第八章 参考文献34第一章 课程设计目的数据结构是一门实践性较强的软件基础课程，本学期我们对数据结构这门课程进行了学习。学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。第二章 课程设计内容和要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力。4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、设计的题目要求达到一定工作量（30页A4纸打印出来）。1、问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2、逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3、详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4、程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。5、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。6、结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。7、编写课程设计报告。第三章 课程设计分析国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗？如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。让我们先从四皇后谈起。若要在如图1所示的44棋盘中，放置四个互不攻击的皇后，可以如下从上到下逐行地考虑：当然在每行中只能放置一个而且必须放置一个皇后，问题是每行中的皇后应放在第几列？图1 图2如果第一行的皇后放置在第一列，第二行的皇后就不能放置在第一、二列，只能放置在第三列或第四列。如果第二行的皇后放置在第三列，那第三行的皇后就没有安身之处了。那么暂且把第二行的皇后放在第四列，看看情况如何。这时，第三行的皇后可以放在第二列（见图2）。然而，第四行的皇后仍然无家可归！要放置好第四个皇后，必须对前几个皇后的位置予以修正。前面已经说过，第三行以至于第二行的所有位置均已考虑过了，只得考虑让第一行的皇后挪一下。如果把第一行的皇后放在第二列，第二行的皇后放在第四列上，第三行的皇后放在第一列上，第四行的皇后放在第三列上，正好四个皇后互不攻击（见图3a）。如果继续这样逐行逐列地考虑下去，还可以找到四皇后问题地另一个解答（见图3b）。图3对于八皇后问题，也可如此解决：从上到下每行放一个皇后；在每一行中均从左至右逐列试放。能放则放（继续考虑下一行）不能放则换（列数加1）换不成则退（退回前一行，让前一皇后所在列数加1后继续考虑），这就是探索八皇后解答的途径。为了记住在探索过程中每行皇后放置的位置就需要用栈。我们可用数组T来作栈；在T(P)中存放第P行皇后所在的列数。例如在第1行的皇后放在第3列，则可置T(1)=3。对于八皇后问题，如此安排后，数组T只需有八个分量就够了。由于我们在每行中只放一个皇后，故而皇后之间保证不会左右相互攻击了；那么如何检查它们是否在上下或斜线方向相互攻击呢？我们用一个数组C来记录每一列上是否放了皇后，不管在哪一行上的第1列上放了一个皇后，就令C(1)=1，.。若把放在第1列上的皇后取走放到别的位置上去了，那么再令C(1)=0,.。这样，只要查看C(I)是否为零，就可以知道第I列上是否可以放置皇后了！显然，八皇后问题中的数组C也只需八个分量就可以了。在88的国际象棋棋盘上，有15条从左上走向右下的斜线，称为主斜线（如图4中左图）；同样有15条从右上走向左下的斜线，称为副斜线。由于每放一个皇后，它所在的两条斜线上就不能再放皇后了。我们可以如同前面所述的那样，再引进两个数组S,M(每个数组有15个分量），分别记录相应的主斜线和副斜线上是否已经放下了皇后。在图4中右图，若在第2行第3列放了一个皇后，则应令S(7)=1,M(4)=1,表示第7条主斜线，第4条副斜线上已有皇后，以后不能再放置了。因为，主对角线数7可由8行数列数8+2-3=7计算得到，副斜线数4可由行数列数12+3-14计算得到。所以一般地说，在第P行，第T(P)列放置皇后以后，应该令：C(T(P)=1；S(8+P-T(P)=1；M(P+T(P)-1)=1。有了以上准备知识，就能为八皇后问题写算法了第四章 算法描述4.1 递归方法解八皇后问题4.1.1 递归的介绍调用子程序的含义：在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是：当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，跳转到子程序A（为了说得简单些，我这里忽略了参数传递这个过程）。当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句（我这又忽略了返回值处理）子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句主程序执行到结束。做个比较：我在吃饭（执行主程序）吃到一半时，某人叫我（执行子程序A），话正说到一半，电话又响了起来（执行子程序B），我只要先接完电话，再和某人把话说完，最后把饭吃完认识递归函数我们在高中时都学过数学归纳法，例：求 n！ 我们可以把n！这么定义 也就是说要求3！，我们必须先求出2！，要求2！，必须先求1！，要求1！，就必须先求0！，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，则如图： 我们可以观察到，除计算0！子程序外，其他的子程序基本相似，我们可以设计这么一个子程序： int factorial(int i) int res; res=factorial(I-1)*i; return res; 那么当执行主程序语句s=factorial(3)时，就会执行factorial(3),但在执行factorial(3)，又会调用factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份！而执行factorial(2)时又会调用factorial（1），执行factorial（1）时又会调用factorial（0），每调用一次factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解；但我们这个函数有点问题，在执行factorial（0）时，它又会调用factorial（1）。造成死循环，也就是说，在factorial函数中，我们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成： int factorial(int i) int res; if (I0) res=factorial(I-1)*i; else res=1;return res; 那么求3!的实际执行过程如图所示： 4.1.2 使用到的函数和变量在这个算法中共有六个函数，除了Main()主函数，还有IsValid(int n)，Output()，Queen(int n)，变量icount，Site这些组成程序，红框圈出的是递归函数的应用，既自己调用自己在Queen(int n)中调用queen是典型的递归调用。编译没有错误4.2 回溯法解决八皇后问题4.2.1 回溯法介绍在计算机奥赛中，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。回溯法的基本思想对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。回溯法中，首先需要明确下面三个概念：（一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。（三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。深度优先搜索（DFS）和广度优先搜索（FIFO）在分支界限法中，一般用的是FIFO或最小耗费搜索；其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列。通过遍历这个队列（队列在遍历过程中不断增长）完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径。而在回溯法中，一般都用DFS。为什么呢？这是因为可以通过约束函数杀死一些节点从而节省时间，由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。FIFO理论上也是可以做到这样的，但是通过对比不难发现，DFS在以这种方法解决问题时思路要清晰非常多。因此，回溯法可以被认为是一个有过剪枝的DFS过程。利用回溯法解题的具体步骤首先，要通过读题完成下面三个步骤：(1) 描述解的形式，定义一个解空间，它包含问题的所有解。(2) 构造状态空间树。(3) 构造约束函数（用于杀死节点）。然后就要通过DFS思想完成回溯，完整过程如下：(1) 设置初始化的方案（给变量赋初值，读入已知数据等）。(2) 变换方式去试探，若全部试完则转(7)。(3) 判断此法是否成功（通过约束函数），不成功则转(2)。(4) 试探成功则前进一步再试探。(5) 正确方案还未找到则转(2)。(6) 已找到一种方案则记录并打印。(7) 退回一步（回溯），若未退到头则转(2)。(8) 已退到头则结束或打印无解。回溯法的数据结构回溯法的状态空间树，在计算机上的数据结构有两种表示方法。当用k表示树的节点层数，n表示节点总数，m表示解的总数时：（一） 用m个k元组表示m种不同的解。其中，每组中的元素是1,n中的一个元素。在Pascal中，可以这样定义变量： var a:array1.k,1.mof integer;（integer可以依n的范围决定）（二） m个n元组表示m种不同的解。因为所有的节点都包含在每个解的表示中，每组中的元素只有两种情况，被选用和不被选用。在Pascal中，可以这样定义变量：var a:array1.n,1.mof boolean;这两种数据结构的解空间最多都含有2n个不同的元组4.2.2 使用到的函数与变量回溯发是很好的算法，在所有算发中空间复杂度是最小的，其只有一个主函数main()，和一个变量total，就可以成功的解决八皇后问题，我本人对于这种算法非常的推崇，也觉的是所有解决了八皇后问题中最好的。编译没有错误4.3 堆栈法解八皇后问题4.3.1 堆栈法介绍堆栈的概念堆栈(Stack)是一种比较重要的线性数据结构，如果对数据结构知识不是很了解的话，我们可以把它简单的看作一维数组。但是对一维数组进行元素的插入、删除操作时，可以在任何位置进行，而对于栈来说，插入、删除操作是固定在一端进行的，这一端称为栈顶(top)，另一端称为栈底(bottom)，向栈中插入数据的操作称为压入(Push)，从栈中删除数据称为弹出(Pop)。二 堆栈的存储方式对栈中元素的操作是按后进先出(Last In First Out,简称LIFO)的原则进行的，即最后压入的元素最先弹出。在栈的操作过程中，有一个永远指向栈顶的栈顶指针，在压入和弹出数据时，栈顶指针向上或向下移动。当栈顶指针为零时(即指向栈底的后面)，栈为空栈。如果压入的数据过多超出了栈的最大空间，则发生栈上溢。在程序设计中，我们可以使用一维数组实现对栈的操作。假设用一维数组s1.arrmax表示栈，则对于非空栈，s1为最早压入栈的元素，同时设栈顶指针top，则stop为最后压入栈的元素。当top=arrmax时栈满，若此时有数据入栈将产生“数组越界”的错误，极为栈上溢，反之当top=0,意为栈空。4.3.2 使用到的函数与变量组成的程序的函数有：DeSetQueen(int row，int col)，DisplayAndSet()，main()，NoConflict(int row,int col)，Pop()，Push(int row，int col)，Queen()，SetQueen(int row，int col)，变量有：ArrayQueen,OutQueen,Top 。没有编译错误第五章 源代码递归算法代码：#include #include #include #include #include #define QUEENS 8int iCount = 0; /!记录解的序号的全局变量。int SiteQUEENS; /!记录皇后在各列上的放置位置的全局数组。void Queen(int n); /!递归求解的函数。void Output();/!输出一个解。int IsValid(int n); /!判断第n个皇后放上去之后，是否有冲突。void main() /*-Main：主函数。-*/system(title递归算法八皇后问题 ); Queen(0); /!从第0列开始递归试探。 getch();/!按任意键返回。void Queen(int n) /*-Queen：递归放置第n个皇后，程序的核心!-*/ int i; if(n = QUEENS) /!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。 Output(); return; for(i = 1 ; i = QUEENS ; i+) /!n还没到8，在第n列的各个行上依次试探。 Siten = i; /!在该列的第i行上放置皇后。 if(IsValid(n) /!如果放置没有冲突，就开始下一列的试探。 Queen(n + 1); int IsValid(int n) /*-IsValid：判断第n个皇后放上去之后，是否合法，即是否无冲突。-*/ int i; for(i = 0 ; i n ; i+) /!将第n个皇后的位置依次于前面n1个皇后的位置比较。 if(Sitei = Siten) /!两个皇后在同一行上，返回0。 return 0; if(abs(Sitei - Siten) = (n - i) /!两个皇后在同一对角线上，返回0。 return 0; return 1; /!没有冲突，返回1。void Output()/*-Output：输出一个解，即一种没有冲突的放置方案。-*/ int i; printf(No.%-5d , +iCount); /!输出序号。 for(i = 0 ; i QUEENS ; i+)/!依次输出各个列上的皇后的位置，即所在的行数。 printf(%d , Sitei); printf(n);回溯算法代码#include # include using namespace std;int total = 0; /方案计数void main() int queen8; int i, j, k; for (i=0;i8;i+) queeni = 0; /八皇后全放在第0列 for (i=1;) /首先安放第0行皇后 if(queeni8) /皇后还可调整 k=0; /检查与第k个皇后是否互相攻击 while(ki&abs(queenk-queeni)&(abs(queenk-queeni)-abs(k-i) k+; if (k=i-1) /与第k个皇后互相攻击 queeni+; /第i个皇后右移一列，重测 continue; i+; /无冲突，安置下一行皇后 if(i8) continue; for(j=0;j8;j+) coutqueenj; /已完成，输出结果 cout ; total+; /方案数加1 if(total%5=0) coutendl; queen7+; / 将第7个皇后右移一列，前7个不动 i=7; /此处是制造机会，如不成功则回溯，关键一步 else /当前行皇后无法安置，回溯 queeni=0; /当前行皇后回归0列 i-; /回溯到前一行皇后 if(i0) /回溯到数组0行之前，结束 cout 总数:totalendl; return; else queeni+; /前一行皇后右移一列 堆栈法的源代码：#include#include/*=定义栈与操作=-*/struct Stack Stack *top;int row;int col;*Top;void Push(int row,int col);void Pop();/*=栈的定义完毕=-*/#define MAXQUEEN 8/*=三个冲突数组确定是否能放置皇后*/0表示无冲突，1表示有冲突static int aMAXQUEEN;/列冲突static int bMAXQUEEN*2-1;/主对角线冲突static int cMAXQUEEN*2-1;/副对角线冲突static int dMAXQUEEN;/*=*/void SetQueen(int row,int col);/放置皇后后在该处设置冲突void DeSetQueen(int row,int col);bool NoConflict(int row,int col);/判断该位置放置皇后/是否与其他皇后冲突/char ArrayQueenMAXQUEENMAXQUEEN;ofstream outQueen;/定义一个输出文件流void DisplayAndSet();/bool Queen();/void main() Top = new Stack; Top-top=NULL; outQueen.open(queen.txt,ios:out,filebuf:openprot); for(int x=0;xMAXQUEEN;x+) for(int y=0;yMAXQUEEN;y+) ArrayQueenxy=*; cout结果在queen.txt文件中endl; coutMAXQUEEN皇后问题是否有解有解？：Queen()endl; outQueen.close();/bool Queen() int count = 0;/计数器 int col = 0;/最初从0列开始 int precolrowMAXQUEEN = 0;/记录每一列上次的行数，全部初始化为0 while( colMAXQUEEN ) int row=precolrowcol;/从该列上一次记录的行数开始循环 while(rowMAXQUEEN) if(NoConflict(row,col)/判断该位置是否发生冲突 Push(row,col);/将皇后位置压入栈 SetQueen(row,col);/设置该方位有冲突 if(col=MAXQUEEN-1)/判断是否找到 count+;/计数器 outQueen第count种情况:endl; DisplayAndSet(); /输出状态，还原空白棋盘 DeSetQueen(row,col); /将第八个皇后冲突数组置0 Pop(); /开始寻找下一个状态 precolrowcol=row+1;col-; /最后一列，row+1行在重新开始寻找 break;/跳出行循环，重新开始列循环 precolrowcol=row;/记录该列的行 break;/跳出，进行下一次列循环 row+;/如果发生冲突，继续行循环 if(row0)/控制结束 return true; if(precolrow0=MAXQUEEN) return false; return true;void SetQueen(int row,int col) acol=1; brow+col=1; crow-col+MAXQUEEN-1=1; drow=1;void DeSetQueen(int row,int col) acol=0; brow+col=0; crow-col+MAXQUEEN-1=0; drow=0;bool NoConflict(int row,int col) if(acol!=1&brow+col!=1&crow-col+MAXQUEEN-1!=1&drow!=1) return true; return false;void DisplayAndSet() Stack *temp=Top-top; for(int x=0;xtop) ArrayQueentemp-rowtemp-col=Q; for( x=0;xMAXQUEEN;x+) for(int y=0;yMAXQUEEN;y+) outQueenArrayQueenxy ; outQueentop; for(x=0;xtop) ArrayQueentemp-rowtemp-col=*;void Push(int row,int col) Stack *s = new Stack; s-row = row; s-col = col; s-top = Top-top; Top-top = s;void Pop() if(Top-top!=NULL) Stack *temp=Top-top; Top-top = temp-top; delete temp; 第六章 运行结果分析6.1 递归具体运行果运行结果表示出有92种可能性6.1.1 算法流程图递归的图解演示6.1.2 结果分析递归是一种很古老的算法，其应用的也十分的广泛，在和多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。递归的优点是：编写简单，缺点是：消耗资源大。八皇后问题是一个经典的数据结构问题用递归是最为常见的方法，由于递归是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。该算法中所有语句的频度之和(即算法的时间耗费)为： T(n)=2n3+3n2+2n+1当n趋向于无穷时，其时间复杂度为O(n3)。6.2 回溯具体运行结果运行结果如图6.2.1 算法流程图回溯算法的图解6.2.2 算法分析回溯是一个很好的算法，其应用的也十分的广泛，在和多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。回溯的优点是：编写复杂，缺点是：消耗资源小。八皇后问题是一个经典的数据结构问题用回溯是最为常见的方法，由于回溯是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。该算法中所有语句的频度之和(即算法的时间耗费)为： T(n)=2n2+1分析：当n趋向于无穷时，其时间复杂度为O(n2+1 +2)。6.3 堆栈具体运行过程运行结果放在queen.txt文件中八皇后问题的源代码运行在queen.txt文件中的92种结果6.3.1 算法流程图6.3.2 算法分析堆栈是一个很好的算法，其应用的也十分的广泛，在和多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。堆栈的优点是：算法比较的平均，运行十分的复杂。八皇后问题是一个经典的数据结构问题用递归是最为常见的方法，由于递归是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。该算法中所有语句的频度之和(即算法的时间耗费)为： T(n)=2nn+1分析：当n趋向于无穷时，其时间复杂度为O(n2 +1)。6.4 八皇后问题所有输出结果为（88棋盘）：第1种情况: 第2种情况: 第3种情况:Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * * * * * Q* * * * * * * Q * * * * * Q * * * * Q * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * Q * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * 第4种情况: 第5种情况: 第6种情况:Q * * * * * * * * * * * * Q * * * * * Q * * * * * * * Q * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * Q * * * * * * * * * * * * * Q* * Q * * * * * * * * * * * * Q * Q * * * * * * * * * * * Q * * * Q * * * * * * * * * * * Q * * Q * * * * * * * * * * * * Q * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * *第7种情况: 第8种情况: 第9种情况:* * * * Q * * * * * Q * * * * * * * * * Q * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * Q * * * * * * * * Q * * * * * * * * Q * * Q * * * * * * * * * * * * * Q * * * * * * * Q* * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * * Q * * * * * Q * * * * * * * Q * * * * Q * * * * * 第10种情况: 第11种情况: 第12种情况:* * * * * * Q * * * * * Q * * * * * * Q * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * * Q * * * * * * * * * Q* * * * * Q * * * * Q * * * * * * * * * * Q * * * * Q * * * * * * * * * * Q * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * Q * * * * * Q * * * * * *第13种情况: 第14种情况: 第15种情况:* Q * * * * * * * * * * Q * * * * * * * * * * Q* * * * * Q * * * * Q * * * * * * * Q * * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * Q * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * Q * * * * * * Q * * * * * * * Q * * * *第16种情况: 第17种情况: 第18种情况:* * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * * * * * * Q * * * Q * * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * * * * * Q* Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * Q * * * * * * * * *