实验报告：回溯法求解N皇后问题(Java实现)(共4页).doc

《实验报告：回溯法求解N皇后问题(Java实现)(共4页).doc》由会员分享，可在线阅读，更多相关《实验报告：回溯法求解N皇后问题(Java实现)(共4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验报告一、实验名称：回溯法求解N皇后问题（Java实现）二、学习知识：回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。三、问题描述N皇后问题：在一个 N * N 的国际象棋棋盘中，怎样放置 N 个皇后才能使 N 个皇后之间不会互相有威胁而共同存在于棋

2、局中，即在 N * N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。深度优先遍历的典型案例。四、求解思路1、求解思路：最容易想到的方法就是有序地从第 1 列的第 1 行开始，尝试放上一个皇后，然后再尝试第 2 列的第几行能够放上一个皇后，如果第 2 列也放置成功，那么就继续放置第 3 列，如果此时第3 列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。2、需要解决的问题：如何表示一

3、个 N * N 方格棋盘能够更有效？怎样测试当前所走的试探路径是否符合要求？这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结构有利于简化编程求解问题的难度。3、我们使用以下的数据结构：int columncol =row 表示第 col列的第row 行放置一个皇后boolean rowExistsi = true 表示第 i 行有皇后boolean ai = true 表示右高左低的第 i 条斜线有皇后（按 顺序从1 2*N -1 依次编号）boolean bi = true 表示左高右低的第 i 条斜线有皇后（按 顺序从1 2*N -1 依次编号）五、算法实现对应这个数据结构的算法

4、实现如下：1. * 2. *回溯法求解N皇后问题 3. *authorhaolloyin 4. */5. publicclassN_Queens 6. 7. /皇后的个数 8. privateintqueensNum=4; 9. 10. /columni=j表示第i列的第j行放置一个皇后 11. privateintqueens=newintqueensNum+1; 12. 13. /rowExistsi=true表示第i行有皇后 14. privatebooleanrowExists=newbooleanqueensNum+1; 15. 16. /ai=true表示右高左低的第i条斜线有皇后

5、 17. privatebooleana=newbooleanqueensNum*2; 18. 19. /bi=true表示左高右低的第i条斜线有皇后 20. privatebooleanb=newbooleanqueensNum*2; 21. 22. /初始化变量 23. privatevoidinit() 24. for(inti=0;iqueensNum+1;i+) 25. rowExistsi=false; 26. 27. 28. for(inti=0;iqueensNum*2;i+) 29. ai=bi=false; 30. 31. 32. 33. /判断该位置是否已经存在一个皇后,

6、存在则返回true 34. privatebooleanisExists(introw,intcol) 35. return(rowExistsrow|arow+col-1|bqueensNum+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

7、. queenscolumn=row; 47. /设置以第row行第column列为交叉点的斜线不可放置皇后 48. rowExistsrow=arow+column-1=bqueensNum+column-row=true; 49. 50. /全部尝试过，打印 51. if(column=queensNum) 52. for(intcol=1;col=queensNum;col+) 53. System.out.print(+col+,+queenscol+); 54. 55. System.out.println(); 56. else 57. /放置下一列的皇后 58. testing(

8、column+1); 59. 60. /撤销上一步所放置的皇后，即回溯 61. rowExistsrow=arow+column-1=bqueensNum+column-row=false; 62. 63. 64. 65. 66. /测试 67. publicstaticvoidmain(Stringargs) 68. N_Queensqueen=newN_Queens(); 69. queen.init(); 70. /从第1列开始求解 71. queen.testing(1); 72. 73. 六、运行结果当 N = 8 时，求解结果如下（注：横坐标为 列数， 纵坐标为 行数）：(1,1)

9、(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)(

10、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(int row, int col) 方法内的 (rowExistsrow | arow + col - 1 | bqueensNum + col - row) 就是很明确的理解了尝试放置皇后的位置的 x ，y 坐标与斜线之间的数值关系，才使得算法得以正确执行。当然，对于斜线的编号、顺序也是相当重要的。专心-专注-专业