逗逼室友说了:
在理!
虽不是第一次接触递归,但是确实实实在在的第一次接触回溯。是琢磨了蛮长时间才编完并测试通过的代码,继承本菜鸟一贯简单的作风,希望能给不太熟悉回溯思想的各位看官一点启发。但是大家在学习回溯时,还是需要明白递归的思想的。不废话
八皇后问题是回溯思想的经典题目,就好像由汉诺塔引入递归一样。具体的要求就不再啰嗦了,google一下一大片(这里给出leetcode中的n皇后的题目大意http://oj.leetcode.com/problems/n-queens/)题目大意:8*8棋盘,8个皇后,怎么放才能保证这几个皇后和谐相处,互不干涉。
算法思想:(为了通俗易懂,本文从1开始计数)
0. 将皇后编号1,2,3,4,5,6,7,8,并且排号为i的皇后,放在第i行
1. 将1号皇后放在第1行(1号皇后是肯定不会冲突的)
2. 1号皇后放好之后,放2号皇后(3号及以后的类似),从第2行第1列开始检测,不冲突就可以落子; 当本行没有合法的位置时,说明上一行皇后放的位置不好,则撤销上一行皇后的位置,并重新摆放(所谓回溯)
3. 如果8个皇后放好之后,按照上文逻辑该放8 + 1 号皇后了,但是已经放完了,所以将摆放结果打印。再重新摆放第8行(很多人不理解这里为什么还回溯)
回溯发生的位置:
1. 皇后i的摆放位置,使得皇后i+1怎么放都不行,即这条路走不通了,回溯(重新摆放皇后i的位置,使得i+1可以摆放,就好像迷宫遇到墙了,要往回走)
2. 8个皇后都摆放完毕,打印出了摆放结果,回溯(就好像迷宫找到了一件宝物(一共需要集齐n件),你找到之后还要回头找另外几件,直到你集齐或者把所有的路都走了(DFS))
算法小结:
1. 对第 i 个皇后,从第i行第1列到第8列,逐个查找,看是否有不冲突的安全位置(特殊情况,皇后1)
2. 如果冲突了,就检查下一列,直到安全的位置,找到最后都不安全,回溯(去找合法序列);
3. 最后一个皇后摆放成功,回溯(去找别的可能性)
public class NQueens { private static int queenNum;//皇后的个数 private static int[] hash;//下标表示i号皇后(皇后i放在第i行)value表示放的列号 private static int count = 0;//合法摆放方式的个数 public void placeQueen(int m) { if (m > queenNum) {//如果摆到了n+1行了,说明前n行都是不冲突的,合法的 count++; System.out.println(Arrays.toString(hash)); //打印合法的摆放结果 for(int i = 1; i <= queenNum; i++){ int column = hash[i];//hash值表示皇后i所在的列号 for(int j = 1; j <= queenNum ;j++){ if(j!= column){ System.out.print("* "); }else{ System.out.print("Q "); } } System.out.println(); } return; } for (int i = 1; i <= queenNum; i++) { //check the column is conflict with former ones or not //if so, check the next column until find a non-conflict column //or until the last column ,return; if (isConfilct(m, i)) { continue; } else {//如果检测到第i列不冲突,是安全的, hash[m] = i;//将皇后m放在第i列 placeQueen(m + 1);//再放皇后m+1, //如果皇后m+1放完并返回了 //两种可能: //1:冲突,返回了 //2.一直将所有的皇后全部放完并安全返回了 //将皇后m回溯,探索新的可能或者安全的位置 hash[m] = -1; //其实这里没必要将m重新赋值的,因为检测到下一个 //安全位置的时候会把hash[m]覆盖掉的 //但是为了更好的体现“回溯”的思想,在这里画蛇添足了 } } } /** * 检测冲突 * @param index * 表示行号 * @param hash * 值表示列号 * @return */ private boolean isConfilct(int row, int column) { if(row == 1){//第1行永远不会冲突 return false; } //只需要保证与那些已经就位的皇后不冲突即可 for (int i = 1; i < row; i++) { if (hash[i] == column || ( column - row) == (hash[i] - i) || (row - column)== (i-hash[i]) || (row + column) == (hash[i] + i)) { return true; } } return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); queenNum = sc.nextInt(); hash = new int[queenNum + 1]; for (int i = 0; i < hash.length; hash[i++] = -1);//初始化棋盘 NQueens demo = new NQueens(); demo.placeQueen(1); System.out.println(count); } }
我取的queenNum = 4时,打印出来的结果是
[-1, 2, 4, 1, 3] //比如hash[1]= 2表示1号皇后在第1行第2列
* Q * *
* * * Q
Q * * *
* * Q *
[-1, 3, 1, 4, 2]
* * Q *
Q * * *
* * * Q
* Q * *
2
相关推荐
总结起来,n皇后问题通过回溯算法在Java中的实现,不仅锻炼了我们的逻辑思维能力,也让我们更好地理解了递归和回溯这两种重要的编程技巧。同时,这个问题也为我们提供了一个在有限搜索空间中寻找解的有效方法,这在...
通过GUI实现N皇后问题的动态演示,可以使用Java Swing或JavaFX库创建用户界面,展示皇后在棋盘上的位置,并允许用户选择不同数量的皇后进行演示。这样,用户可以直观地看到回溯法如何在棋盘上逐步尝试和撤销皇后的...
算法分析与设计 用回溯法实现n皇后问题(java源码)
总结,通过回溯法解决N皇后问题,需要理解回溯法的基本思想,实现冲突检测和回溯策略,并能够将算法结果通过Java Swing界面展示出来。提供的压缩包文件可能包含了实现这个功能的源代码,可以进一步学习和理解如何将...
总之,N皇后问题的Java实现是一个涉及回溯算法、面向对象编程和图形化界面设计的综合性实例,对于提升编程技能和理解算法有着显著的帮助。通过学习和实践这样的项目,开发者不仅可以掌握基本的编程技巧,还能深入...
n 皇后问题是一道经典的回溯算法问题,其目标是在一个 � × � n×n 的棋盘上放置 � n 个皇后,使得任意两个皇后都不能在同一行、同一列或同一斜线上。 栈可以用来辅助实现回溯算法,本质上就是手动维护了递归...
这是一个用Java实现的关于N皇后问题的算法 其中包括回溯和迭代两种算法
Java编写的N皇后问题是一个经典的计算机编程挑战,它涉及到回溯算法、递归以及问题解决策略。N皇后问题要求在N×N的棋盘上放置N个皇后,使得每个皇后都不能在同一行、同一列或同一斜线上。这个问题的解决方案数量...
**压缩包子文件的文件名称列表**:“n皇后问题”可能是包含Java源代码的文件,可能包含一个主程序类和一个或多个辅助类,用于实现n皇后的解决方案和图形用户界面(GUI)展示。 总的来说,解决n皇后问题不仅可以锻炼...
本实验包涵盖了五种重要的算法,包括Java实现的快速排序、归并排序,以及分治算法、回溯算法和N皇后问题的C语言解决方案。下面将对这些算法进行详细介绍。 1. **快速排序**:快速排序是一种高效的排序算法,由C.A.R...
使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。
在给定的实验内容中,有两个基于回溯算法的Java程序,分别是“符号三角形问题”和“N后问题”。 1. 符号三角形问题: 这个问题的目标是找到所有合法的符号排列方式,使得在一个半边长度为n的三角形中,每行的“+”...
总的来说,这个项目结合了基本的计算机科学概念,如回溯算法,以及实际的编程技能,如Java GUI编程,提供了一个直观的学习和演示n皇后问题的平台。读者可以通过研究和修改此代码,加深对这两个领域的理解,并锻炼...
因此,本文尝试使用简易的回溯算法在Java语言环境下实现N皇后问题的求解。 在Java程序中,我们使用了三个数组来描述皇后的位置:列方向(col)、斜线方向(slash)和反斜线方向(blash)。每个皇后的四个作业方向...
在给定的文件中,有两个具体的回溯算法应用实例:符号三角形问题和N皇后问题。 1. 符号三角形问题: 这个问题的目标是构建一个由"+"和"-"符号组成的三角形,使得每行的"+"符号数量等于三角形的半边长,并且 "+" ...
总之,这个Java程序通过图形界面展示了如何用回溯法解决N皇后问题,用户可以通过操作按钮动态观察解的生成过程,加深对回溯算法的理解。在编程实践中,这样的可视化工具对于复杂问题的调试和解释同样具有很高的价值...
在Java语言中,可以使用回溯算法来解决皇后问题。例如,在NQueensII类中,我们可以使用回溯算法来解决皇后问题。首先,我们需要初始化皇后个数N和当前解x[]。然后,我们可以使用递归函数backTrace来实现回溯算法。在...
在Java中,实现N皇后问题的回溯算法通常会用到二维数组来表示棋盘状态,以及递归函数来遍历所有可能的摆放。每个元素在数组中表示对应位置是否有皇后,递归函数会根据当前行数和已放置的皇后数量来进行判断。 其次...
在C++编程环境下实现n皇后问题,首先需要理解如何构建问题的搜索树。每个节点代表棋盘上的一个状态,即在当前行放置皇后的可能性。每个节点有两个子节点,分别表示在当前行放置皇后后,下一行的两种可能布局:一是...