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

实验报告实验报告一、实验名称：一、实验名称：回溯法求解回溯法求解 N N 皇后问题（皇后问题（JavaJava 实现）实现）二、学习知识：二、学习知识：回溯法：回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。三、问题描述三、问题描述N N 皇后问题：皇后问题：在一个在一个 N*N N*N 的国际象棋棋盘中，怎样放置的国际象棋棋盘中，怎样放置 N N 个皇后才能使个皇后才能使 N N 个皇后之间个皇后之间不会互相有威胁而共同存在于棋局中，即在不会互相有威胁而共同存在于棋局中，即在 N*N N*N 个格子的棋盘中没有任何两个皇后是在个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。同一行、同一列、同一斜线上。深度优先遍历的典型案例。深度优先遍历的典型案例。四、求解思路四、求解思路1 1、求解思路：、求解思路：最容易想到的方法就是有序地从第最容易想到的方法就是有序地从第 1 1 列的第列的第 1 1 行开始，尝试放上一个行开始，尝试放上一个皇后，然后再尝试第皇后，然后再尝试第 2 2 列的第几行能够放上一个皇后，如果第列的第几行能够放上一个皇后，如果第 2 2 列也放置成功，那么就列也放置成功，那么就继续放置第继续放置第 3 3 列，如果此时第列，如果此时第3 3 列没有一行可以放置一个皇后，说明目前为止的尝试是列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 2 步），将上一步步），将上一步（第（第 2 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍步）所放置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。历加上回溯，就可以慢慢地逼近最终解了。2 2、需要解决的问题：、需要解决的问题：如何表示一个如何表示一个 N*N N*N 方格棋盘能够更有效怎样测试当前所走的方格棋盘能够更有效怎样测试当前所走的试探路径是否符合要求这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结试探路径是否符合要求这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结构有利于简化编程求解问题的难度。构有利于简化编程求解问题的难度。3 3、我们使用以下的数据结构：、我们使用以下的数据结构：int columncol=int columncol=rowrow表示第表示第 col col列的第列的第rowrow 行放置一个皇后行放置一个皇后boolean rowExistsi=trueboolean rowExistsi=true表示第表示第 i i 行有皇后行有皇后booleanboolean aiai=truetrue表示右高左低的第表示右高左低的第 i i 条斜线有皇后条斜线有皇后（按（按 顺序从顺序从 11 2*N2*N-1-1依次编号）依次编号）boolean bi=trueboolean bi=true 表示左高右低的第表示左高右低的第 i i 条斜线有皇后（按条斜线有皇后（按 顺序从顺序从 1 2*N-11 2*N-1依次编号）依次编号）五、算法实现五、算法实现对应这个数据结构的算法实现如下：对应这个数据结构的算法实现如下：1.1.2.2.3.3.4.4.*回溯法求解回溯法求解N N皇后问题皇后问题*authorauthorhaolloyinhaolloyin*/*/5.5./6.6.publicpublicclassclassN_QueensN_Queens7.7.1.2.3.(1,8)(1,8)(2,2)(2,2)(3,4)(3,4)4.(1,8)(1,8)(2,2)(2,2)(3,5)(3,5)5.(1,8)(1,8)(2,3)(2,3)(3,1)(3,1)6.(1,8)(1,8)(2,4)(2,4)(3,1)(3,1)当当 N=4N=4 时，求解结果如下：时，求解结果如下：(4,1)(4,1)(5,7)(5,7)(6,5)(6,5)(7,3)(7,3)(8,6)(8,6)(4,3)(4,3)(5,1)(5,1)(6,7)(6,7)(7,4)(7,4)(8,6)(8,6)(4,6)(4,6)(5,2)(5,2)(6,5)(6,5)(7,7)(7,7)(8,4)(8,4)(4,3)(4,3)(5,6)(5,6)(6,2)(6,2)(7,7)(7,7)(8,5)(8,5)1.(1,2)(1,2)(2,4)(2,4)(3,1)(3,1)(4,3)(4,3)2.(1,3)(1,3)(2,1)(2,1)(3,4)(3,4)(4,2)(4,2)】七、实验小结：七、实验小结：1 1、根据问题选择恰当的数据结构非常重要，就像上面、根据问题选择恰当的数据结构非常重要，就像上面 a a、b b 标志数组来表示每一条标志数组来表示每一条斜线的编号顺序以及方向都相当重要。看书的时候也是费了些时间来理解的，呼另外，斜线的编号顺序以及方向都相当重要。看书的时候也是费了些时间来理解的，呼另外，queens col=rowqueens col=row数组只是用了一维而不是二维来表示纵横交错的方格棋盘上特定位数组只是用了一维而不是二维来表示纵横交错的方格棋盘上特定位置是否有皇后也是比较经济而有意思的。置是否有皇后也是比较经济而有意思的。2 2、正确运用、组织所确定的数据结构到算法的实现逻辑中也是很重要的，就像代码中、正确运用、组织所确定的数据结构到算法的实现逻辑中也是很重要的，就像代码中的的 isExists(int row,int col)isExists(int row,int col)方法内的方法内的(rowExistsrow|arow+col-1|(rowExistsrow|arow+col-1|bqueensNum+col-row)bqueensNum+col-row)就是很明确的理解了尝试放置皇后的位置的就是很明确的理解了尝试放置皇后的位置的 x x，y y 坐标与斜坐标与斜线之间的数值关系，才使得算法得以正确执行。当然，对于斜线的编号、顺序也是相当重线之间的数值关系，才使得算法得以正确执行。当然，对于斜线的编号、顺序也是相当重要的。要的。