八皇后问题实验报告递归非递归javaC语言+分析

1数据结构课程设计题目八皇后问题指导教师胡学生院系数学学院学生班级信计班学生姓名黎文学生学号140702042016年12月30日2目录一功能以及需求分析311问题的由来和背景312问题的基本解决思路313问题的应用3二总体设计421运行环境422程序框架423算法分析4231总体算法分析4232非递归算法分析6233递归算法的分析6三详细设计631递归法的详细设计632非递归法的详细设计7四具体实现及运行1041QUEENMAINL类的实现1042QUEENNR类1043QUEENRS类1144C语言程序11五总结12六代码清单1361JAVA代码1362C语言源代码203一功能以及需求分析11问题的由来和背景八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯贝瑟尔于1848年提出在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。八皇后问题是一个以国际象棋为背景的问题如何能够在88的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的N皇后摆放问题这时棋盘的大小变为NN，而皇后个数也变成N。当且仅当N1或N4时问题有解。12问题的基本解决思路八皇后问题最早是由国际西洋棋棋手马克斯贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的N皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹诺克给出的。诺克也是首先将问题推广到更一般的N皇后摆放问题的人之一。1874年，S冈德尔提出了一个通过行列式来求解的方法。八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的88棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。这里实际操作时多加一行多加一列即第0行第0列，但这一行/列不作输出，只是作此行/列有无皇后的参考。总的来说现在解八皇后问题的总体算法都是采用回溯法，也叫作穷搜法，再穷搜的时候去掉分支，减少不必要的运算，对于八皇后问题的求解，一般只能做出15皇后问题，有部分算法高手在有精良设备的情况下算出了25皇后的解。受算法和硬件计算能力的影响，因为计算量为ON，而且回溯法使用的内存空间特别大，所以此问题的求解还有很多可以探究的地方，尤其是算法上的改进。13问题的应用八皇后问题可以用来解决地图的着色问题，以及迷宫的求解问题，同时，八皇后问题是一个典型的回溯法求解问题，可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。4二总体设计21运行环境（1）编译环境JDK18，以及ECLIPSE，MARS452，VISUALC60（2）电脑系统WINDOWSSERVER200332位（3）编译语言JAVA，C语言22程序框架（1）MAINQUEEN实现可视化界面，可以选择递归和非递归两种算法得到八皇后问题的解，并将答案打印出来。（2）QUEENNR采用非递归方法求解问题。（3）QUEENRS采用递归方法求解问题。（4）编译C语言程序。23算法分析231总体算法分析算法的核心是回溯法，也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径。当撤销之后满足条件，就一直做下去，直到试探完所有的可能解。总结如下1设置初始化的方案（给变量赋初值，读入已知数据等）。2变换方式去试探，若全部试完则转7。3判断此法是否成功（通过约束函数），不成功则转2。4试探成功则前进一步再试探。5正确方案还未找到则转2。6已找到一种方案则记录并打印。7退回一步（回溯），若未退到头则转2。8已退到头则结束或打印无解另外一个关键就是对于每一个部分解的判定，可归纳问题的条件为1不在同一行（列）上2不在同一斜线上3不在同一反斜线上5具体到八皇后的问题，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的就是下一个棋子的摆放位置与前面的棋子不在同一行（或列）。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历，当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第一列开始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的，当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，一个同在一条斜线上。第二列第三行成为第二列第一个合适的位置，以此类推，第三列的第5行又会是一个合适位置，这个过程中，我们注意到，每一列的合适位置都是受到前面几列的位置所影响，归纳如下假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是3行，2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用COLS数组来表示8个列棋子所放的行数，数组下标从0开始，其中数组下标表示列数，数组的元素值表示该列棋子所在行数，当前列为N（N0,N0,M0,与第M列的棋子不在同一斜线上COLSNCOLSMNM0ROWSCOLSIDTRUEIFCOLSID0IIFRECORD1IN/是否同一列FFALSEBREAKIFLEFT0IFRECORD1ILEFT/是否同一右斜FFALSEBREAKELSELEFTIFRIGHT0I/往上移ELSE/SYSTEMOUTPRINTLN“IOJHIPO“/在此结束回溯RETURN/结束ELSE/当前点为普通点IFISTRUERECORD,I,J/该定位点位置不满足要求IFJ0I/往上找定位点ELSE/SYSTEMOUTPRINTLN“IOJHIPO“/RETURN/结束ELSE/该定位点位置满足要求/放置定位点FLAGIJ1RECORD0IIRECORD1IJIFI0I/往上移ELSE/SYSTEMOUTPRINTLN“IOJHIPO“/在此结束回溯RETURN/结束ELSE/当前点为普通点IFISTRUERECORD,I,J/该定位点位置不满足要求IFJ0I/往上找定位点ELSE/SYSTEMOUTPRINTLN“IOJHIPO“/RETURN/结束ELSE/该定位点位置满足要求/放置定位点FLAGIJ1RECORD0IIRECORD1IJIFI0IIFRECORD1IN/是否同一列FFALSEBREAKIFLEFT0IFRECORD1ILEFT/是否同一右斜FFALSEBREAKELSELEFTIFRIGHT4“QUEENNRAPPNEWQUEENNRINNEXTINTSYSTEMOUTPRINTLN“皇后有“APPCOUNT“条路径“INCLOSEQUEENRS类PACKAGECOMLISTENIMPORTJAVAUTILSCANNERPUBLICCLASSQUEENRSPUBLICINTNUM0/累计方案总数PUBLICINTMAXQUEEN/皇后个数，同时也是棋盘行列总数PUBLICINTCOLS/定义COLS数组，表示8列棋子摆放情况PUBLICQUEENRSINTNMAXQUEENNCOLSNEWINTMAXQUEEN/核心函数GETARRANGEMENT0SYSTEMOUTPRINT“N“SYSTEMOUTPRINTLNMAXQUEEN“皇后问题有“NUM“种摆放方法。“/核心函数代码PUBLICVOIDGETARRANGEMENTINTN/遍历该列所有不合法的行，并用ROWS数组记录，不合法即ROWSITRUE19BOOLEANROWSNEWBOOLEANMAXQUEEN/判断该点是不是合法，如果有合法的，不赋值为NULLFORINTI0I0ROWSCOLSIDTRUEIFCOLSID4“QUEENRSQUEENNEWQUEENRSINNEXTINT2062C语言源代码/八皇后问题INCLUDEINCLUDE/输出0代表皇后VOIDPRINTFFINTPOSITIONINTI0,J0FORI0I0I,KIFCHESSIK1RETURN0/判断右上方FORIROW,KJI0I,K22IFCHESSIK1RETURN0/递归函数VOIDEIGHTQUEENINTCOUNT,INTROW,INTN,INTCHESS8INTCHESS288,I,JFORI0I8IFORJ0J8JCHESS2IJCHESSIJIFROW8PRINTF“第D种N“,COUNTFORI0I8IFORJ0J8JPRINTF“D“,CHESS2IJPRINTF“N“ELSE/判断这个位置是否有危险/如果有危险，那继续往下FORJ0JNJIFNOTDANGERROW,J,CHESS/判断是否危险FORI0I8ICHESS2ROWI0CHESS2ROWJ1EIGHTQUEENCOUNT,ROW1,N,CHESS2VOIDQUEENRSINTCHESS88/为递归方法初始化条件INTI,JINTCOUNT0/初始化棋盘为0FORI0I8IFORJ0J8JCHESSIJ023EIGHTQUEEN/从第0行开始依次以行为单位遍历