【Java】八皇后问题（递归回溯/深搜）
回溯法
回溯法，又被称为“试探法”。解决问题时，每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯法。
所谓深搜（也叫回溯法）就是采用的是“一直往下走，走不通了就掉头，换一条路再往下走”
总结来说就是递归的枚举
深度优先搜索的实质就是穷举，按照一定的顺序和规则不断地去尝试，直到找到问题的解。
对于一个问题的第一个状态叫做初始状态，最后要求的状态叫做目的状态。
在搜索的过程中，对当前状态进行检测，如果当前状态满足目的状态，那么这个当前状态就是结果之一。
回溯VS递归
很多人认为回溯和递归是一样的，其实不然。在回溯法中可以看到有递归的身影，但是两者是有区别的。
回溯法从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发现当前情况根本不可能存在，就停止后续的所有工作，返回上一步进行新的尝试。
递归是从问题的结果出发，例如求 n!，要想知道 n！的结果，就需要知道 n*(n-1)! 的结果，而要想知道 (n-1)! 结果，就需要提前知道 (n-1)*(n-2)!。这样不断地向自己提问，不断地调用自己的思想就是递归。
回溯和递归唯一的联系就是，回溯法可以用递归思想实现。
参考博客1——回溯法（八皇后问题）及C语言实现
参考博客2——深搜（总结+例题）
问题
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法
思路
1)第一个皇后先放第一行第一列
2)第二个皇后放在第二行第一列、然后判断是否OK，如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
3)继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
4)当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
5)然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3,4的步骤
说明:
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题.
arr[8]={0,4,7,5,2,6,1,3}
//对应 arr下标表示第几行，即第几个皇后， ar[i]=val ,
// val表示第i+1个皇后，放在第i+1行的第val+1列
代码
package 八皇后;
public class Queen8 {
//定义一个max表示共有多少个皇后
int max = 8;
//定义数组array，保存皇后放置位置的结果
//eg:array[i] = x,下标i表示第i+1个皇后,也就是第i+1行，x表示棋盘的第x+1列
int array[] = new int[max];
//统计八皇后有多少种摆法【静态方法中只能调用静态方法或属性】
static int count=0;
public static void main(String[] args) {
// TODO Auto-generated method stub
Queen8 queen8 = new Queen8();
queen8.check(0);
System.out.println("一共有"+count+"种摆法");
}
//放置第n个皇后
//注意：check是每一次递归时，进入到check都有for(int i=0;i<max;i++),因此会有回溯
private void check(int n) {
if(n==max) {
print();
count++;
return ;
}
//依次放入皇后，并判断是否冲突
for(int i=0;i<max;i++) {
//先把当前这个皇后n放入该行的第一列
array[n] = i;
//判断当放置第n个皇后到i列时是否冲突
if(judge(n)) {
//接着放第n+1个皇后（进入下一行）
check(n+1);
}
//如果冲突，就继续循环，即将第n个皇后放置到下一列【本行后移一个位置】
}
}
//查看当我们放置第n个皇后时，就去检测该皇后是否和前面放置的皇后有冲突
private boolean judge(int n) { //n表示第n个皇后
for(int i=0;i<n;i++) {
/**
* 说明：
* 1.array[i]==array[n]表示判断第n个皇后和前面的n-1个皇后是否在同一列或同一斜线
* 2.Math.abs(n-i)==Math.abs(array[n]-array[i])
* 判断两个皇后是否处在同一斜线，此斜线的斜率为1或-1，可以想一下数学中求斜率的方法
*/
if(array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])) {
return false;
}
}
return true;
}
//将皇后放置的位置输出
private void print() {
for(int i=0;i<max;i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
}