八皇后问题（递归回溯法）

问题

在一个8*8的棋盘中，有八个皇后的棋子。这些棋子所放的位置的同一行，同一列和同一个斜线上不能出现另一个皇后，问有多少种摆放的方式。

思路

（1）先将一个皇后放到第一行的第一列

（2）然后将第二个皇后放到第二行的第一列，进行判断是否与其他皇后冲突，如果冲突，则移动到第二列…以此类推，直到不再冲突，如果全部列都冲突，则去除该行，前一行在进行移动列，寻找下一个不冲突的位置。

（3）然后根据前两个步骤继续放第三行，第四行，直到第八行，当找到第八行合适位置的时候，则找到一种正确的摆放方式。

（4）去除第八行的皇后，移动第七行的皇后向后移动一列，直到找到下一个与前面不冲突的地方或者到最后一列，如果找到下一个不冲突的地方，就将第八行的皇后放入再一次寻找，就这样一次一次进行循环递归回溯。一次列推下去。

（5）这样往复的进行循环，就能找到全部的摆放方式

其实这样说，可能也有些人不太理解，尤其是在回溯这方面，下面我们先看一下代码，然后我会在对此进行详细的分析。

代码

在这我们通过一个一维数组 arr[8] arr的（下标）表示第几行arr[i]=val ，val表第i个皇后，放在i行的val+1列。【这里从0开始】
代码如下：

public class Queue8 {
	
	int max = 8; //定义行
	int[] arry = new int[max];//定义数组
	static int count =0;//定义解法的个数
	public static void main(String[] args) {
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.println(count);
	}
	
	//编写一个方法，放置第n个皇后
	public void check(int n) {
		//如果以及摆放好
		if (n == max) {
			print();
			return;
		}
		//依次放入皇后。并判断是不是冲突
		for (int i = 0; i < arry.length; i++) {
			//将这个皇后放进第i列
			arry[n]=i;
			//判断冲突
			if (judge(n)) {
				//不冲突，就放入这个皇后
				check(n+1);
			}
			//如果冲突，就执行arry[n]=i，这样就相当于移动了一列
		}
	}
	
	//查看当前我们放置第n个皇后，就去检测该皇后和前面的是否冲突
	/**
	 * @param n :表示第几个皇后
	 * @return
	 * Math.abs():绝对值
	 */
	public boolean judge(int n) {
		for(int i=0;i<n;i++){
			//arry[i] == arry[n]表示n个皇后和前面的皇后是否在一列
			//Math.abs(n-i) == Math.abs(arry[n] - arry[i])表示判断第n个皇后和第i个皇后自爱一个斜线【行和列的差值是一样的】
			if (arry[i] == arry[n]||Math.abs(n-i) == Math.abs(arry[n] - arry[i])) {
				return false;
			}
		}
		return true;
	}
	
	//定义一个方法，将皇后摆放的位置输出
	public void print() {
		count++;
		for(int i =0;i<arry.length;i++){
			System.out.print(arry[i] + " ");
		}
		System.out.println();
	}
}

分析

我们对这段代码中最关键的部分进行了修改：

public void check(int n) {
    if (n == max) {
        print();
        return;
    }
    for (int i = 0; i < arry.length; i++) {
        System.out.println("这是"+n+"行，第"+i+"列");
        arry[n]=i;
        if (judge(n)) {
            check(n+1);
        }
    }
}

这样他在运行的时候，就会不断的输出第几行和第几列，这样我们通过debug的方式来探寻这是如何回溯的（请看下面这个图）：

我们可以发现当前4行都找到相应的皇后位置的时候，第5行的皇后这7列都不能使用，于是在n=5的时候就进行了一次回溯，我们可以发现在第5行之前，第4行是在第3列的，在回溯的时候，第4行将继续执行for循环，一次判断下面的列是否可行，终于在第7列的时候找到了，于是在递归运算第5行，回溯就是这样来的，这样可能还不是很清楚，下面，我们用图进行相应的展示：
首先把前4行放好：

我们可以看出，第五行的所有的列都于前面的皇后冲突，因此执行到这一步就没有在递归，而是进行了回溯：

在回溯的过程中，先回溯到了第4行，继续执行check(4)，继续执行for循环，于是第4行继续的向下一列移动，当移动到第7列的时候找到了相应的位置（不与前三个皇后冲突），但很可惜第5行依旧没有位置放皇后：

于是将继续回溯，这一次第4行已经到头了，所以这次n=4开始回溯，回溯到第3行，继续执行check(3)，于是第3列开始进行移动，找到相应的位置第6列，于是继续递归寻找第4行，找到了相应位置第1列，在此递归找第5行，找到了相应位置第3列

这样前5行就成功的找到了，这样依次的向下不断的递归回溯，最终就会得到相应的位置，在对这些位置进行统计就得到了相应的个数。