回溯法：

有这样一类题目，它们要求在相对问题的输入规模按照指数速度增长（或者更快）的域中，找出一个具有指定特性的元素。例如：在图顶点的所有排列中求一个哈密顿回路，在背包问题的一个实例中求其中最有价值的物品子集，等等。在原则上这类问题可以采用穷举法求解，穷举法通常需要我们求出所有的候选解，然后从中找出符合特征的元素。

而回溯法确实一个聪明的改变。回溯的思想是每次只构造解的一部分，如果这部分构造解可以进一步构造而不会违反约束条件，那么就接受对解的下一个分量所做的第一个合法解释，反之，则不需要对该分量继续选择，将该分量替换成它的下一个选择。

我们可以用树的模型来简化理解，而这棵树也被称为空间状态树。回溯法会逐层遍历，而一旦某个节点不符合约束，则直接放弃这个节点下的所有情况。

示意图

n皇后问题是在8皇后的基础上衍生而来的，我们以8皇后为例讲解：

8皇后问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种情况。

示意图

思路：8皇后问题就是最经典的回溯法问题，对检查[m, 1]...[m, n]，从中找出满足约束（即任意两个皇后都不能处于同一行、同一列或同一斜线上）的情况，递归执行，检查[m+1, 1]...[m+1, n]。每次注意回溯。

完整代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package parcel;

public class Main {
    static final int N = 8;
    static int chess[][] = new int[N][N];
    static int count = 0;
    public static void main(String[] args) {
        // 逐行
        f(0);
        System.out.println(count);
    }

    private static void f(int row) {
        if(row > N-1) {
            count++;
            print();
            return;
        }
        
        for(int i=0;i<N;i++) {
            //摆放每一行的皇后前，要清除这一行之前的摆放
            for(int j = 0; j < N; j++) {
            	chess[row][j] = 0;
            }
            chess[row][i] = 1;
            
            if( isSafety(row, i) ) {
                f(row+1);
            }
        }
    }

	private static boolean isSafety(int row, int col) {
        //判断中上、左上、右上是否安全
        int step=1;
        while(row - step >= 0){
            if(chess[row-step][col] == 1) {                //上
                return false;
            }
            if(col-step >= 0 && chess[row-step][col-step] == 1) {       //左上
                return false;
            }
            if(col+step < N && chess[row-step][col+step] == 1) {       //右上
                return false;
            }
            step++;
        }
        return true;
    }
	
    private static void print() {
		// TODO Auto-generated method stub
    	System.out.println("方案" + count + ":");
    	for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                System.out.print(chess[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
	}
}

8皇后问题采用这种方法虽然能解出来92，但是对于n皇后问题来说，这个程序显然有诸多不足，当执行15皇后的时候已经需要花费将近90s才能出来结果，效率非常低下。如果是专注于算法研究的话，推荐参考下面的文章。

8皇后以及N皇后算法探究，回溯算法的JAVA实现，递归方案

位运算解决八皇后问题