摘要
回溯本质就是前进不成，就后退一步换另外一条路继续前进，直到到达目的地。它在树结构、图结构中都有应用。本文通过解决八皇后的问题来了解回溯的思想。
回溯可以理解成在岔路口选择不同的道路，直到达到目的地。它的每一步都会选择一条路出发，能前进都前进，不能前进就退到上一步，选择其他的路走，直到走完所有路或者到达目的地为止。不能前进就退到上一步的过程就是回溯。
典型的回溯应用有树、图的深度优先搜索、八皇后问题或者走迷宫等等。这里以八皇后的问题为例，来看一下回溯。
八皇后问题是在一个8X8的棋牌中放8个皇后，使其不能相互攻击，也就是任意两个皇后不能在同一行、同一列、同一斜率上。
解决思路
解决八皇后问题，有这样几种思路，第一种就是暴力破解，从64个格子中选择出任意的8个格子摆放皇后，然后检查摆法是否合适，检查完每一种，需要检查的次数非常的大。
那么，可以根据题意来减少暴力破解的次数，因为任意两个皇后不能在同一行，也就是每一行只能放一个皇后，所以摆放的次数就减少成 88 次。虽然次数减少了很多，但是次数还是比较多的。
最后一个思路就是用回溯法来处理，每次摆放皇后后，就将不能被摆放的格子给剔除掉，这种操作叫做剪切。当到了无法摆放，并且皇后也没有摆放完时，就退回到最初摆放第一个皇后的位置，排除这个位置，从下一个位置开始，这个操作叫做回溯。所以这个思路是回溯+剪切。
实现代码
首先创建一个类，并定义数组，保存皇后摆放的位置 cols，cols 数组的索引对应的是第几行，从 0 开始，索引对应的元素是第几列，从 0 开始，也就是存储的数据是第几行中的第几列摆放了皇后，其次还定义一个属性 ways 记录有多少种摆法：
public class Queens {
/**
* 数组索引是行号，数组元素是列号
*/
int[] cols;
/**
* 一共有多少种排法
*/
int ways;
}
接下来创建摆放八皇后的函数，placeQueens()，函数中传递参数 n，表示摆放多少个皇后，让函数适应更多的同类场景，所以摆放八皇后就是 placeQueens(8)，代码实现如下：
void placeQueens(int n) {
if (n < 1) return;
cols = new int[n];
place(0);
System.out.println(n + "皇后一共有" + ways + "种摆法");
}
函数中先定义了 cols 数组的大小，有多少个皇后，就创建多少空间的数组。place() 函数执行的是摆放皇后的过程，传递的参数表示从第几行开始摆放，具体代码如下：
void place(int row) {
// 终止指令
if (row == cols.length) {
ways ++;
return;
}
for (int col = 0; col < cols.length; col++) {
if (isValid(row, col)) {
cols[row] = col;
place(row + 1);
}
}
}
函数中可以看到 place(row+1) 这行代码，就是跳到下一行执行。当某行某列已经确定可以摆放皇后后，就暂时结束该行的遍历，跳到下一行执行。这里使用到递归思想， for 循环结束都是回溯的条件，如果没有达到终止条件，那么就会走 for 循环，当走完for 循环仍然没有找到可以摆放的位置时，然后执行 place(row+1) 上一行的代码，这就达到了路不通，就回到上一步选择另外一条路。isValid(row, col) 函数就是判断 (row, col) 的格子是否可以摆放皇后，代码如下：
boolean isValid(int row, int col) {
// row 的遍历要从 i 开始
for (int i = 0; i < row; i++) {
// 第 col 列已经有皇后
if (cols[i] == col) {
return false;
}
// 第i行的皇后跟第row行第col列格子处于同一斜线上
// 利用斜率解决，即 x1-x2 = y1-y2
// row 永远大于 i ，所以不用取绝对值
if (row - i == Math.abs(col - cols[i])) {
return false;
}
}
return true;
}
这就是摆放皇后的核心部分。首先判断 col 列是否已经有皇后了，即遍历 cols 数组中是否存在 col 元素。如果不存在，就判断该 i 行的皇后和 (row, col) 区域的格子是否在同一斜率上，这里使用了斜率公式，x1-x2 = y1-y2 就是在同一斜率上，因为摆放的皇后，它的斜率就是 1。
斜率公式
k= (y2-y1)/(x2-x1)
总结
- 回溯很多时候使用递归来处理；
- 使用斜率等于1来判断摆放皇后的斜线；
- 代码中的回溯条件就是走完 for 循环，这个地方需要细品。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: