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

1、数据结构课程设计题目：八皇后问题指导教师：胡学生院系：数学学院学生班级：信计*班学生姓名：黎*文学生学号：14070204*2016年12月30日目录一. 功能以及需求分析 31.1问题的由来和背景 31.2问题的基本解决思路 31.3 问题的应用 3二. 总体设计 42.1运行环境 42.2程序框架 42.3 算法分析 42.3.1 总体算法分析 42.3.2 非递归算法分析 6递归算法的分析 6三. 详细设计 63.1递归法的详细设计 63.2非递归法的详细设计 8四. 具体实现及运行 104.1 QueenMainl 类的实现： 104.2 QueenNR类： 104.3 QueenRS

2、类： 114.4 C语言程序： 11五. 总结 12六. 代码清单 136.1 Java 代码： 136.2 C语言源代码： 20一.功能以及需求分析1.1问题的由来和背景八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题 是国际西洋棋棋手马克斯贝瑟尔于1848年提出：在8X8格的国际象棋上摆放 八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或 同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了 40种不同的解，后来有人用图论的方法解出92种 结果。计算机发明后，有多种计算机语言可以解决此问题。八皇后问题是一个以国际

3、象棋为背景的问题： 如何能够在8 X 8的国际象 棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了 达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题 可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为 nxn,而皇后个 数也变成n。当且仅当n = 1 或n4时问题有解。1.2问题的基本解决思路八皇后问题最早是由国际西洋棋棋手马克斯 贝瑟尔于1848年提出。之后 陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的 n皇后摆放问题。八皇后问题的第一个解是在 1850年由弗朗兹诺克给出的。 诺克也是首先将问题推广到更一般的 n皇后摆放问题的

4、人之一。1874年，S. 冈德尔提出了一个通过行列式来求解的方法。八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三 维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标 是残卷号。相当于有N张叠在一起的8*8棋盘，每张棋盘只在复制前面棋盘及皇 后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。这 里实际操作时多加一行多加一列即第 0行第0列，但这一行/列不作输出，只是 作此行/列有无皇后的参考。总的来说现在解八皇后问题的总体算法都是采用回溯法，也叫作穷搜法，再穷搜的时候去掉分支，减少不必要的运算，对于八皇后问题的求解，一般只 能做出15皇

5、后问题，有部分算法高手在有精良设备的情况下算出了 25皇后的 解。受算法和硬件计算能力的影响，因为计算量为0(n!)，而且回溯法使用的内存空间特别大，所以此问题的求解还有很多可以探究的地方，尤其是算法上的改进。1.3问题的应用八皇后问题可以用来解决地图的着色问题，以及迷宫的求解问题，同时， 八皇后问题是一个典型的回溯法求解问题，可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。二.总体设计2.1运行环境（1）编译环境（2）电脑系统（3）编译语言JDK 1.8，以及 eclipse ，Mars 4.5.2 ，Visual C+ 6.0Win dows server

6、 2003 32 位Java， C语言2.2程序框架（1）MainQueen实现可视化界面，可以选择递归和非递归两种算法得到八皇 后问题的解，并将答案打印出来。（2）QueenNR采用非递归方法求解问题。（3）QueenRS采用递归方法求解问题。（4）编译C语言程序。2.3算法分析总体算法分析算法的核心是回溯法，也称为试探法，它并不考虑问题规模的大小，而是 从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因 为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解

7、路径。为了能够撤销当前的求解过程， 必须保存上一步以来的求解路径。当撤销之后满足条件，就一直做下去，直到 试探完所有的可能解。总结如下：（1）设置初始化的方案（给变量赋初值，读入已知数据等）。（2）变换方式去试探，若全部试完则转（7）。（3）判断此法是否成功（通过约束函数），不成功则转（2）。（4）试探成功则前进一步再试探。（5）正确方案还未找到则转（2）。（6）已找到一种方案则记录并打印。（7）退回一步（回溯），若未退到头则转 。（8）已退到头则结束或打印无解另外一个关键就是对于每一个部分解的判定，可归纳问题的条件为：1. 不在同一行（列）上2. 不在同一斜线上3. 不在同一反斜线上具体到八

8、皇后的问题，我们可以逐行或者逐列来进行可行摆放方案的遍历， 每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋 子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的 就是下一个棋子的摆放位置与前面的棋子不在同一行（或列）。接下来，我 们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所 有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的 所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历， 当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的 8皇后摆放方案，累加一次八皇后可行方案的

9、个数，然后继续遍历该行其他位置 是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样 一个过程下来，我们就可以得出所有符合条件的 8皇后摆放方案了。这是一个深 度优先遍历的过程，同时也是经典的递归思路。接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第一列开 始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的， 当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时, 第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，一个同在一条斜线上。第二列第三行成为第二列第一个合适的位置， 以此类推，第三列的第5行

