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

八皇后问题实验报告递归非递归javaC语言+分析
数据结构课程设计

题目：八皇后问题

指导教师： 胡*
学生院系： 数学学院
学生班级： 信计*班
学生姓名： 黎*文
学生学号： 14070204**

2016年12月30日

目录

一.功能以及需求分析 3
1.1 问题的由来和背景 3
1.2 问题的基本解决思路 3
1.3 问题的应用 3
二.总体设计 4
2.1 运行环境 4
2.2 程序框架 4
2.3 算法分析 4
2.3.1 总体算法分析 4
2.3.2 非递归算法分析 6
2.3.3 递归算法的分析 6
三.详细设计 6
3.1 递归法的详细设计 6
3.2 非递归法的详细设计 7
四.具体实现及运行 10
4.1 QueenMainl类的实现： 10
4.2 QueenNR类： 10
4.3 QueenRS类： 11
4.4 C语言程序： 11
五. 总结 12
六.代码清单 13
6.1 Java代码： 13
6.2 C语言源代码： 20

一.功能以及需求分析
1.1 问题的由来和背景
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出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序列问题也可以从中得到启发。
二.总体设计
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.不在同一反斜线上
具体到八皇后的问题，我们可以逐行或者逐列来进行可行摆放方案的遍历，每一行（或列）遍历出一个符合条件的位置，接着就到下一行或列遍历下一个棋子的合适位置，这种遍历思路可以保证我们遍历过程中有一个条件是绝对符合的——就是下一个棋子的摆放位置及前面的棋子不在同一行（或列）。接下来，我们只要判断当前位置是否还符合其他条件，如果符合，就遍历下一行（或列）所有位置，看看是否继续有符合条件的位置，以此类推，如果某一个行（或列）的所有位置都不合适，就返回上一行（或列）继续该行（或列）的其他位置遍历，当我们顺利遍历到最后一行（或列），且有符合条件的位置时，就是一个可行的8皇后摆放方案，累加一次八皇后可行方案的个数，然后继续遍历该行其他位置是否有合适的，如果没有，则返回上一行，遍历该行其他位置，依此下去。这样一个过程下来，我们就可以得出所有符合条件的8皇后摆放方案了。这是一个深度优先遍历的过程，同时也是经典的递归思路。
接下来，我们以逐列遍历，具体到代码，进一步说明。首先，从第一列开始找第一颗棋子的合适位置，我们知道，此时第一列的任何一个位置都是合适的，当棋子找到第一个合适的位置后，就开始到下一列考虑下一个合适的位置，此时，第二列的第一行及第二行显然就不能放第二颗棋子了，因为其及第一个棋子一个同在一行，一个同在一条斜线上。第二列第三行成为第二列第一个合适的位置，以此类推，第三列的第5行又会是一个合适位置，这个过程中，我们注意到，每一列的合适位置都是受到前面几列的位置所影响，归纳如下：
假设前面1列的棋子放在第3行，那当前列不能放的位置就一定是3行，2行，4行。因为如果放在这三行上就分别跟前一列的棋子同在一行、同在斜线、同在反斜线上，不符合我们的要求。现在我们用cols数组来表示8个列棋子所放的行数，数组下标从0开始，其中数组下标表示列数，数组的元素值表示该列棋子所在行数，当前列为N（N>=0,N<max），即cols[N-1]=3,则有：
cols[N] != cols[N-1]（=3，表示不在同一行）

cols[N] != cols[N-1]-1（=3-1=2，表示不在同一斜线上)

ols[N]!=cols[N-1]+1(=3+1,表示不在同一反斜线上)
这里我们注意到，如果N-2列存在的话，那么我们还要考虑当前列N不及N-2列的棋子同行，同斜线，同反斜线。把当前列N的前面的某一列设为m,则m的所有取值为｛m>=0,m<N｝的集合,故又可在上面式子的基础，归纳为如下：
cols[N] != cols[m]（及第m列的棋子不在同一行）

cols[N] != cols­­[m] -（N-m）(>=0 ,及第m列的棋子不在同一斜线上)

