所谓回溯算法，在笔者看来就是一种直接地思想----假设需要很多步操作才能求得最终的解，每一步操作又有很多种选择，那么我们就直接选择其中一种并依次深入下去。直到求得最终的结果，或是遇到明细的错误，回溯到上一步，换一种选择继续。就像把每种结果都遍历一遍，找到我们需要的结果。
回溯算法非常适合使用递归来求解，但与一般的递归又稍有不同。一个递归需要递归公式+递归终止条件，当然使用递归来实现的回溯算法也需要这些，只是就笔者的理解而言回溯算法还需要“回溯”这一部分。所谓回溯，就是在某一步中有多个选择的时候，选择完某一个选择后可能造成一些影响，把这些影响消除后再去选择同级的另一个选择。（笔者自己的理解，可能有不准确或是更好地描述，还望不吝赐教）
废话不多说，来看看十分著名的“N皇后”问题。题目来源与力扣（LeetCode），传送门。
51.N皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
这里稍微解释一下，N皇后问题最初来源与国际象棋的，而国际象棋的棋盘大小是8X8,因此经典版本的问题也叫“8皇后问题”。而所谓的皇后彼此之间不能相互攻击指的是：每个皇后棋子所在的行，所在的列，包括所在的对角线（两条）都没有其它棋子。
解决N皇后问题的思路是这样的，依次将棋子放到第一行，第二行...第N行。每次放置的时候都检查一下当前放棋子的位置，检查是否满足“皇后彼此之间不能相互攻击”。如果不满足要求，就在同一行内换一个位置继续尝试。如果满足要求，就到下一行继续放置棋子。贴一下笔者的代码，抛砖引玉了。（由于输出结果格式的一些问题，添加了一些不必要的代码，可以优化掉）
public class Solution {
private int count;
private IList<IList<string>> result = new List<IList<string>>();
IList<IList<string>> output = new List<IList<string>>();
public IList<IList<string>> SolveNQueens(int n)
{
count = n;
//初始化结果集合
for (int i = ; i < n; i++)
{
result.Add(new List<string>());
for (int j = ; j < n; j++)
{
result[i].Add(".");
}
}
//从第0行开始调用
calNQueens();
return output;
}
private void calNQueens(int row)
{
if (row == count) //已经遍历了N行了，可以返回结果了，内层是关于格式的调整，可以优化掉的
{
List<string> temp = new List<string>();
for (int i = ; i < count; i++)
{
temp.Add(string.Join("", result[i]));
}
output.Add(temp);
return;
}
//依次检查该列的每个位置
for (int column = ; column < count; column++)
{
if (isOk(row, column)) //放置棋子前检查是否满足要求，满足就放置棋子，并进入下一行。
{
result[row][column] = "Q";
calNQueens(row + );
}
//注意下面这一行，是笔者认为和一般的递归有些不同的地方，就是每次将“影响”消除，即“回溯”。对应到题目中去就是将刚刚放好的棋子再拿起来，避免出现一行有多个棋子的情况。
result[row][column] = ".";
}
}
// 检查要放置棋子的位置是否满足条件
private bool isOk(int row, int column)
{
int leftup = column - ; //用于检查左上方的对角线
int rightup = column + ; //用于检查右上方的对角线
// 下面一段是用于检查同行内是否有重复的棋子，但其实这段逻辑是不需要的，因为在上面的调用过程中已经避免了这种情况。
// for (int i = count- ; i >= ; i--)
// {
// if (result[row][i].Equals("Q"))
// {
// return false;
// }
// }
for (int i = row - ; i >= ; i--)
{
if (result[i][column].Equals("Q")) //检查同列
{
return false;
}
if (leftup >= ) //检查左上方
{
if (result[i][leftup].Equals("Q"))
{
return false;
}
}
if (rightup < count) //检查右上方
{
if (result[i][rightup].Equals("Q"))
{
return false;
}
}
leftup--;
rightup++;
}
return true;
}
}
笔者自己的思路大致是上面的样子，更详细一点的解法可以参照官方给出的解答，传送门。除了回溯的想法以外，官方的解法还有一点很有意思的优化。利用到一个公式：
对于所有的主对角线（右上到左下）有 行号 + 列号 = 常数。对于所有的次对角线（左上到右下）有 行号 - 列号 = 常数。感兴趣的小伙伴可以自己去看一哈。
关于回溯算法还有很多很多经典的问题，比如0-1背包等等，有机会再更新把。