10、又会是一个合适位置，这个过程中，我们注意到，每 一列的合适位置都是受到前面几列的位置所影响，归纳如下：假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是 3行, 2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、 同在斜线、 同在反斜线上，不符合我们的要求。现在我们用 cols数组来表示8个列棋子所 放的行数，数组下标从0开始，其中数组下标表示列数，数组的元素值表示该列 棋子所在行数，当前列为 N（N=0,N=0,m=0 ,与第m列的棋子不colsN != cols在同一斜线上）colsN != cols- - m + （N-m） （=8-1, 与第 m列的棋子不在同一反斜

11、线上）为了使此程序能够解决N皇后的问题，一般将参数改成 N,已解决N皇后的问 题，当然，这还和计算机性能和算法差异有关，此程序一般能解决到15皇后的问题。在Java程序中以实现N皇后问题。232非递归算法分析程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具 体方法是对该行的每一列进行探测， 看是否可以放置皇后，如果可以，则在该列 放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没 有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列， 如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或 回溯到第一行，如果第一行皇后也无法

12、找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放 置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程 序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从 当前放置皇后列数的下一列继续探测。233递归算法的分析第1次考虑把皇后放在第1行的某个位置，第2次放的时候就不用去放在第 一行了，因为这样放皇后间是可以互相攻击的。第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递 归。每计算1行，递归一次，每次递归里面考虑 8列，即对每一行皇后有8个 可能的位置可以

13、放。找到一个与前面行的皇后都不会互相攻击的位置，然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。用一个一维数组来表示相应行对应的列，比如colsi=j 表示，第i行的皇后放在第j列。如果当前行是r，皇后放在哪一列呢？ colsr列。一共有8 列, 所以我们要让colsr依次取第0列，第1列，第2列 一直到第7列，每 取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。怎样是有冲突呢？同行，同列，对角线。由于已经不会同行了，所以不用考虑这一 点。只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入 下一级递归。.详细设计3.1递归法的详细设计

14、(1) 定义一个cols数组，存储八皇后问题中每一列(j)对应放置的皇 后的位置(i )。(2) 定义getArrangement(int n)递归函数，其中定义一个boolean型rows数组，记录每一行能够正常放置的位置，如果能放置，设置为true，默认为null。函数中，先找出每列合适的的第一个位置。然后判断是不是最 后一列，是最后一列就输出，不是就进入递归。如果该列没找到一个合适的位置，跳出此次递归，进入上一次递归。具体函数如下：public void getArra ngeme nt(i nt n)/遍历该列所有不合法的行，并用rows数组记录，不合法即rowsi=trueboole

15、a n rows = new boolea nMAXQUEEN;/ 判断该点是不是合法，如果有合法的，不赋值为nullfor(int i=0;i= 0) rowscolsi-d=true;if(colsi+d = MAXQUEEN-1) rowscolsi+d=true;for(int i=0;iMAXQUEEN;i+)/判断该行是否合法合法就跳出选出第一个可以添加的行if(rowsi)co nti nue;cols n = i; /设置当前列合法棋子所在行数if(*M AXQUEEN-1) /当前列不为最后一列时getArra ngeme nt( n+1);elsenum+; /累计方案个数

16、prin tChessBoard();打印棋盘信息(3) 定义输出函数 public void prin tChessBoard() ，输出函数比较简单，利用全部赋值之后clos数组，序号代表列，序列的值代表行。两个for循环即可输出。 + 代表空， 0代表皇后。具体函数如下：public void prin tChessBoard()System.out.pri nt(第+nu m+ 种走法 n);for(int i=0;iMAXQUEEN;i+)for(i nt j=0;j0;) i-;if(record1i=n)是否同一列f=false; break;if(left=0)if(recor

17、d1i=left)/是否同一右斜f=false; break;else left-;if(right=le n-1)if(record1i=right)/是否同一左斜f=false; break;else right+;(4) 定义 parseQuee n( in t flag,i nt record)核心回溯函数。public void parseQuee n( in t flag,i nt叩 record) int i=O,j=O,le n=flagen gth;/System.out.pri ntl n(le ngth=+le n);while(true)if(record1i!=-1)

