什么是回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
八皇后问题
我们学习了什么是回溯算法，听起来很简单，但具体怎么使用呢？下面我们通过一个例子来说明回溯算法的用法。
八皇后问题：有一个8X8的棋盘，希望往里放8个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子，找到所有满足这种要求的放棋方式。
解题思路：把这个问题划分成8个阶段，依次将8个棋子放到第一行、第二行、第三行....第八行。在放置的过程中，不停地检查当前的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就换一种方法，继续尝试。
代码实现如下：
public class Solution {
int[] result = new int[8]; // 全局或成员变量，下标表示行，值表示queen存储在哪一列
public void Cal8Queens (int row) { // 调用方式：Cal8Queens(0);
if (row == 8) { // 8个棋子都放置好了，打印结果
PrintQueens (result);
return; // 8行棋子都放好了，已经没法再往下递归了，所以就return
}
for (int column = 0; column < 8; ++column) { // 每一行都有8中放法
if (IsOK (row, column)) { // 有些放法不满足要求
result[row] = column; // 第row行的棋子放到了Column列
Cal8Queens (row + 1); // 考察下一行
}
}
}
private bool IsOK (int row, int column) { // 判断row行column列放置是否合适
int leftup = column - 1, rightup = column + 1;
for (int i = row - 1; i >= 0; --i) { // 逐行往上考察每一行
if (result[i] == column) return false; // 第i行的column列有棋子吗？
if (leftup >= 0) { // 考察左上对角线：第i行leftup列有棋子吗？
if (result[i] == leftup) return false;
}
if (rightup < 8) { // 考察右上对角线：第i行rightup列有棋子吗？
if (result[i] == rightup) return false;
}
--leftup;
++rightup;
}
return true;
}
private void PrintQueens (int[] result) { // 打印出一个二维矩阵
for (int row = 0; row < 8; ++row) {
for (int column = 0; column < 8; ++column) {
if (result[row] == column) Console.Write ("Q ");
else Console.Write ("* ");
}
Console.WriteLine ();
}
Console.WriteLine();
}
}
总结
回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题：从一组可能的解中，选择出一个满足要求的解。
回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，并不需要穷举搜索所有的情况，从而提高搜索效率。
网友评论