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

- .
数据构造课程设计

题目：八皇后问题

指导教师：*
学生院系： 数学学院
学生班级：信计*班
学生XX：黎*文
学生学号： 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 .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 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 ;
*/
i--;//往上继续搜寻
} //end else
}
}
}
}

//判断函数：
public boolean isTrue(int[][] record, int m, int n) {
int left = n-1,r