《八皇后问题实验报告递归非递归javaC语言 分析.docx》由会员分享，可在线阅读，更多相关《八皇后问题实验报告递归非递归javaC语言 分析.docx（30页珍藏版）》请在课桌文档上搜索。
1、数据结构课程设计题目：八皇后问题指导老师：皿学生院系：数学学院学生班级：信计*班学生姓名：黎*文学生学号：14070204*2016年12月30日书目一.功能以与需求分折21.1.问题的由来和背景21.2 问题的基本解决思路31.3 问题的应用4二 .总体设计41. 1运行环境42. 2程序框架43. 3算法分析54. 3.1总体算法分析55. 3.2非递归算法分析86. 3.3递归算法的分析8三 .具体设计93.1 递归法的具体设计93.2 非递归法的具体设计11四 .具体实现与运行144. 1QueenMain1.类的实现：145. 2QueenNR类：146. 3QueenRS类：144
2、4C语言程序：15五总结15六.代码清单1561Java代码：1562C语言源代码：27一.功能以与需求分析1.1 问题的由来和背景八皇后问题，是一个占老而闻名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能相互攻击，即随意两个皇后都不能处于同一行、同列或同斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表40种不同的解，后来有人用图论的方法解出92种结果。计算机独创后，有多种计算机语言可以解决此问题。八皇后问题是个以国际象棋为背毋的问题：如何能够在8X8的国际象棋棋盘上放置八个
3、皇后，使得任何一个皇后都无法脆吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同条横行纵行或斜线上。八皇后问题可以推广为更一般的n皇后探放问题：这时棋盘的大小变为nXn,而皇后个数也变成n,当且仅当n=1或n24时问题有解。1.2 问题的基本解决思路八皇后问题最早是由国际西洋棋棋手马克斯贝瑟尔于1848年提出。之后接连有数学家对其进行探讨，其中包括高斯和康托，并且将其推广为更一般的n皇后排放问题。八皇后问题的第一个解是在1850年由弗朗兹诺克给出的。诺克也是首先将问题推广到更般的n皇后摆放问题的人之一。1874年，S.冈彼尔提出了一个通过行列式来求解的方法。八皇后问题出现在1990年头初期
4、的闻名电子嬉戏第七访客中。设置一个三维数组，第一个下标是皇后的行坐标，其次个下标是皇后的列坐标,第三个卜.标是残卷号。相当于有N张叠在起的8*8棋盘，每张棋盘只在豆制前面棋盘与皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。这里实际操作时多加一行多加列即第0行第0列,但这一行/列不作输出，只是作此行/列有无皇后的参考。总的来说现在解八皇后问题的总体算法都是采纳回溯法，也叫作穷搜法，再穷搜的时候去掉分支，削减不必要的运算，对于八皇后问题的求解，一般只能做出15皇后问题，有部分算法高手在有精良设备的状况下算出了25皇后的解“受算法和硬件计算实力的影响，因为计算量为0(n!),
5、而且回溯法运用的内存空间特殊大，所以此问题的求解还有许多可以探究的地方，尤其是算法上的改进。1.3 问题的应用八皇后问题可以用来解决地图的着色问题，以与迷富的求解问题，同时，八皇后问题是一个典型的回溯法求解问题，可以用它来类比许多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。二.总体设计2.1 运行环境(1)编译环境：JDK1.8，以与ec1.ipse，Mars4.5.2,Visua1.C+6.0(2)电脑系统：Windowsserver200332位(3)编译语言：Java,C语言2.2 程序框架(1) MainQueen:实现可视化界面，可以选择递归和非递归两种算法得到八
6、皇后问题的解，并将答案打印出来。(2) QueenNR:采纳非递归方法求解问题。(3) QueenRS:采纳递归方法求解问题，(4)编译C语言程序。2.3 算法分析2.4 3.1总体算法分析算法的核心是回溯法，也称为摸索法，它并不考虑问题规模的大小,而是从问题的最明显的最小规模起先逐步求解出可能的答案，并以此渐渐地扩大问题规模，迭代地靠近最终问题的解。这种迭代类似于穷举并且是摸索性的，因为当目前的可能答案被测试出不行能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步找寻其他求解路径。为了能够撤销当前的求解过程，必需保存上步以来的求解路径。当撤销之后满意条件，就始终做下去，直到摸索完全
7、部的可能解。总结如卜.：(1)设置初始化的方案(给变量赋初值，读入已知数据等)。(2)变换方式去摸索，若全部试完则转(7)。(3)推断此法是否胜利(通过约束函数)，不胜利则转(2)。(4)摸索胜利则前进步再摸索。(5)正确方案还未找到则转(2)。(6)已找到一种方案则记录并打印。(7)退回一步(回溯)，若未退到头则转(2)。(8)已退到头则结束或打印无解另外一个关键就是对于每一个部分解的判定，可归纳问题的条件为:1.不在同一行(列)上2 .不在同一斜线上3 .不在同一反斜线上具体到八皇后的问题，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接者就到下一行
8、或列遍历卜个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有个条件是肯定符合的一一就是下一个棋子的摆放位置与前面的棋子不在同行（或列）。接卜.来，我们只要推断当前位置是否还符合其他条件，假如符合，就遍历下一行（或列）全部位置，看看是否接着有符合条件的位置，以此类推，假如某个行（或列）的全部位置都不合适，就返回上一行（或列）接者该行（或列）的其他位置遍历，当我们顺当遍历到最终 行（或列），且有符合条件的位置时，就是个可行的8皇后摆放方案,累加一次八皇后可行方案的个数，然后接着遍历该行其他位置是否有合适的，假如没有，则返回上一行，遍历该行其他位置，依此卜去。这样个过程下来，我们就可以得出全部符
9、合条件的8皇后投放方案r.这是一个深度优先遍历的过程，同时也是经典的递归思路。接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第 列起先找第颗棋子的合适位置，我们知道，此时第列的任何个位置都是合适的，当棋子找到第一个合适的位置后，就起先到下一列考虑下 个合适的位置，此时，其次列的第行与其次行明显就不能放其次颗棋子了,因为其与第一个棋子一个同在一行，一个同在一条斜线上。其次列第三行成为其次列第个合适的位苴，以此类推，第三列的第5行又会是一个合适位置，这个过程中，我们留意到，每一列的合适位置都是受到前面几列的位置所影响，归纳如卜丁假设前面1列的棋子放在第3行，那当前列不能放的位置就肯定是3
10、行，2行，4行.因为假如放在这三行上就分别跟前列的棋子同在行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用co1.s数组来表示8个列棋子所放的行数，数组F标从0起先，其中数组卜.标表示列数,数组的元素值表示该列棋子所在行数，当前列为N（N=0,N=O,nKN的集合，故又可在上面式子的基础，归纳为如卜.：co1.sN!=co1.smj（与第m列的棋子不在同一行）co1.sN!=co1.s-mJ-（N-In）（0,与第m列的棋子不在同一斜线上）co1.sN!=co1.s-m+（N-m）（=8T,与第m列的棋子不在同一反斜线上）为了使此程序能够解决N皇后的问题，股将参数改成N,已解决N皇后的
11、问题，当然，这还和汁算机性能和算法差异有关，此程序一般能解决到15皇后的问题。在Java程序中以实现N皇后问题。2.3.2非递归算法分析程序首先对N行中的每一行进行探测，找寻该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，假如可以，则在该列放置一个皇后，然后接着探测下一行的皇后位置。假如已经探测完全部的列都没有找到可以放置皇后的列，此时就应当回溯，把上一行皇后的位置往后移一列，假如上一行皇后移动后也找不到位置,则接着回溯直至某一行找到皇后的位置或回溯到第一行，假如第行皇后也无法找到可以放置皇后的位置，则说明已经找到全部的解程序终止。假如该行已经是最终行，则探测完
12、该行后，假如找到放置皇后的位置，则说明我到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是全部N皇后问题全部的解，此时应当消除该行的皇后，从当前放置皇后列数的下一列接着探测。2.3.3递归算法的分析第1次考虑把皇后放在第I行的某个位置，第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以相互攻击的。第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置，这样依次去递归。每计算1行，递归一次，每次递归里面考虑8列,即对每一行皇后有8个可能的位置可以放.找到一个与前面行的皇后都不会相互攻击的位置，然后再递归进入下一行。找到一组可行解即可输出，然后程
13、序回溯去找下一组军界解。用一个一维数组来表示相应行对应的列，比如coki=j表示，第i行的皇后放在第j列。假如当前行是r,皇后放在哪一列呢？COISr列。一共有8列,所以我们要让co1.sr依次取第0列，第1列，第2列始终到第7列，每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。怎样是有冲突呢？同行，同列，对角线。由于已经不会同行了，所以不用考虑这一点。只有满意了当前皇后和前面全部的皇后都不会相互攻击的时候，才能进入卜级递归。三.具体设计3.1递归法的具体设计(1)定义一个COIS数组，存储八皇后问题中每一列(j)对应放置的皇后的位置(i)o(2)定义ge1.Arrange
14、ment(intn)递归函数,其中定义一个boo1.ean型rows口数组，记录每行能够正常放置的位置，假如能放置，设置为Irue,默认为nu1.1.。函数中，先找出每列合适的的第一个位置。然后推断是不是最终列，是最终列就输出，不是就进入递归。假如该列没找到一个合适的位置，跳出此次递归，进入上一次递归。具体函数如卜丁pub1.icvoidge1.Arrange11ent(intn)/遍历该列全部不合法的行，并用rows数组记录，不合法即rowsi=trueboo1.ean11rows=newbooIeanfMAXQUEEN;推断该点是不是合法，假如有合法的，不赋值为nu1.1.for(inti
15、=0:i=0)rowsco1.si-dj=true:if(co1.si+d=MAXQ1.iEEN-I)rowsco1.si+d=Irue;for(inti=O;iMAXQUEEN;i+)推断该行是否合法合法就跳出选出第一个可以添加的行if(rowsi)coniinue:co1.sn=i;设置当前列合法棋子所在行数if(nMAXQ1.EEN-1.)当前列不为最终一列时getArrangement(n+1);e1.senum+;/累计方案个数PrintChessBoard0;/打印棋盘信息3)定义输出函数PUbIiCVoidPrinteheSSBoard0,输出函数比较简洁,利用全部赋值之后dos
16、数组，序号代表列，序列的值代表行。两个for循环即可输出.代表空，0代表皇后。具体函数如卜：pub1.icvoidpriHtChessBoard()System.OUt.print（第+num+”种走法n*）;for(inti=0：i.MAXQ1.EEN;i+)for(intj=O：j0;)i;if(record1i=n)是否同一列f=fa1.se;break;if(1.eft=0)(if(recordi=1.eft)是否同右斜f=fa1.se:break;e1.se1.eft;if(right推断当前点是否为上次退行的位置，是则进行再定位清除原来在回溯行定位的点j=record1.i:rec
17、ord1.i=-1.;f1.agij=-1.;/把回溯点的值改为Tif(jO)i-;往上移e1.se*System.out.printIn(*iojhipo);*/在此结束回溯return;/结束e1.se当前点为一股点if(!isTrue(record,i,j)该定位点位置不满意要求if(j0)i-;往上找定位点e1.se/System.out.printIn(*iojhipow);*/return;结束e1.se该定位点位置满意要求放翼定位点f1.agij=1.;record0i=i;record1i=j;if(i1.en-D(往下走i+；j=0;/endife1.se到末尾，找到-条路径
18、isExist=true;PrintArray(f1.ag);打印record1i=-1:/做回溯处理打算f1.agij=-1.;i-;往上接着搜寻/ende1.se(5)定义输出函数rintArray(intf1.ag),代码略(见代码清单注明：C语言.程序的分析和上述类似，不在赘述。四.具体实现与运行3.2 QueenMain1.类的实现：3.3 QueenNR类：实现fQueenMain类的非递归按钮功能4. 3QueenRS类：实现了QUoCnMain类的递归按钮功能5. 4C语言程序:五.总结1.八皇后问题的求解计算量是特殊大的，对于非递归算法，由于等价于穷搜法，他的时间困难度约等于
19、0(n!),即是n的全排列。虽然采纳了去除分支的方法，但是对于总体来说，并不会削减太多运算，所以对于这种大型的计算。还须要改进算法，并且须要硬件的支持。木试验般只能解决到12皇后，而且计算时间都比较长。2 .对于递归算法，效率比较低，但是便于理解，便利写代码。3 .对于两个算法的比较，都是用的回溯法，只是在具体的回溯方法上的区分。4 .八皇后问题在实际的生活中有许多的得到好用的地方，娴熟地驾驭八皇后问题的求解过程，能解决许多实际中的算法问题。比如迷宫问题和地图着色问题，都可以应用相应的律法。六.代码清单6.1Java代码：QUeenMainI类:packagecom.1.isten;impor
20、tjava.aw1.Border1.ayout;importjava.awt.Card1.ayout;importjava.aw1.Container：importjava.awt.Font;imporIjava.awt.Grid1.ayout:importjava.awt.event.ActionEvent;importjava.awt.event.Action1.istener;importjavax.swing.Box1.ayout;importjavax.swing.JBu1.ton:importjavax.swing.JFrame;importjavax.swing.J1.abe1.
21、;importjavax.swing.JPane1.:importjavax.swing.JScro1.1.Pane:importjavax.swing.JTextArea;importjavax.swing.JTextFie1.d;pub1.icc1.assQueenMainextendsJFrameimp1.ementsAction1.istenerfJPane1.topPane1.=newJPane1.()：JButtonjb1.,jb2,jb3;JTex1.Areajta=nu1.1.;JScro1.1.Panejscro1.1.Pane;J1.abe1.input1.abe1.;JT
22、extFie1.dJnputNum;JPane1.pane1.1,pane1.2;Strings=请在上方输入410的数杳看八皇后路径问题：”；pub1.icQueenMainOSet1.ayout(newBorder1.ayout();/设置按钮pane1.1=newJPane1.()：pane1.2-newJPane1.OJtopPane1.=newJPane1.();input1.abe1.=newJ1.abe1(请输入数字:);inputNum=newJTextFie1.d(25);pane1.I.add(input1.abe1.);pane1.1.add(inputNum);/top
23、Pane1.Set1.ayout(Box1.ayout.Y_AXIS);topPane1.Set1.ayout(newBox1.ayout(topPane1.,Box1.ayou1.Y,AXIS);topPane1.,add(pane1.1):jb1.=newJBU1.Ion(递归”)：jb1.addActIon1.istener(Action1.istener)this);jb2=newJBu1.1.on(非递归”)；jb2.addActIon1.istener(Action1.istener)this);jb3=newJBu1.1.onC清空”)；jb3.addction1.istener
24、(Action1.istener)this);添加按钮pane2.Set1.ayout(newGrid1.ayout(1,3);pane12.add(jb1.)：pane1.2.add(jb2);pane12.add(jb3);topPane1.,add(pane1.2);add(topPane1.,Border1.ayout.NORTH);jta=newJTextAreadO,15);jta.setText(三);jta.SetEditabIe(fa1.se);jta.SetTabSize(4):jta.setFont(newFont(标楷体，Font.BO1.D,16):jta.Se1.1
25、.ineWrap(Irue)：/激活自动换行功能jta.SetWrapSty1.eWord(true);/激活断行不断字功能jscro1.IPane=newJScro1.1.Pane(Jta)：add(jscro1.IPane,Border1.ayout.CENTER);privatevoidQueenRs()(intn=Integer.parse1.nt(inputNm.getTextO);QueenRSTqr=newQueenRST(n,this);privatevoidQueenNrOintn=Integer.parse1.nt(inputNum.getText();QueenRSTqr
26、=newQueenRST(n,this);pub1.icstaticvoidnain(Stringargs)QueenMainapp=newQueenMainO;app.SetTitIe(八皇后问题“);app.setVisib1.e(true):app.SetBounds(300,100,400,600);app.SetDefau1.tcioseOperation(JFrame.EX1.T_0N_C1.OSE);pub1.icvoidacIionPerformed(ActionEvente)if(e.getSource()=jb1.)this.jta.setText(nu1.1.);Quee
27、nRsO;if(e.getSource()=jb2)this.jta.setText(nu1.1.);QueenNrO；if(e.getSource()=jb3)this.inputNum.setText(nu1.1.);this.jta.setText(三):QueenNS类:packagecom.1.isten;importjava,uti1.Scanner;pub1.icc1.assQueenNRpub1.icintcoun1.=0;pub1.icboo1.eanisExist=fa1.se:pub1.icintMAXQUEEN;pub1.icintf1.ag;为解空间的值,即各个N*N
28、方格的值pub1.icintrecord：/2*N,第一行记录每一行对应的列，其次行记录对应的回溯点(每列对应的值)构造函数pub1.icQueenNR(intn)MXQ1.EEN=n;赋初始值f1.ag-newintMAXQUEENMAXQUEEN;定义推断数组record=newint2MAXQUEEN;定义记录数组reset(f1.ag);reset(record);初始化ParseQueen(f1.ag,record);pub1.icvoidreset(intf1.ag)(inti,j,m=f1.ag.1.ength,n=f1.ag0.1.ength;for(i=0：im;i+)for
29、(j=0JnJ+)f1.agij=-1.;定义核心算法pub1.icvoidParSeQUeen(intf1.ag,intrecord)(inti=0,j=0,1.en=f1.ag.1.ength;/System,out.prin1.1.n(*1.ength=*+1.en):whi1.e(true)(if(recordi!=-D/推断当前点是否为上次退行的位置，是则进行再定位清除原来在回溯一行定位的点j=record1.i;record1.i=-1.:f1.agij=-1.;把回溯点的值改为Tif(jO)i-;往上移e1.se*System.out.printin(*iojhipo*);*/在
30、此结束回溯return;结束e1.se当前点为一般点if(!iSTrUe(record,i,j)(该定位点位置不满意要求if(j0)i-;往上找定位点e1.se/System,out.printIn(*iojhipo*);*/return;)结束e1.se该定位点位置满意要求放置定位点f1.agij=1.;record0i=i:record1.i=j:if(i0;)i；if(record1i=n)是否同一列f-fa1.se;break;if(1.eft=O)if(recordi=1.eft)/是否同一右斜1-fa1.se：break;e1.se1.eft;if(right=1.en-1.)(i
31、f(record1i=right)/是否同一左斜f=fa1.se:break;e1.seright+;returnf：输出函数：pub1.icvoidprintArray(intf1.ag)(inti,j,1.en=f1.ag.1.ength,1.en2=f1.ag0.1.ength;count+;System.out.PrintIn(这是第+count+路径：”)；for(i=0:i1.en:i+)(for(j=0;j1.en2;j+)if(f1.agij=-1.)System,out.print(*+”);e1.seSystem,out.print(0);System,out.print1
32、.n();System,out.print1.n();/reset(f1.ag)：*pub1.icvoidprintArray(intrecord)count+;System.out.print(第+count+”种走法n);for(inti=O：iMAXQUEEN：i+)for(intj=O;j=4):);QueenNRapp=newQueenNR(in.next1.ntO);System,out.Prin1.1.n(皇后有+app.COUnI+条路径”);in.c1.ose();QueenRS类:packagecom.1.isten;importjava.uti1.Scanner;pub1
33、.icc1.assQueenRSpub1.icintnum=O;累计方案总数pub1.icintMAXQUEEN;皇后个数,同时也是棋盘行列总数pub1.icintco1.s;定义Co1.S数组,表示8列棋子摆放状况pub1.icQueenRS(intr)MAXQUEEN=n;co1.s=newintMXQ1.EEN：/核心函数geIArrangement(0);System,out.print(n*);System,out.PrinI1.n(MAKQUEEN+”皇后问题有+num种搜放方法。”)；/核心函数代码pub1.icvoidgetArrangement(intn)遍历该列全部不合法的
34、行，并用i-ows数组记录，不合法即rowsi=trueboo1.eanrows=newboo1.eanMAXQUEEN;推断该点是不是合法，假如有合法的，不赋值为nu1.1.for(inti=0：in:i+)/推断行是否合法rowsco1.si=true：intd=n-i推断左右斜线是否合法if(co1.si-=0)rowsco1.si-d=true:if(co1.si+d=MAXQUEEN-Drowsco1.si+d=true：for(inti=O:iMAXQUEEN;i+)(推断该行是否合法合法就跳出选出第一个可以添加的行if(rowsi)continue;设置当前列合法棋子所在行数co
35、1.sn=i;、的前列不为最终一列时if(nMAXQUEEN-1.)getrrangemen1.(n+1.);e1.senum+;/累计方案个数PrintCheSSBoard();打印棋盘信息打印函数pub1.icvoidPrintChessBoardOSystem,out.PrinI(第+num+”种走法n);for(inti=O;iMAXQUEEN;i+)for(intj=0:j=4):);QueenRSqueen=newQueenRS(in.nextIntO)：6. 2C语言源代码：八皇后问题升inc1.ude#inc1.ude/输出0代表皇后voidprintFF(int*positi
36、on)inti=0,j=0;for(i=0;i8;+i)for(j=0;jif(positioni=j)printf(*0);e1.seprintf(*+”);printf(*n*);printfr);/非递归算法voidempress(int*count,ini*position)inti,j,f1.ag;whi1.e(position8!=1)+positionOJ:for(i=0:i8;+i)if(positioni=8)positioni=0:+positioni+1.;f1.ag=1;推断结果是否满意条件for(i=0:i8;+i)for(j=0：j8：+j)if(i!=j)if(p
37、ositioni=positionj)f1.ag=0：e1.seif(abs(positioni-positionj)abs(i-j)f1.ag=0;if(f1.ag=1)Printf(第%d种解法:n*,(*count)+1.);printFF(position);(count)+=f1.ag;voidQueenNSO(intcount=0;intposition9=0;empress(&count,position);PrinIr(%d种解n,count);递归法实现八皇后问题参数row表示起始行，参数n表示列数参数(*chess)8表示指向棋盘每行的指针intnotdanger(introw,intj,int(*chess)8)inti,k;推断列方向for(i=0;i_0&k=0：i,k-)if(*(*(chess+i)+k)=1.)return0;推断右上方for(i=row,k-j;i_0&k8;i,k+)(if(*(*(chess+i)+k)=1.)returnO;/递归函数voideightqueen(int*count,introw,intn,int(*chess)8)i
