`
huntfor
  • 浏览: 201075 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

回溯算法之N皇后问题(java实现)

 
阅读更多

逗逼室友说了:

回溯是思想,深搜是本质,递归是实现。

 在理!

 

虽不是第一次接触递归,但是确实实实在在的第一次接触回溯。是琢磨了蛮长时间才编完并测试通过的代码,继承本菜鸟一贯简单的作风,希望能给不太熟悉回溯思想的各位看官一点启发。但是大家在学习回溯时,还是需要明白递归的思想的。不废话

 

八皇后问题是回溯思想的经典题目,就好像由汉诺塔引入递归一样。具体的要求就不再啰嗦了,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时,打印出来的结果是 

4 //hash从1开始计数,第0位没有意义,hash[row] = column 表示row号皇后放在第row行,第column列
[-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

 

分享到:
评论
1 楼 hthhit 2014-08-31  

相关推荐

    n后问题回溯算法 java

    总结起来,n皇后问题通过回溯算法在Java中的实现,不仅锻炼了我们的逻辑思维能力,也让我们更好地理解了递归和回溯这两种重要的编程技巧。同时,这个问题也为我们提供了一个在有限搜索空间中寻找解的有效方法,这在...

    回溯法解决N皇后问题 Java代码实现

    通过GUI实现N皇后问题的动态演示,可以使用Java Swing或JavaFX库创建用户界面,展示皇后在棋盘上的位置,并允许用户选择不同数量的皇后进行演示。这样,用户可以直观地看到回溯法如何在棋盘上逐步尝试和撤销皇后的...

    用回溯法实现n皇后问题(java源码)

    算法分析与设计 用回溯法实现n皇后问题(java源码)

    回溯法实现N皇后问题

    总结,通过回溯法解决N皇后问题,需要理解回溯法的基本思想,实现冲突检测和回溯策略,并能够将算法结果通过Java Swing界面展示出来。提供的压缩包文件可能包含了实现这个功能的源代码,可以进一步学习和理解如何将...

    NQueen N皇后问题java实现

    总之,N皇后问题的Java实现是一个涉及回溯算法、面向对象编程和图形化界面设计的综合性实例,对于提升编程技能和理解算法有着显著的帮助。通过学习和实践这样的项目,开发者不仅可以掌握基本的编程技巧,还能深入...

    用栈求解n皇后问题 ,经典的回溯算法问题

    n 皇后问题是一道经典的回溯算法问题,其目标是在一个 � × � n×n 的棋盘上放置 � n 个皇后,使得任意两个皇后都不能在同一行、同一列或同一斜线上。 栈可以用来辅助实现回溯算法,本质上就是手动维护了递归...

    Java实现N皇后问题的算法

    这是一个用Java实现的关于N皇后问题的算法 其中包括回溯和迭代两种算法

    Java编写的N皇后问题

    Java编写的N皇后问题是一个经典的计算机编程挑战,它涉及到回溯算法、递归以及问题解决策略。N皇后问题要求在N×N的棋盘上放置N个皇后,使得每个皇后都不能在同一行、同一列或同一斜线上。这个问题的解决方案数量...

    算法用JAVA写的n皇后问题

    **压缩包子文件的文件名称列表**:“n皇后问题”可能是包含Java源代码的文件,可能包含一个主程序类和一个或多个辅助类,用于实现n皇后的解决方案和图形用户界面(GUI)展示。 总的来说,解决n皇后问题不仅可以锻炼...

    算法实验(java快速排序。归并排序,分治算法,回溯算法,n后问题) C语言

    本实验包涵盖了五种重要的算法,包括Java实现的快速排序、归并排序,以及分治算法、回溯算法和N皇后问题的C语言解决方案。下面将对这些算法进行详细介绍。 1. **快速排序**:快速排序是一种高效的排序算法,由C.A.R...

    分支限界法解决N皇后问题

    使用分支限界法解决N皇后问题。因为是广度优先,而且占用比较多的额外空间,所以并不是解N皇后问题的很好的算法,主要是理解分支限界法的使用。

    回溯算法-N后问题和符号三角形java算法源程序

    在给定的实验内容中,有两个基于回溯算法的Java程序,分别是“符号三角形问题”和“N后问题”。 1. 符号三角形问题: 这个问题的目标是找到所有合法的符号排列方式,使得在一个半边长度为n的三角形中,每行的“+”...

    n皇后问题(java含界面)

    总的来说,这个项目结合了基本的计算机科学概念,如回溯算法,以及实际的编程技能,如Java GUI编程,提供了一个直观的学习和演示n皇后问题的平台。读者可以通过研究和修改此代码,加深对这两个领域的理解,并锻炼...

    N皇后问题的Java程序实现及分析.pdf

    因此,本文尝试使用简易的回溯算法在Java语言环境下实现N皇后问题的求解。 在Java程序中,我们使用了三个数组来描述皇后的位置:列方向(col)、斜线方向(slash)和反斜线方向(blash)。每个皇后的四个作业方向...

    回溯算法-N后问题和符号三角形java算法源程序.pdf

    在给定的文件中,有两个具体的回溯算法应用实例:符号三角形问题和N皇后问题。 1. 符号三角形问题: 这个问题的目标是构建一个由"+"和"-"符号组成的三角形,使得每行的"+"符号数量等于三角形的半边长,并且 "+" ...

    N皇后问题 java图形界面实现.doc

    总之,这个Java程序通过图形界面展示了如何用回溯法解决N皇后问题,用户可以通过操作按钮动态观察解的生成过程,加深对回溯算法的理解。在编程实践中,这样的可视化工具对于复杂问题的调试和解释同样具有很高的价值...

    五大常用算法——回溯算法详解及经典例题,算法数据结构 五大常用算法

    在Java语言中,可以使用回溯算法来解决皇后问题。例如,在NQueensII类中,我们可以使用回溯算法来解决皇后问题。首先,我们需要初始化皇后个数N和当前解x[]。然后,我们可以使用递归函数backTrace来实现回溯算法。在...

    N皇后问题,带界面的 java版

    在Java中,实现N皇后问题的回溯算法通常会用到二维数组来表示棋盘状态,以及递归函数来遍历所有可能的摆放。每个元素在数组中表示对应位置是否有皇后,递归函数会根据当前行数和已放置的皇后数量来进行判断。 其次...

    n皇后问题(队列分支限界法)

    在C++编程环境下实现n皇后问题,首先需要理解如何构建问题的搜索树。每个节点代表棋盘上的一个状态,即在当前行放置皇后的可能性。每个节点有两个子节点,分别表示在当前行放置皇后后,下一行的两种可能布局:一是...

Global site tag (gtag.js) - Google Analytics