18、/判断当前点是否为上次退行的位置，是则进行再定位/清除原来在回溯一行定位的点j=record1i;record1i=-1;flagij=-1; /把回溯点的值改为-1if(j0) i-;/往上移else /*System.out.pri ntl n( iojhipo);*/ /在此结束回溯return ;/结束else/当前点为普通点if(!isTrue(record,i,j)if(j0) i-;/ else往上找定位点/*System.out.pri ntln( iojhipo);*/return ;/结束else/该定位点位置满足要求 放置疋位点flagij=1;record0i=i;re

19、cord1i=j;if(iJJ4tU34.2 Quee nNR 类：实现了 QueenMain类的非递归按钮功能0 + * + + + + 第91种走淮+ +O + + + + + + + +0 + + + 牛 0 + 备* +母 + + + + + + +O + + + + O+ + + + + O+ + +4.3 Quee nRS 类：实现了 QueenMain类的递归按钮功能4.4 C语言程序:五. 总结1八皇后问题的求解计算量是特别大的，对于非递归算法，由于等价于穷 搜法，他的时间复杂度约等于 0(n!)，即是n的全排列。虽然采用了去除分 支的办法，但是对于总体来说，并不会减少太多运算

20、，所以对于这种大型的计 算。还需要改进算法，并且需要硬件的支持。本实验一般只能解决到12皇后,而且计算时间都比较长。2. 对于递归算法，效率比较低，但是便于理解，方便写代码。3. 对于两个算法的比较，都是用的回溯法，只是在具体的回溯方法上的区 别。4. 八皇后问题在实际的生活中有很多的得到实用的地方， 熟练地掌握八皇 后问题的求解过程，能解决很多实际中的算法问题。比如迷宫问题和地图着色 问题，都可以应用相应的算法。六. 代码清单6.1 Java 代码:Quee nMai nl 类：package com.Liste n;import java.awt.BorderLayout;import j

21、ava.awt.CardLayout;import java.awt.C ontainer;import java.awt.F ont;import java.awt.GridLayout;import java.awt.eve nt.Acti on Eve nt;import java.awt.eve nt.Actio nListe ner;import javax.swi ng.BoxLayout;import javax.swi ng.J Butt on;import javax.sw in g.JFrame;import javax.sw in g.JLabel;import java

22、x.swi ng.JPan el;import javax.swi ng.J ScrollPa ne;import javax.sw in g.JTextArea;import javax.sw in g.JTextField;public class Quee nMain exte nds JFrame impleme nts Actio nListe nerJPa nel topPa nel = new JPa nel();JButton jb1, jb2, jb3;JTextArea jta = n ull;JScrollPa ne jscrollPa ne;JLabel in putL

23、abel;JTextField in putNum;JPa nel pan el1,pa nel2;String s =请在上方输入4-10的数查看八皇后路径问题：;public Quee nMain() setLayout (new BorderLayout();new/设置按钮panel1 = new JPanel();panel2= new JPanel();topPanelJPa nel();in putLabel = new JLabel(请输入数字：);in putNum = new JTextField(25);pan el1.add(i nputLabel);pa nel1.a

24、dd(i nputNum);/topPa nel.setLayout( BoxLayout.Y_AXIS);topPa nel.setLayout (new BoxLayout(topPa nel, BoxLayout.Y_AXIS); topPa nel.add(pa nel1);jb1 = new JButto n(” 递归);jbl.addActi on Liste ner(Acti on Liste ner) this);jb2 = new JButton(”非递归);jb2.addActio nListe ner(Actio nListe ner) this);jb3 = new J

25、Butto n(清空);jb3.addActio nListe ner(Actio nListe ner) this);/添加按钮pan el2.setLayout (new GridLayout(1, 3);pan el2.add(jb1);pa nel2.add(jb2);pa nel2.add(jb3);topPa nel.add(pa nel2);add(topPa nel,BorderLayout.NORTH);jta = new JTextArea(10, 15);jta.setText(s);jta.setEditable(false);jta.setTabSize(4);jta

26、.setFo nt( new Fon t(标楷体,Fon t.BOLD, 16);jta.setL in eWrap(true);/激活自动换行功能jta.setWrapStyleWord(true);/激活断行不断字功能jscrollPa ne = new JScrollPa ne(jta);add(jscrollPa ne ,BorderLayout.CENTER);private void Quee nRs() int n =ln teger.parse In t(i nputNum.getText();Quee nRST qr = new Quee nRST( n,this);priv

27、ate void Quee nNr() int n =ln teger.parse In t(i nputNum.getText();Quee nRST qr = new Quee nRST( n,this);public static void main( Stri ng args) Quee nMain app = new Quee nMain();即p.setTitle(”八皇后问题);app.setVisible(true);app.setBou nds(300,100,400,600); app.setDefaultCloseOperati on (JFrame.EXIT_ON_CL

28、OSE); 一 一 public void actio nPerformed(Actio nEve nt e) if (e.getSource() = jb1) this.jta.setText( null); Quee nRs();if(e.getSource() = jb2)this.jta.setText( null);Quee nNr();if(e.getSource() = jb3)this.i nputNum.setText (nu II);this.jta.setText(s);Quee nNS类：package com.Liste n;import java.util.Sca

29、nner;public class Quee nNR public int coun t=0;public boolea n isExist=false;public int MAXQUEEN;public int flag;/为解空间的值，即各个N*N方格的值public in t record;/ 2*N ,第一行记录每一行对应的列，第二行记录对应的回溯点(每一列对应的值)/ 构造函数public Quee nNR(i nt n)MAXQUEEN=n;赋初始值flag=new in tMAXQUEENMAXQUEEN;定义判断数组record=new in t2MAXQUEEN; /定义记

30、录数组reset(flag);reset(record); /初始化parseQuee n(flag,record);public void reset(i nt flag) int i,j,m=flag .len gth ,n=flag0.le ngth;for( i=0;im;i+)for(j=0;j0) i-;往上移else /*System.out.pri ntl n( iojhipo);*/ /在此return ;/结束else/当前点为普通点if(!isTrue(record,i,j) if(j0) i-;/结束回溯该定位点位置不满足要求 往右找定位点往上找定位点else/*Sys

31、tem.out.pri ntln( iojhipo);*/return ;/结束else/该定位点位置满足要求/放置定位点flagij=1;record0i=i;record1i=j;if(i0;)i-;if(record1i=n)是否同一列f=false; break;if(left=0)if(record1i=left)是否同一右斜f=false; break; else left-;if(right=le n-1)if(record1i=right)/是否同一左斜f=false; break; else right+;return f;/输出函数：public void prin tAr

32、ray(i nt叩 flag) int i,j,le n=flagen gth,le n2=flag0.le ngth;coun t+;(”这是第+count+路径：)；for( i=0;ile n; i+)for(j=0;jle n2;j+)if(flagij=-1)System.out.pri nt(+ );elseSystem.out.pri nt(0 );System.out.pri ntl n();System.out.pri ntl n();/reset(flag);/* public void prin tArray(i nt叩 record) coun t+;System.ou

33、t.print(第+count+种走法 n);for(i nt i=O;iMAXQUEEN;i+)for(i nt j=0;j=4):);(”皇后有+app.count+条路径);in .close();Quee nRS类 package com Liste n;累计方案总数皇后个数，同时也是棋盘行列总数import java.util.Sca nner; public class Quee nRS public int num = 0; / public int MAXQUEEN ;/public in t cols;/ 定义cols数组，表示8列棋子摆放情况public Quee nRS(

34、i nt n) MAXQUEEN = n;cols = new in tMAXQUEEN;/ 核心函数getArra ngeme nt(0);System.out.pri nt(n);System.out.println(MAXQUEEN+皇后问题有+num+种摆放方法。);/核心函数代码public void getArra ngeme nt(i nt n)/遍历该列所有不合法的行，并用rows数组记录，不合法即rowsi=trueboolea n rows = new boolea nMAXQUEEN;/判断该点是不是合法，如果有合法的，不赋值为nullfor(i nt i=0;i= 0)

35、 rowscolsi-d=true;if(colsi+d = MAXQUEEN-1) rowscolsi+d=true;for(i nt i=0;iMAXQUEEN;i+)/判断该行是否合法合法就跳出选出第一个可以添加的行if(rowsi)c on ti nue;/设置当前列合法棋子所在行数cols n = i;/当前列不为最后一列时if(nM AXQUEEN-1)getArra ngeme nt( n+1);elsenum+; / 累计方案个数prin tChessBoard();打印棋盘信息/ 打印函数public void prin tChessBoard()System.out.pri

36、 nt(第+nu m+ 种走法 n);for(i nt i=0;iMAXQUEEN;i+)for(i nt j=O;j=4):);Quee nRS quee n = new Quee nRS(i n.n extI nt();6.2 C语言源代码:/八皇后问题#i nclude #in elude /输出0代表皇后void prin tFF(i nt *positi on)int i=0,j=0;for(i = 0; i 8; +i)for(j = 0; j 8; +j)if(positi on i = j) prin tf(0 );elseprin tf(+ );prin tf(n);prin

37、 tf(n);/非递归算法void empress(i nt *co un t, int *positi on)int i, j, flag;while(positio n8 != 1)+positi on 0;for(i = 0; i 8; +i)if(positi on i = 8)positi on i = 0;+positi on i+1;flag = 1;/判断结果是否满足条件for(i = 0; i 8; +i)for(j = 0; j 8; +j)if(i != j)=abs(i-j)if(positi on i = positi on j) flag = 0;elseif(abs(positioni- positionj)flag = 0;if(flag = 1) printf(第d#解法：n,(*count