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

八皇后问题实验报告 递归 非递归 java C语言 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 题目:八皇后问题 指导教师: 胡* 学生院系: 数学学院 学生班级: 信计*班 学生姓名: 黎*文 学生学号: 14070204** 2016年12月30日 1 目录 一.功能以及需求分析................................................................................................... 3 1.1 问题的由来和背景......................................................................................... 3 1.2 问题的基本解决思路..................................................................................... 3 1.3 问题的应用..................................................................................................... 3 二.总体设计................................................................................................................... 4 2.1 运行环境......................................................................................................... 4 2.2 程序框架......................................................................................................... 4 ......................................................................... 4 2.3 算法分析................................ 2.3.1 总体算法分析............................................................................................. 4 2.3.2 非递归算法分析......................................................................................... 6 2.3.3 递归算法的分析......................................................................................... 6 三.详细设计.................................................................................................................. 6 3.1 递归法的详细设计......................................................................................... 6 3.2 非递归法的详细设计..................................................................................... 8 ..................................................................... 10 四.具体实现及运行................................ 4.1 QueenMainl类的实现:.............................................................................. 10 4.2 QueenNR类:................................................................................................ 10 4.3 QueenRS类:................................................................................................ 11 4.4 C语言程序:................................................................................................ 11 五. 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ....................................................................................................................... 12 六.代码清单................................................................................................................. 13 6.1 Java代码:.................................................................................................. 13 6.2 C语言源代码:............................................................................................ 20 2 一.功能以及需求分析 1.1 问题的由来和背景 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯?贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。1854年在柏林的象棋杂志上不同的作者发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 了40种不同的解，后来有人用图论的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后,为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n，而皇后个数也变成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序列问题也可以从中得到启发。 3 二.总体设计 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 程序框架 (1)MainQueen:实现可视化界面，可以选择递归和非递归两种算法得到八皇后问题的解，并将答案打印出来。 (2)QueenNR:采用非递归方法求解问题。 (3)QueenRS: 采用递归方法求解问题。 (4)编译C语言程序。 2.3 算法分析 2.3.1 总体算法分析 算法的核心是回溯法，也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径。当撤销之后满足条件，就一直做下去，直到试探完所有的可能解。 总结如下: (1)设置初始化的方案(给变量赋初值，读入已知数据等)。 (2)变换方式去试探，若全部试完则转(7)。 (3)判断此法是否成功(通过约束函数)，不成功则转(2)。 (4)试探成功则前进一步再试探。 (5)正确方案还未找到则转(2)。 (6)已找到一种方案则记录并打印。 (7)退回一步(回溯)，若未退到头则转(2)。 (8)已退到头则结束或打印无解 另外一个关键就是对于每一个部分解的判定，可归纳问题的条件为: 1.不在同一行(列)上 2.不在同一斜线上 3.不在同一反斜线上 4 具体到八皇后的问题，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行(或列)遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置与前面的棋子不在同一行(或列)。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行(或列)所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行(或列)的所有位置都不合适，就返回上一行(或列)继续该行(或列)的其他位置遍历，当我们顺利遍历到最后一行(或列)，且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。 接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第一列开始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的，当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其与第一个棋子一个同在一行，一个同在一条斜线上。第二列第三行成为第二列第一个合适的位置，以此类推，第三列的第5行又会是一个合适位置，这个过程中，我们注意到，每一列的合适位置都是受到前面几列的位置所影响，归纳如下: 假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是3行，2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数，数组下标从0开始，其中数组下标表示列数，数组的元素值表示该列棋子所在行数，当前列为N(N>=0,N=0,m=0 ,与第m列的棋子不在同一斜线上) cols[N] != cols??[m] + (N-m) (<=8-1,与第m列的棋子不在同一反斜线上) 为了使此程序能够解决N皇后的问题，一般将参数改成N，已解决N皇后的问题，当然，这还和计算机性能和算法差异有关，此程序一般能解决到15皇后的问题。在Java程序中以实现N皇后问题。 5 2.3.2 非递归算法分析 程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。 2.3.3 递归算法的分析 第1次考虑把皇后放在第1行的某个位置， 第2次放的时候就不用去放在第一行了，因为这样放皇后间是可以互相攻击的。 第2次我就考虑把皇后放在第2行的某个位置，第3次我考虑把皇后放在第3行的某个位置， 这样依次去递归。每计算1行，递归一次，每次递归里面考虑8列， 即对每一行皇后有8个可能的位置可以放。找到一个与前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。 第i行的皇 用一个一维数组来表示相应行对应的列，比如cols[i]=j表示， 后放在第j列。如果当前行是r，皇后放在哪一列呢,cols[r]列。 一共有8列，所以我们要让cols[r]依次取第0列，第1列，第2列……一直到第7列， 每取一次我们就去考虑，皇后放的位置会不会和前面已经放了的皇后有冲突。 怎样是有冲突呢,同行，同列，对角线。由于已经不会同行了，所以不用考虑这一点。 只有满足了当前皇后和前面所有的皇后都不会互相攻击的时候，才能进入下一级递归。 三.详细设计 3.1 递归法的详细设计 (1) 定义一个cols[]数组，存储八皇后问题中每一列(j)对应放置的皇后的位置(i)。 (2) 定义getArrangement(int n) 递归函数，其中定义一个boolean型 rows[]数组，记录每一行能够正常放置的位置，如果能放置，设置为true，默认为null。函数中，先找出每列合适的的第一个位置。然后判断是不是最后一列，是最后一列就输出，不是就进入递归。如果该列没找到一个合适的位置，跳出此次递归，进入上一次递归。 6 具体函数如下: public void getArrangement(int n){ //遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; //判断该点是不是合法 ，如果有合法的，不赋值为 null for(int i=0;i= 0) rows[cols[i]-d]=true; if(cols[i]+d <= MAXQUEEN-1) rows[cols[i]+d]=true; } for(int i=0;i0;){ i--; if(record[1][i]==n){//是否同一列 f=false; break; } if(left>=0){ if(record[1][i]==left){//是否同一右斜 f=false; break; } else left--; } if(right<=len-1){ if(record[1][i]==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(record[1][i]!=-1){//判断当前点是否为上次退行的位置，是则进行再定位 //清除原来在回溯一行定位的点 8 j=record[1][i]; record[1][i]=-1; flag[i][j]=-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{//该定位点位置满足要求 //放置定位点 flag[i][j]=1; record[0][i]=i; record[1][i]=j; if(i0) i--;//往上找定位点 else {/*System.out.println("iojhipo");*/return ;}//结束 } } else{//该定位点位置满足要求 放置定位点 // flag[i][j]=1; record[0][i]=i; record[1][i]=j; if(i0;){ i--; if(record[1][i]==n){//是否同一列 f=false; break; } if(left>=0){ if(record[1][i]==left){//是否同一右斜 f=false; break; } else left--; } if(right<=len-1){ if(record[1][i]==right){//是否同一左斜 f=false; break; } else right++; } } } return f; } //输出函数: public void printArray(int[][] flag) { int i,j,len=flag.length,len2=flag[0].length; count++; System.out.println("这是第"+count+"路径:"); for( i=0;i=4):"); QueenNR app = new QueenNR(in.nextInt()); System.out.println("皇后有"+app.count+"条路径"); in.close(); } } QueenRS类: package com.Listen; import java.util.Scanner; public class QueenRS { public int num = 0; //累计方案总数 public int MAXQUEEN ;//皇后个数，同时也是棋盘行列总数 public int[] cols; //定义cols数组，表示8列棋子摆放情况 public QueenRS(int n) { MAXQUEEN = n; cols = new int[MAXQUEEN]; //核心函数 getArrangement(0); System.out.print("\n"); System.out.println(MAXQUEEN+"皇后问题有"+num+"种摆放方法。"); } //核心函数代码 public void getArrangement(int n){ //遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true boolean[] rows = new boolean[MAXQUEEN]; 18 //判断该点是不是合法 ，如果有合法的，不赋值为 null for(int i=0;i= 0) rows[cols[i]-d]=true; if(cols[i]+d <= MAXQUEEN-1) rows[cols[i]+d]=true; } for(int i=0;i=4):"); QueenRS queen = new QueenRS(in.nextInt()); } } 19 6.2 C语言源代码: //八皇后问题 #include #include //输出0代表皇后 void printFF(int *position){ int i=0,j=0; for(i = 0; i < 8; ++i) { for(j = 0; j < 8; ++j) { if(position[i] == j) printf("0 "); else printf("+ "); } printf("\n"); } printf("\n"); } //非递归算法 void empress(int *count,int *position) { int i, j, flag; while(position[8] != 1) { ++position[0]; for(i = 0; i < 8; ++i) { if(position[i] == 8) { position[i] = 0; ++position[i+1]; } } flag = 1; //判断结果是否满足条件 for(i = 0; i < 8; ++i) { for(j = 0; j < 8; ++j) 20 { if(i != j) { if(position[i] == position[j]) flag = 0; else if(abs(position[i] - position[j]) == abs(i-j)) flag = 0; } } } if(flag == 1) { printf("第%d种解法:\n",(*count)+1); printFF(position); } (*count) += flag; } } void QueenNS(){ int count = 0; int position[9] = {0}; empress(&count,position); printf("%d种解\n", count); } //递归法实现八皇后问题 //参数row表示起始行，参数n表示列数 //参数(*chess)[8]表示指向棋盘每一行的指针 int notdanger(int row,int j,int (*chess)[8]){ int i,k; //判断列方向 for(i=0;i<8;i++){ if(*(*(chess+i)+j)==1){//这一列已存在皇后 return 0; } } //判断左上方 for(i=row,k=j;i>=0&&k>=0;i--,k--){ if(*(*(chess+i)+k)==1){ return 0; } } //判断右上方 for(i=row,k=j;i>=0&&k<8;i--,k++){ if(*(*(chess+i)+k)==1){ return 0; 21 } }//递归函数 void eightqueen(int *count,int row,int n,int (*chess)[8]){ int chess2[8][8],i,j; for(i=0;i<8;i++){ for(j=0;j<8;j++){ chess2[i][j]=chess[i][j]; } } if(row==8){ printf("第%d种:\n",++(*(count))); for(i=0;i<8;i++){ for(j=0;j<8;j++){ printf("%d ",*(*(chess2+i)+j)); } printf("\n"); } } else { //判断这个位置是否有危险 //如果有危险，那继续往下 for(j=0;j