八皇后问题实验报告 递归 非递归 java C语言 +分析.docx
《八皇后问题实验报告 递归 非递归 java C语言 +分析.docx》由会员分享，可在线阅读，更多相关《八皇后问题实验报告 递归 非递归 java C语言 +分析.docx（31页珍藏版）》请在冰点文库上搜索。
八皇后问题实验报告递归非递归javaC语言+分析
数据结构课程设计
题目：
八皇后问题
指导教师：
胡*
学生院系：
数学学院
学生班级：
信计*班
学生姓名：
黎*文
学生学号：
14070204**
2016年12月30日
一.功能以及需求分析
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）编译环境：
JDK1.8，以及eclipse，Mars4.5.2，VisualC++6.0
（2）电脑系统：
Windowsserver200332位
（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,Ncols[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,mcols[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（intn）递归函数，其中定义一个boolean型rows[]数组，记录每一行能够正常放置的位置，如果能放置，设置为true，默认为null。
函数中，先找出每列合适的的第一个位置。
然后判断是不是最后一列，是最后一列就输出，不是就进入递归。
如果该列没找到一个合适的位置，跳出此次递归，进入上一次递归。
具体函数如下：
publicvoidgetArrangement（intn）{
//遍历该列所有不合法的行，并用rows数组记录，不合法即rows[i]=true
boolean[]rows=newboolean[MAXQUEEN];
//判断该点是不是合法，如果有合法的，不赋值为null
for（inti=0;i//判断行是否合法
rows[cols[i]]=true;
intd=n-i;
//判断左右斜线是否合法
if（cols[i]-d>=0）rows[cols[i]-d]=true;
if（cols[i]+d<=MAXQUEEN-1）rows[cols[i]+d]=true;
}
for（inti=0;i//判断该行是否合法合法就跳出选出第一个可以添加的行
if（rows[i]）continue;
cols[n]=i;//设置当前列合法棋子所在行数
if（ngetArrangement（n+1）;
}else{
num++;//累计方案个数
printChessBoard（）;//打印棋盘信息
}
}
}
（3）定义输出函数publicvoidprintChessBoard（），输出函数比较简单，利用全部赋值之后clos数组，序号代表列，序列的值代表行。
两个for循环即可输出。
‘+’代表空，‘0’代表皇后。
具体函数如下：
publicvoidprintChessBoard（）{
System.out.print（"第"+num+"种走法\n"）;
for（inti=0;ifor（intj=0;jif（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,intm,intn）判断函数。
判断对应的点能否放置皇后。
采用了和递归法中不一样的思路，将判断独立成一个函数，利用记录数组和位置m,n判定。
使得对点的判断更加直观。
publicbooleanisTrue（int[][]record,intm,intn）{
intleft=n-1,right=n+1,len=record[0].length;
booleanf=true;
if（m==0）
returntrue;
else{
for（inti=m;i>0;）{i--;
if（record[1][i]==n）{//是否同一列
f=false;break;
}
if（left>=0）{
if（record[1][i]==left）{//是否同一右斜
f=false;break;
}
elseleft--;
}
if（right<=len-1）{
if（record[1][i]==right）{//是否同一左斜
f=false;break;
}
elseright++;
}
}
}
（4）定义parseQueen（int[][]flag,int[][]record）核心回溯函数。
publicvoidparseQueen（int[][]flag,int[][]record）{
inti=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（jelse{
if（i>0）i--;//往上移
else{/*System.out.println（"iojhipo"）;*///在此结束回溯
return;
}//结束
}
}
else{//当前点为普通点
if（!
isTrue（record,i,j））{//该定位点位置不满足要求
if（jelse{
if（i>0）i--;//往上找定位点
else{/*System.out.println（"iojhipo"）;*/return;}//结束
}
}
else{//该定位点位置满足要求
//放置定位点
flag[i][j]=1;record[0][i]=i;record[1][i]=j;
if（ii++;j=0;
}//endif
else{//到末尾，找到一条路径
isExist=true;
printArray（flag）;//打印
record[1][i]=-1;//做回溯处理准备
flag[i][j]=-1;
i--;//往上继续搜寻
}//endelse
}
}
}
}
（5）定义输出函数rintArray（int[][]flag），代码略（见代码清单）。
注明：
C语言程序的分析和上述类似，不在赘述。
四.具体实现及运行
4.1QueenMainl类的实现：
4.2QueenNR类：
实现了QueenMain类的非递归按钮功能
4.3QueenRS类：
实现了QueenMain类的递归按钮功能
4.4C语言程序：
5.总结
1.八皇后问题的求解计算量是特别大的，对于非递归算法，由于等价于穷搜法，他的时间复杂度约等于O（n！
），即是n的全排列。
虽然采用了去除分支的办法，但是对于总体来说，并不会减少太多运算，所以对于这种大型的计算。
还需要改进算法，并且需要硬件的支持。
本实验一般只能解决到12皇后，而且计算时间都比较长。
2.对于递归算法，效率比较低，但是便于理解，方便写代码。
3.对于两个算法的比较，都是用的回溯法，只是在具体的回溯方法上的区别。
4.八皇后问题在实际的生活中有很多的得到实用的地方，熟练地掌握八皇后问题的求解过程，能解决很多实际中的算法问题。
比如迷宫问题和地图着色问题，都可以应用相应的算法。
六.代码清单
6.1Java代码：
QueenMainl类：
packagecom.Listen;
importjava.awt.BorderLayout;
importjava.awt.CardLayout;
importjava.awt.Container;
importjava.awt.Font;
importjava.awt.GridLayout;
importjava.awt.event.ActionEvent;
importjava.awt.event.ActionListener;
importjavax.swing.BoxLayout;
importjavax.swing.JButton;
importjavax.swing.JFrame;
importjavax.swing.JLabel;
importjavax.swing.JPanel;
importjavax.swing.JScrollPane;
importjavax.swing.JTextArea;
importjavax.swing.JTextField;
publicclassQueenMainextendsJFrameimplementsActionListener{
JPaneltopPanel=newJPanel（）;
JButtonjb1,jb2,jb3;
JTextAreajta=null;
JScrollPanejscrollPane;
JLabelinputLabel;
JTextFieldinputNum;
JPanelpanel1,panel2;
Strings="请在上方输入4--10的数查看八皇后路径问题：
";
publicQueenMain（）{
setLayout（newBorderLayout（））;
//设置按钮
panel1=newJPanel（）;panel2=newJPanel（）;topPanel=newJPanel（）;
inputLabel=newJLabel（"请输入数字：
"）;
inputNum=newJTextField（25）;
panel1.add（inputLabel）;panel1.add（inputNum）;
//topPanel.setLayout（BoxLayout.Y_AXIS）;
topPanel.setLayout（newBoxLayout（topPanel,BoxLayout.Y_AXIS））;
topPanel.add（panel1）;
jb1=newJButton（"递归"）;
jb1.addActionListener（（ActionListener）this）;
jb2=newJButton（"非递归"）;
jb2.addActionListener（（ActionListener）this）;
jb3=newJButton（"清空"）;
jb3.addActionListener（（ActionListener）this）;
//添加按钮
panel2.setLayout（newGridLayout（1,3））;
panel2.add（jb1）;panel2.add（jb2）;panel2.add（jb3）;
topPanel.add（panel2）;
add（topPanel,BorderLayout.NORTH）;
jta=newJTextArea（10,15）;
jta.setText（s）;
jta.setEditable（false）;
jta.setTabSize（4）;
jta.setFont（newFont（"标楷体",Font.BOLD,16））;
jta.setLineWrap（true）;//激活自动换行功能
jta.setWrapStyleWord（true）;//激活断行不断字功能
jscrollPane=newJScrollPane（jta）;
add（jscrollPane,BorderLayout.CENTER）;
}
privatevoidQueenRs（）{
intn=Integer.parseInt（inputNum.getText（））;
QueenRSTqr=newQueenRST（n,this）;
}
privatevoidQueenNr（）{
intn=Integer.parseInt（inputNum.getText（））;
QueenRSTqr=newQueenRST（n,this）;
}
publicstaticvoidmain（String[]args）{
QueenMainapp=newQueenMain（）;
app.setTitle（"八皇后问题"）;
app.setVisible（true）;
app.setBounds（300,100,400,600）;
app.setDefaultCloseOperation（JFrame.EXIT_ON_CLOSE）;
}
publicvoidactionPerformed（ActionEvente）{
if（e.getSource（）==jb1）{
this.jta.setText（null）;
QueenRs（）;
升级会员 