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

《实验报告回溯法求解N皇后问题(Java实现).doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、*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依次编号）五、算法实现对应这个数据结构的算法

4、实现如下：1.** 2. * 回溯法求解 N 皇后问题 3. * @author haolloyin 4. */ 5.public class N_Queens { 6.     7.    // 皇后的个数 8.    private int queensNum = 4; 9. 10.    // column[i] = j 表示第 i 列的第 j 行放置一个皇后 11.    private int[] queens = new int[queensNum + 1]; 12. 13.    // rowExists[i] = true 表示第 i 行有皇

5、后 14.    private boolean[] rowExists = new boolean[queensNum + 1]; 15. 16.    // a[i] = true 表示右高左低的第 i 条斜线有皇后 17.    private boolean[] a = new boolean[queensNum * 2]; 18. 19.    // b[i] = true 表示左高右低的第 i 条斜线有皇后 20.    private boolean[] b = new boolean[queensNum * 2]; 21.     22.  

6、  // 初始化变量 23.    private void init() { 24.        for (int i = 0; i < queensNum + 1; i++) { 25.            rowExists[i] = false; 26.        } 27.         28.        for(int i = 0; i < queensNum * 2; i++) { 29.            a[i] = b[i] = false; 30.        } 31.    } 32. 33.    // 判断该

7、位置是否已经存在一个皇后,存在则返回 true 34.    private boolean isExists(int row, int col) { 35.        return (rowExists[row] 

8、

9、 a[row + col - 1] 

10、

11、 b[queensNum + col - row]); 36.    } 37. 38.    // 主方法：测试放置皇后 39.    public void testing(int column) { 1. 2.        // 遍历每一行 3.        for (int row = 

12、1; row < queensNum + 1; ro