回溯算法之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