八皇后问题-递归回溯

1、八皇后问题介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

2、八皇后问题算法思路分析

（1）第一个皇后先放第一行第一列；

（2）第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适；

（3）继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解；

（4）当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到；

（5）然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤 。

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标表示第几行，即第几个皇后，arr[i] = val 表示第i+1个皇后，放在第i+1行的第val+1列

3、代码实现

（1）定义变量

//定义一个max表示一个有多少个皇后
	int max = 8;
	
	//定义数组，保存皇后防止位置结果
	//比如arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} 
	int[] array = new int[max];
	
	static int count =0;        //统计解法
	static int judgeCount = 0;  //统计调用check方法

（2）输出

	private void print(){
		count++;       //统计输出多少次，即就是多少种解法
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}

（3）查看当我们放置第n个皇后时，就去检测该皇后是否和前面已经摆放的皇后冲突

private boolean judge(int n){
		judgeCount++;          //统计调用check方法
		for(int i=0;i<n;i++){
			//array[i] == array[n]【判断是否在同一列】 
			//Math.abs(n-i) == Math.abs(array[n] - array[i])【斜线】      行差和列差是一样的          
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])){
				return false;
			}
		}
		return true;
	}

（4）放置第n个皇后

//特别注意：check是 每一次递归时，进入到check中都有for循环，因此会有回溯
	private void check(int n){
		if(n == max){
			//n=8表示在放第9个皇后，前8个皇后已经放好了
			print();          //打印结果
			return;
		}
		
		//依次放入皇后，并判断是否冲突
		for(int i=0;i<max;i++){
			//先把当前这个皇后，放到该行的第1列
			array[n] = i;
			
			//判断放第n个皇后到第i列时，是否冲突
			if(judge(n)){
				//不冲突，接着放第n+1个皇后，开始递归
				check(n+1);
			}
			//如果冲突，就继续执行array[n] = i;即将第n个皇后，放置在本行的后移的一个位置
		}
	}

（5）测试

public static void main(String[] args) {
		
		//测试
		Queue8 queue8 = new Queue8();
		queue8.check(0);        //放第一个皇后
		System.out.printf("一共有%d解法\n",count);
		System.out.printf("一共判断了%d次\n",judgeCount);
	}

这思路分析得好好消化理解。