力扣第 51 题「N 皇后」就是这个经典问题，简单解释一下：给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击，请你计算出所有可能的放法。函数签名如下：
vector<vector<string>> solveNQueens(int n);
Tip
皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
比如如果给你输入 N = 4，那么你就要在 4x4 的棋盘上放置 4 个皇后，返回以下结果（用 . 代表空棋盘，Q 代表皇后）：
[
[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]
]
这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
class Solution {
List<List<String>> res = new ArrayList<>();
/* 输入棋盘边长 n，返回所有合法的放置 */
public List<List<String>> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; j++) {
sb.append('.');
}
board.add(sb.toString());
}
backtrack(board, 0);
return res;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(List<String> board, int row) {
// 触发结束条件
if (row == board.size()) {
res.add(new ArrayList<>(board));
return;
}
int n = board.get(row).length();
for (int col = 0; col < n; col++) {
// 排除不合法选择
if (!isValid(board, row, col)) {
continue;
}
// 做选择
StringBuilder sb = new StringBuilder(board.get(row));
sb.setCharAt(col, 'Q');
board.set(row, sb.toString());
// 进入下一行决策
backtrack(board, row + 1);
// 撤销选择
sb.setCharAt(col, '.');
board.set(row, sb.toString());
}
}
/* 是否可以在 board[row][col] 放置皇后？ */
boolean isValid(List<String> board, int row, int col) {
int n = board.size();
/* 检查列是否有皇后互相冲突 */
for (int i = 0; i < n; i++) {
if (board.get(i).charAt(col) == 'Q') {
return false;
}
}
/* 检查右上方是否有皇后互相冲突 */
for (int i = row - 1, j = col + 1;
i >= 0 && j < n; i--, j++) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
/* 检查左上方是否有皇后互相冲突 */
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
return true;
}
}
这部分主要代码，其实跟全排列问题差不多，isValid 函数的实现也很简单：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
/* 是否可以在 board[row][col] 放置皇后？ */
boolean isValid(List<String> board, int row, int col) {
int n = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i <= row; i++) {
if (board.get(i).charAt(col) == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < n; i--, j++) {
if (board.get(i).charAt(j) == 'Q')
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q')
return false;
}
return true;
}
Info
肯定有读者问，按照 N 皇后问题的描述，我们为什么不检查左下角，右下角和下方的格子，只检查了左上角，右上角和上方的格子呢？
因为皇后是一行一行从上往下放的，所以左下方，右下方和正下方不用检查（还没放皇后）；因为一行只会放一个皇后，所以每行不用检查。也就是最后只用检查上面，左上，右上三个方向。
函数 backtrack 依然像个在决策树上游走的指针，通过 row 和 col 就可以表示函数遍历到的位置，通过 isValid 函数可以将不符合条件的情况剪枝：
当 N = 8 时，就是八皇后问题，数学大佬高斯穷尽一生都没有数清楚八皇后问题到底有几种可能的放置方法，但是我们的算法只需要一秒就可以算出来所有可能的结果。
不过真的不怪高斯，这个问题的复杂度确实非常高，粗略估算一下：
N 行棋盘中，第一行有 N 个位置可能可以放皇后，第二行有 N - 1 个位置，第三行有 N - 2 个位置，以此类推，再叠加每次放皇后之前 isValid 函数所需的 O(N) 复杂度，所以总的时间复杂度上界是 O(N! * N)，而且没有什么明显的冗余计算可以优化效率。你可以试试 N = 10 的时候，计算就已经很耗时了。
当然，因为有 isValid 函数剪枝，并不会真的在每个位置都尝试放皇后，所以实际的执行效率会高一些。
有的时候，如果我们并不想得到所有合法的答案，只想要一个答案，怎么办呢？比如解数独的算法，找所有解法复杂度太高，只要找到一种解法就可以。
其实特别简单，只要稍微修改一下回溯算法的代码，用一个外部变量记录是否找到答案，找到答案后就停止继续递归即可：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
boolean found = false;
//函数找到一个答案后就返回true
boolean backtrack(List<String> board, int row) {
if (found) {
//已经找到一个答案了，不用再找了
return;
}
//触发结束条件
if (row == board.size()) {
res.add(new ArrayList<>(board));
//找到了第一个答案
found = true;
return;
}
//其他代码
}这样修改后，只要找到一个答案，后续的递归穷举都会被阻断。也许你可以在 N 皇后问题的代码框架上，稍加修改，写一个解数独的算法
再简单拓展一下，有可能题目不需要你计算出 N 皇后问题的所有具体结果，而仅仅问你共有几种解法，应该怎么做呢？
比如力扣第 52 题「 N 皇后 II 」：
给你一个整数 n，返回 n 皇后问题不同的解决方案的数量。比如输入 n = 4，你的算法返回 2，因为 4x4 的棋盘只有两种可行的解决方案。
其实你把我们上面写的解法 copy 过去也可以解决这个问题，因为我们计算出来的 res 就存储了所有合法的棋盘嘛，那么 res 中元素的个数不就是所有可行解法的总数吗？
是这样的，但要知道创建和存储这些具体的棋盘解法是要消耗空间和时间的，所以效率上可能会差一些。
更好的办法就是直接把 res 变量变成 int 类型，每次在 base case 找到一个合法答案的时候递增 res 变量即可：
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。
// 仅仅记录合法结果的数量
int res = 0;
void backtrack(List<String> board, int row) {
if (row == board.size()) {
// 找到一个合法结果
res++;
return;
}
// 其他都一样
}
最后总结
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：
def backtrack(...):
for 选择 in 选择列表:
做选择
backtrack(...)
撤销选择写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
其实想想看，回溯算法和动态规划是不是有点像呢？我们在动态规划系列文章中多次强调，动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？