本文共 2609 字，大约阅读时间需要 8 分钟。

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

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

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

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

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

、

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

完整代码：

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
   
    = 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();	}}
   

C++一维数组实现

#include 
   
    using namespace std;const int N = 8;int chess[N];int cnt = 0;bool isSafety(int row, int col){    //判断中上、左上、右上是否安全    int step = 1;    while (row - step >= 0)    {        if (chess[row - step] == col)        { //上            return false;        }        if (col - step >= 0 && chess[row - step] == (col - step))        { //左上            return false;        }        if (col + step < N && chess[row - step] == (col + step))        { //右上            return false;        }        step++;    }    return true;}void f(int row){    if (row > N - 1)    {        cnt++;        return;    }    for (int i = 0; i < N; i++)    {        chess[row] = i;        if (isSafety(row, i))        {            f(row + 1);        }    }}int main(){    f(0);    cout << cnt;    return 0;}
   

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