cols[N] != cols­­[m] + (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个可能的位置可以放。找到一个及前面行的皇后都不会互相攻击的位置， 然后再递归进入下一行。找到一组可行解即可输出，然后程序回溯去找下一组可靠解。
用一个一维数组来表示相应行对应的列，比如cols[i]=j表示， 第i行的皇后放在第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。函数中，先找出每列合适的的第一个位置。然后判断是不是最后一列，是最后一列就输出，不是就进入递归。如果该列没找到一个合适的位置，跳出此次递归，进入上一次递归。

具体函数如下：
public void getArrangement(int n){
//遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true
boolean[] rows = new boolean[MAXQUEEN];
//判断该点是不是合法 ，如果有合法的，不赋值为 null
for(int i=0;i<n;i++){
// 判断行是否合法
rows[cols[i]]=true;
int d = n-i;
//判断左右斜线是否合法
if(cols[i]-d >= 0) rows[cols[i]-d]=true;
if(cols[i]+d <= MAXQUEEN-1) rows[cols[i]+d]=true;
}
for(int i=0;i<MAXQUEEN;i++){
//判断该行是否合法 合法就跳出 选出第一个可以添加的行
if(rows[i])continue;
cols[n] = i; //设置当前列合法棋子所在行数
if(n<MAXQUEEN-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;i<MAXQUEEN;i++){
for(int j=0;j<MAXQUEEN;j++){
if(i==cols[j]){
System.out.print("0 ");
}else
System.out.print("+ ");
}
System.out.print("\n");
}
}

3.2 非递归法的详细设计

（1）定义一个flag[n][n]数组，作为存储皇后位置。定义record[2][n]数组作为回溯步骤，其中record[0][n]记录序号对应行的位置，record[1][n]，记录序号对应列的位置。多几个数组便于理解和回溯。
（2） 定义reset(int[][] flag)函数，将数组flag全部初始化为-1；代码略。
（3） 定义 isTrue(int[][] record, int m, int n) 判断函数 。判断对应的点能否放置皇后。采用了和递归法中不一样的思路，将判断独立成一个函数，利用记录数组和位置m,n判定。使得对点的判断更加直观。
public boolean isTrue(int[][] record, int m, int n) {
int left = n-1,right = n+1,len=record[0].length;
boolean f=true;
if(m==0)
return true;
else{
for(int i=m;i>0;){ 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){//判断当前点是否为上次退行的位置，是则进行再定位
//清除原来在回溯一行定位的点
j=record[1][i];
record[1][i]=-1;
flag[i][j]=-1; //把回溯点的值改为-1
if(j<len-1) j++;//往右移
else{
if(i>0) i--;//往上移
else {/*System.out.println("iojhipo");*/ //在此结束回溯
return ;
}//结束
}
}
else{//当前点为普通点
if(!isTrue(record,i,j)){//该定位点位置不满足要求
if(j<len-1) j++;//往右找定位点
else{
if(i>0) i--;//往上找定位点
else {/*System.out.println("iojhipo");*/return ;}//结束
}
}
else{//该定位点位置满足要求
//放置定位点
flag[i][j]=1; record[0][i]=i; record[1][i]=j;

if(i<len-1){//往下走
i++; j=0;
} //end if
else{//到末尾，找到一条路径
isExist=true;
printArray(flag);//打印
record[1][i]=-1;//做回溯处理准备
flag[i][j]=-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 com.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.JButton;
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();
JButton jb1, jb2, jb3;
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);
jb1 = new JButton("递归");
jb1.addActionListener((ActionListener) this);
jb2 = new JButton("非递归");
jb2.addActionListener((ActionListener) this);
jb3 = new JButton("清空");
jb3.addActionListener((ActionListener) this);
//添加按钮
panel2.setLayout(new GridLayout(1, 3));
panel2.add(jb1);panel2.add(jb2);panel2.add(jb3);
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() == jb1) {
this.jta.setText(null);
QueenRs();

}
if(e.getSource() == jb2){
this.jta.setText(null);
QueenNr();
}
if(e.getSource() == jb3){
this.inputNum.setText(null);
this.jta.setText(s);
}
}
}
QueenNS类：
package com.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 int[MAXQUEEN][MAXQUEEN];//定义判断数组
record=new int[2][MAXQUEEN]; //定义记录数组
reset(flag);
reset(record); //初始化
parseQueen(flag,record);
}
public void reset(int[][] flag) {
int i,j,m=flag.length,n=flag[0].length;
for( i=0;i<m;i++)
for(j=0;j<n;j++){
flag[i][j]=-1;
}
}
//定义核心算法
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){//判断当前点是否为上次退行的位置，是则进行再定位
//清除原来在回溯一行定位的点
j=record[1][i];
record[1][i]=-1;
flag[i][j]=-1; //把回溯点的值改为-1
if(j<len-1) j++;//往右移
else{
if(i>0) i--;//往上移
else {/*System.out.println("iojhipo");*/ //在此结束回溯
return ;
}//结束
}
}
else{//当前点为普通点
if(!isTrue(record,i,j)){//该定位点位置不满足要求
if(j<len-1) j++;//往右找定位点
else{
if(i>0) i--;//往上找定位点
else {/*System.out.println("iojhipo");*/return ;}//结束
}
}
else{//该定位点位置满足要求
//放置定位点
flag[i][j]=1;
record[0][i]=i;
record[1][i]=j;

if(i<len-1){//往下走
i++;
j=0;
} //end if
else{//到末尾，找到一条路径
isExist=true;
printArray(flag);//打印
record[1][i]=-1;//做回溯处理准备
flag[i][j]=-1;
/* if(i==0)//结束
return ;