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

- .数据构造课程设计题目：八皇后问题 指导教师：* 学生院系： 数学学院 学生班级：信计*班 学生XX：黎*文 学生学号： 14070204*2016年12月30日目录一.功能以及需求分析31.1 问题的由来和背景31.2 问题的根本解决思路31.3 问题的应用3二.总体设计42.1 运行环境42.2 程序框架42.3 算法分析42.3.1 总体算法分析42.3.2 非递归算法分析62.3.3 递归算法的分析6三.详细设计63.1 递归法的详细设计63.2 非递归法的详细设计7四.具体实现及运行104.1 QueenMainl类的实现：104.2 QueenNR类：104.3 QueenRS类：114.4 C语言程序：11五. 总结12六.代码清单136.1 Java代码：136.2 C语言源代码：20一.功能以及需求分析1.1 问题的由来和背景八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机创造后，有多种计算机语言可以解决此问题。八皇后问题是一个以国际象棋为背景的问题：如何能够在 88 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了到达此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为nn，而皇后个数也变成n。当且仅当 n = 1 或 n 4 时问题有解。1.2 问题的根本解决思路 八皇后问题最早是由国际西洋棋棋手马克斯贝瑟尔于1848年提出。之后陆续有数学家对其进展研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法。 八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N叠在一起的8*8棋盘，每棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一完整的8皇后图，称完卷。这里实际操作时多加一行多加一列即第0行第0列，但这一行/列不作输出，只是作此行/列有无皇后的参考。 总的来说现在解八皇后问题的总体算法都是采用回溯法，也叫作穷搜法，再穷搜的时候去掉分支，减少不必要的运算，对于八皇后问题的求解，一般只能做出15皇后问题，有局部算法高手在有精良设备的情况下算出了25皇后的解。受算法和硬件计算能力的影响，因为计算量为O(n!)，而且回溯法使用的存空间特别大，所以此问题的求解还有很多可以探究的地方，尤其是算法上的改良。1.3 问题的应用八皇后问题可以用来解决地图的着色问题，以及迷宫的求解问题，同时，八皇后问题是一个典型的回溯法求解问题，可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。二.总体设计2.1 运行环境 1编译环境：JDK 1.8 ，以及eclipse ，Mars 4.5.2，Visual C+ 6.0 2电脑系统： Windows server 2003 32位 3编译语言：Java，C语言2.2 程序框架 1MainQueen：实现可视化界面，可以选择递归和非递归两种算法得到八皇后问题的解，并将答案打印出来。 2QueenNR：采用非递归方法求解问题。 3QueenRS： 采用递归方法求解问题。 4编译C语言程序。2.3 算法分析2.3.1 总体算法分析算法的核心是回溯法，也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开场逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，那么撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径。当撤销之后满足条件，就一直做下去，直到试探完所有的可能解。 总结如下：(1)设置初始化的方案给变量赋初值，读入数据等。(2)变换方式去试探，假设全部试完那么转(7)。(3)判断此法是否成功通过约束函数，不成功那么转(2)。(4)试探成功那么前进一步再试探。(5)正确方案还未找到那么转(2)。(6)已找到一种方案那么记录并打印。(7)退回一步回溯，假设未退到头那么转(2)。(8)已退到头那么完毕或打印无解 另外一个关键就是对于每一个局部解的判定，可归纳问题的条件为: 1.不在同一行列上 2.不在同一斜线上 3.不在同一反斜线上 具体到八皇后的问题，我们可以逐行或者逐列来进展可行摆放方案的遍历，每一行或列遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的适宜位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的就是下一个棋子的摆放位置与前面的棋子不在同一行或列。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行或列所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行或列的所有位置都不适宜，就返回上一行或列继续该行或列的其他位置遍历，当我们顺利遍历到最后一行或列，且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有适宜的，如果没有，那么返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。 接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第一列开场找第一颗棋子的适宜位置，我们知道，此时第一列的任何一个位置都是适宜的，当棋子找到第一个适宜的位置后，就开场到下一列考虑下一个适宜的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，一个同在一条斜线上。第二列第三行成为第二列第一个适宜的位置，以此类推，第三列的第5行又会是一个适宜位置，这个过程中，我们注意到，每一列的适宜位置都是受到前面几列的位置所影响，归纳如下： 假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是3行，2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数，数组下标从0开场，其中数组下标表示列数，数组的元素值表示该列棋子所在行数，当前列为NN=0,N=0,m=0 ,与第m列的棋子不在同一斜线上) colsN != colsm + (N-m) (=8-1,与第m列的棋子不在同一反斜线上) 为了使此程序能够解决N皇后的问题，一般将参数改成N，已解决N皇后的问题，当然，这还和计算机性能和算法差异有关，此程序一般能解决到15皇后的问题。在Java程序中以实现N皇后问题。2.3.2 非递归算法分析 程序首先对N行中的每一行进展探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进展探测，看是否可以放置皇后，如果可以，那么在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，那么继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，那么说明已经找到所有的解程序终止。如果该行已经是最后一行，那么探测完该行后，如果找到放置皇后的位置，那么说明找到一个结果，打印出来。但是此时并不能再此处完毕程序，因为我们要找的是所有N皇后问题所有的解，此时应该去除该行的皇后，从当前放置皇后列数的下一列继续探测。2.3.3 递归算法的分析 第1次考虑把皇后放在第1行的某个位置， 第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。 第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递归。每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。 用一个一维数组来表示相应行对应的列，比方colsi=j表示， 第i行的皇后放在第j列。如果当前行是r，皇后放在哪一列呢？colsr列。 一共有8列，所以我们要让colsr依次取第0列，第1列，第2列一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。 怎样是有冲突呢？同行，同列，对角线。由于已经不会同行了，所以不用考虑这一点。 只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。三.详细设计3.1 递归法的详细设计 1 定义一个cols数组，存储八皇后问题中每一列j对应放置的皇后的位置i。 2 定义getArrangement(int n) 递归函数，其中定义一个boolean型 rows数组，记录每一行能够正常放置的位置，如果能放置，设置为true，默认为null。函数中，先找出每列适宜的的第一个位置。然后判断是不是最后一列，是最后一列就输出，不是就进入递归。如果该列没找到一个适宜的位置，跳出此次递归，进入上一次递归。具体函数如下： public void getArrangement(int n)/遍历该列所有不合法的行，并用rows数组记录，不合法即rowsi=true boolean rows = new booleanMAXQUEEN; /判断该点是不是合法 ，如果有合法的，不赋值为 null for(int i=0;i= 0) rowscolsi-d=true; if(colsi+d = MAXQUEEN-1) rowscolsi+d=true; for(int i=0;iMAXQUEEN;i+) /判断该行是否合法 合法就跳出 选出第一个可以添加的行 if(rowsi)continue; colsn = i; /设置当前列合法棋子所在行数 if(nMAXQUEEN-1) /当前列不为最后一列时 getArrangement(n+1); else num+; /累计方案个数 printChessBoard();/打印棋盘信息 3定义输出函数public void printChessBoard()，输出函数比拟简单，利用全部赋值之后clos数组，序号代表列，序列的值代表行。两个for循环即可输出。+代表空，0代表皇后。具体函数如下： public void printChessBoard() System.out.print(第+num+种走法 n); for(int i=0;iMAXQUEEN;i+) for(int j=0;j0;) i-; if(record1i=n)/是否同一列 f=false; break; if(left=0) if(record1i=left)/是否同一右斜 f=false; break; else left-; if(right=len-1) if(record1i=right)/是否同一左斜 f=false; break; else right+; 4 定义 parseQueen( int flag,int record) 核心回溯函数。 public void parseQueen( int flag,int record) int i=0,j=0,len=flag.length; /System.out.println(length=+len); while(true) if(record1i!=-1)/判断当前点是否为上次退行的位置，是那么进展再定位 /去除原来在回溯一行定位的点 j=record1i; record1i=-1; flagij=-1; /把回溯点的值改为-1 if(j0) i-;/往上移 else /*System.out.println(iojhipo);*/ /在此完毕回溯 return ; /完毕 else/当前点为普通点 if(!isTrue(record,i,j)/该定位点位置不满足要求 if(j0) i-;/往上找定位点 else /*System.out.println(iojhipo);*/return ;/完毕 else/该定位点位置满足要求 /放置定位点 flagij=1; record0i=i; record1i=j; if(ilen-1)/往下走 i+; j=0; /end if else/到末尾，找到一条路径 isExist=true; printArray(flag);/打印 record1i=-1;/做回溯处理准备 flagij=-1; i-;/往上继续搜寻 /end else 5定义输出函数 rintArray(int flag)，代码略见代码清单。注明：C语言程序的分析和上述类似，不在赘述。四.具体实现及运行4.1 QueenMainl类的实现：4.2 QueenNR类： 实现了QueenMain类的非递归按钮功能4.3 QueenRS类：实现了QueenMain类的递归按钮功能4.4 C语言程序：五. 总结1. 八皇后问题的求解计算量是特别大的，对于非递归算法，由于等价于穷搜法，他的时间复杂度约等于O(n！) ，即是n的全排列。虽然采用了去除分支的方法，但是对于总体来说，并不会减少太多运算，所以对于这种大型的计算。还需要改良算法，并且需要硬件的支持。本实验一般只能解决到12皇后，而且计算时间都比拟长。 2. 对于递归算法，效率比拟低，但是便于理解，方便写代码。 3. 对于两个算法的比拟，都是用的回溯法，只是在具体的回溯方法上的区别。 4. 八皇后问题在实际的生活中有很多的得到实用的地方，熟练地掌握八皇后问题的求解过程，能解决很多实际中的算法问题。比方迷宫问题和地图着色问题，都可以应用相应的算法。六.代码清单6.1 Java代码：QueenMainl类：package .Listen;import java.awt.BorderLayout;import java.awt.CardLayout;import java.awt.Container;import java.awt.Font;import java.awt.GridLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.BoxLayout;import javax.swing.utton;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JPanel;import javax.swing.JScrollPane;import javax.swing.JTextArea;import javax.swing.JTextField;public class QueenMain extends JFrame implements ActionListener JPanel topPanel = new JPanel(); utton 1, 2, 3; JTextArea jta = null; JScrollPane jscrollPane; JLabel inputLabel;JTextField inputNum; JPanel panel1,panel2; String s =请在上方输入4-10的数查看八皇后路径问题：;public QueenMain() setLayout(new BorderLayout();/ 设置按钮panel1 = new JPanel();panel2 = new JPanel();topPanel = new JPanel();inputLabel = new JLabel(请输入数字：);inputNum = new JTextField(25);panel1.add(inputLabel);panel1.add(inputNum);/topPanel.setLayout( BoxLayout.Y_AXIS);topPanel.setLayout(new BoxLayout(topPanel, BoxLayout.Y_AXIS);topPanel.add(panel1);1 = new utton(递归); 1.addActionListener(ActionListener) this);2 = new utton(非递归);2.addActionListener(ActionListener) this);3 = new utton(清空);3.addActionListener(ActionListener) this);/添加按钮panel2.setLayout(new GridLayout(1, 3);panel2.add(1);panel2.add(2);panel2.add(3);topPanel.add(panel2);add(topPanel,BorderLayout.NORTH);jta = new JTextArea(10, 15); jta.setText(s); jta.setEditable(false);jta.setTabSize(4);jta.setFont(new Font(标楷体, Font.BOLD, 16);jta.setLineWrap(true);/ 激活自动换行功能jta.setWrapStyleWord(true);/ 激活断行不断字功能jscrollPane = new JScrollPane(jta);add(jscrollPane ,BorderLayout.CENTER); private void QueenRs() int n =Integer.parseInt(inputNum.getText() ; QueenRST qr = new QueenRST(n,this); private void QueenNr() int n =Integer.parseInt(inputNum.getText() ; QueenRST qr = new QueenRST(n,this); public static void main(String args) QueenMain app = new QueenMain();app.setTitle(八皇后问题);app.setVisible(true);app.setBounds(300,100,400,600);app.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);public void actionPerformed(ActionEvent e) if (e.getSource() = 1) this.jta.setText(null);QueenRs();if(e.getSource() = 2)this.jta.setText(null);QueenNr();if(e.getSource() = 3)this.inputNum.setText(null);this.jta.setText(s); QueenNS类：package .Listen;import java.util.Scanner; public class QueenNR public int count=0; public boolean isExist=false; public int MAXQUEEN; public int flag;/为解空间的值 ，即各个N*N方格的值 public int record;/ 2*N ,第一行记录每一行对应的列，第二行记录对应的回溯点每一列对应的值 /构造函数 public QueenNR(int n) MAXQUEEN=n;/赋初始值 flag=new intMAXQUEENMAXQUEEN;/定义判断数组 record=new int2MAXQUEEN; /定义记录数组 reset(flag); reset(record); /初始化 parseQueen(flag,record); public void reset(int flag) int i,j,m=flag.length,n=flag0.length; for( i=0;im;i+) for(j=0;jn;j+) flagij=-1; /定义核心算法 public void parseQueen( int flag,int record) int i=0,j=0,len=flag.length; /System.out.println(length=+len); while(true) if(record1i!=-1)/判断当前点是否为上次退行的位置，是那么进展再定位 /去除原来在回溯一行定位的点 j=record1i; record1i=-1; flagij=-1; /把回溯点的值改为-1 if(j0) i-;/往上移 else /*System.out.println(iojhipo);*/ /在此完毕回溯 return ; /完毕 else/当前点为普通点 if(!isTrue(record,i,j)/该定位点位置不满足要求 if(j0) i-;/往上找定位点 else /*System.out.println(iojhipo);*/return ;/完毕 else/该定位点位置满足要求 /放置定位点 flagij=1; record0i=i; record1i=j; if(ilen-1)/往下走 i+; j=0; /end if else/到末尾，找到一条路径 isExist=true; printArray(flag);/打印 record1i=-1;/做回溯处理准备 flagij=-1; /* if(i=0)/完毕 return ; */ i-;/往上继续搜寻 /end else /判断函数： public boolean isTrue(int record, int m, int n) int left = n-1,r