搜索
实验报告一、实验名称：回溯法求解N皇后问题（Java实现）二、学习知识：回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。三、问题描述N皇后问题：在一个N*N的国际象棋棋盘中，怎样放置N个皇后才能使N个皇后之间不会互相有威胁而共同存在于棋局中，即在N*N个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。深度优先遍历的典型案例。四、求解思路1、求解思路：最容易想到的方法就是有序地从第1列的第1行开始，尝试放上一个皇后，然后再尝试第2列的第几行能够放上一个皇后，如果第2列也放置成功，那么就继续放置第3列，如果此时第3列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第2步），将上一步（第2步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。2、需要解决的问题：如何表示一个N*N方格棋盘能够更有效？怎样测试当前所走的试探路径是否符合要求？这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结构有利于简化编程求解问题的难度。3、我们使用以下的数据结构：intcolumn[col]=row表示第col列的第row行放置一个皇后booleanrowExists[i]=true表示第i行有皇后booleana[i]=true表示右高左低的第i条斜线有皇后（按→↓顺序从1~2*N-1依次编号）booleanb[i]=true表示左高右低的第i条斜线有皇后（按→↑顺序从1~2*N-1依次编号）五、算法实现对应这个数据结构的算法实现如下：1.**2.*回溯法求解N皇后问题3.*@authorhaolloyin4.*/5.publicclassN_Queens{6.7.//皇后的个数8.privateintqueensNum=4;9.10.//column[i]=j表示第i列的第j行放置一个皇后11.privateint[]queens=newint[queensNum+1];12.13.//rowExists[i]=true表示第i行有皇后14.privateboolean[]rowExists=newboolean[queensNum+1];15.16.//a[i]=true表示右高左低的第i条斜线有皇后17.privateboolean[]a=newboolean[queensNum*2];18.19.//b[i]=true表示左高右低的第i条斜线有皇后20.privateboolean[]b=newboolean[queensNum*2];21.22.//初始化变量23.privatevoidinit(){24.for(inti=0;iqueensNum+1;i++){25.rowExists[i]=false;26.}27.28.for(inti=0;iqueensNum*2;i++){29.a[i]=b[i]=false;30.}31.}32.33.//判断该位置是否已经存在一个皇后,存在则返回true34.privatebooleanisExists(introw,intcol){35.return(rowExists[row]||a[row+col-1]||b[queensNum+col-row]);36.}37.38.//主方法：测试放置皇后39.publicvoidtesting(intcolumn){40.41.//遍历每一行42.for(introw=1;rowqueensNum+1;row++){43.//如果第row行第column列可以放置皇后44.if(!isExists(row,column)){45.//设置第row行第column列有皇后46.queens[column]=row;47.//设置以第row行第column列为交叉点的斜线不可放置皇后48.rowExists[row]=a[row+column-1]=b[queensNum+column-row]=true;49.50.//全部尝试过，打印51.if(column==queensNum){52.for(intcol=1;col=queensNum;col++){53.System.out.print((+col+,+queens[col]+));54.}55.System.out.println();56.}else{57.//放置下一列的皇后58.testing(column+1);59.}60.//撤销上一步所放置的皇后，即回溯61.rowExists[row]=a[row+column-1]=b[queensNum+column-row]=false;62.}63.}64.}65.66.//测试67.publicstaticvoidmain(String[]args){68.N_Queensqueen=newN_Queens();69.queen.init();70.//从第1列开始求解71.queen.testing(1);72.}73.}六、运行结果当N=8时，求解结果如下（注：横坐标为列数，纵坐标为行数）：(1,1)(2,5)(3,8)(4,6)(5,3)(6,7)(7,2)(8,4)1.(1,1)(2,6)(3,8)(4,3)(5,7)(6,4)(7,2)(8,5)2.(1,1)(2,7)(3,4)(4,6)(5,8)(6,2)(7,5)(8,3)3.......4.......5.(1,8)(2,2)(3,4)(4,1)(5,7)(6,5)(7,3)(8,6)6.(1,8)(2,2)(3,5)(4,3)(5,1)(6,7)(7,4)(8,6)7.(1,8)(2,3)(3,1)(4,6)(5,2)(6,5)(7,7)(8,4)8.(1,8)(2,4)(3,1)(4,3)(5,6)(6,2)(7,7)(8,5)当N=4时，求解结果如下：1.(1,2)(2,4)(3,1)(4,3)2.(1,3)(2,1)(3,4)(4,2)七、实验小结：1、根据问题选择恰当的数据结构非常重要，就像上面a、b标志数组来表示每一条斜线的编号顺序以及方向都相当重要。看书的时候也是费了些时间来理解的，呼…另外，queens[col]=row数组只是用了一维而不是二维来表示纵横交错的方格棋盘上特定位置是否有皇后也是比较经济而有意思的。2、正确运用、组织所确定的数据结构到算法的实现逻辑中也是很重要的，就像代码中的isExists(introw,intcol)方法内的(rowExists[row]||a[row+col-1]||b[queensNum+col-row])就是很明确的理解了尝试放置皇后的位置的x，y坐标与斜线之间的数值关系，才使得算法得以正确执行。当然，对于斜线的编号、顺序也是相当重要的。