回溯算法

1. 回溯算法概述

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，直到找到解或者尝试了所有可能的选择都无法找到解为止。这种走不通就退回再走的技术称为回溯法，它是一种“优化的暴力搜索”，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法通常采用深度优先搜索来遍历解空间，前序、中序和后序遍历都属于深度优先搜索。回溯算法的核心思想有两点：

  1. 深度优先搜索：回溯算法基于深度优先搜索的思想，它会沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点所在的路径无法得到有效的解时，算法会回溯到上一个节点，尝试其他的路径继续搜索。
  2. 穷举与剪枝：本质上是对所有可能的解进行穷举搜索，但与纯粹的暴力枚举不同，回溯算法会在搜索过程中根据问题的约束条件进行剪枝操作，避免对一些明显不可能产生解的分支进行搜索，从而提高搜索效率。

1.1 子集树

子集树解决的是选还是不选的问题，也就是组合问题。元素的顺序不重要，只关心包含了谁。

  • 节点的含义：到达树的第i层，意味着我们正在考虑第i个物品。对于每个物品，只有两条路：
    1. 要它（左子树）。
    2. 不要它（右子树）。
  • 树的形状：这是一棵二叉树。因为每个节点只有选和不选两个分支。

图解示例（从集合 [A, B, C] 中选，求所有子集）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                              {}                          (根节点：还没开始选)

                 /                        \
            选A                          不选A
             /                             \
           {A}                             {}             (第1层结束：决定A的命运)

         /      \                       /        \
     选B        不选B               选B         不选B
      /           \                  /             \
   {A,B}          {A}              {B}             {}     (第2层结束：决定B的命运)

   /    \        /    \           /    \        /     \
选C     不选C   选C    不选C    选C     不选C  选C     不选C
 |       |      |      |       |       |      |      |
{A,B,C} {A,B}  {A,C}   {A}    {B,C}    {B}   {C}    {}    (第3层结束：决定C的命运)

顺着这棵树走到尽头，你会得到以下 8 个结果，正好对应数学上的 23=8 种子集：

  1. 左左左：选A -> 选B -> 选C = {A, B, C}
  2. 左右右：选A -> 选B -> 不选C = {A, B}
  3. 左左右：选A -> 不选B -> 选C = {A, C}
  4. 左右右：选A -> 不选B -> 不选C = {A}
  5. 右左左：不选A -> 选B -> 选C = {B, C}
  6. 右左右：不选A -> 选B -> 不选C = {B}
  7. 右右左：不选A -> 不选B -> 选C = {C}
  8. 右右右：不选A -> 不选B -> 不选C = {} (空集)

在C++代码中子集树的循环里，通常是：

1
2
3
// 只有选和不选两个分支
dfs(i + 1, sum + w[i]);  // 选
dfs(i + 1, sum);         // 不选

1.2 排列树

排列树解决的是先排A还是先排B的问题，也就是全排列问题。元素的顺序很重要，或者需要穷举所有可能的顺序。

  • 节点的含义：到达树的第 i层，意味着我们要确定第 i个位置放谁。可以从剩下的元素中任选一个放进来。

  • 树的形状：这不是二叉树，而是多叉树。第 1 层有 n个分叉，第 2 层有 n−1个分叉，……

    注意：排列树通常不需要记录路径的长度状态，而是通过标记数组记录谁被用过了。

图解示例（对 [A, B, C] 进行全排列）：

1
2
3
4
5
6
7
8
9
10
11
12
13
                         { }                        (根节点：还没开始排)
           /              |             \
       放A               放B              放C        (第1层：第1个位置有3种选择)
        |                |                |
       {A}              {B}              {C}        (第1层结束：第1位已确定)
    /      \         /      \         /      \
  放B      放C     放A       放C     放A       放B   (第2层：第2个位置只有剩下的2种选择)
  |        |       |         |       |        |
 {AB}     {AC}    {BA}      {BC}    {CA}     {CB}   (第2层结束：前2位已确定)
  |        |       |         |       |        |
 放C      放B      放C       放A     放B      放A    (第3层：第3个位置只有剩下的1种选择)
  |        |       |         |       |        |
{ABC}    {ACB}   {BAC}     {BCA}   {CBA}    {CAB}   (第3层结束：排列完成)
特征 子集树 排列树
典型问题 0-1背包、组合 全排列、旅行商问题
决策逻辑 0 or 1 (选还是不选) 谁是下一个? (排列组合)
兄弟节点关系 兄弟节点做同样的选择逻辑，只是针对不同的物品 兄弟节点代表不同的元素在同一个位置
树的分叉数 固定为 2 (二叉树) 随层数递减 (n, n−1, n−2 …)
是否去重 天然不需要担心顺序问题 (因为只有位置i) 需要标记是否用过该元素 (防重复选)

在C++代码中排列树的循环里，通常是：

1
2
3
4
5
6
7
8
9
10
11
// 尝试把剩下的每个数都放进来试试
for (int i = 0; i < n; i++) 
{
    if (!used[i]) 
    {      // 只要没用过
        used[i] = true;
        path.push_back(nums[i]);
        dfs(depth + 1);
        used[i] = false; // 回溯
    }
}

1.3 剪枝

在算法和数据结构中（特别是回溯算法、决策树学习中），剪枝指的是在搜索或构建树的过程中，提前断开那些“明显不可能得出最优解”或“明显不符合要求”的路径，从而减少计算量，提高效率。

树的每一次分叉代表一种选择。树越深，节点越多（呈指数级增长）。如果我们能判断出某一根树枝“长势不好”，就在它刚开始长出来的时候把它切断，那么这根树枝下面的所有子树就都不用生成了。

剪枝的核心目的：

  1. 少干活：不计算那些注定没用的情况。
  2. 省空间：不需要存储那些废弃的分支。

通常在以下 3 种情况下，我们会挥动剪刀：

  1. 可行性剪枝（约束条件）—— “这路不对，别走了”

  2. 最优性剪枝（界限条件）—— “这路太慢，追不上了”

  3. 重复性剪枝（去重）—— “来过了，别回头”

我们在刚才的排列树上加上一个具体的限制条件，来看看什么是“剪枝”。假设题目要求：

生成的排列中，中间那个字符（第2个位置）不能是 “B”。

我们来看如何在生长过程中把不符合要求的树枝“剪”掉，从而省去后面无意义的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
                         { }                        (根节点: 未开始)
          /               |               \
       放A               放B               放C
        |                |                 |
       {A}              {B}               {C}       (第1层结束)
     /     \          /     \           /      \
   放B      放C     放A       放C      放A      放B
    |       |       |         |       |        |
    ✂     {AC}    {BA}     {BC}     {CA}      ✂    (第2层结束)
(第2位是B)   |       |         |       |     (第2位是B)
           放B     放C       放A      放B
            |       |         |       |
          {ACB}   {BAC}     {BCA}   {CAB}           (最终结果)

1.4 解空间

在回溯算法中，解空间是一个非常核心的理论概念。简单来说，解空间就是问题所有可能解构成的集合。回溯算法的过程，本质上就是在这个解空间中进行遍历，并在这个过程中搜索出满足条件的解。

下面详细解释这一概念及其用途：

解空间是一个隐形的树状结构。我们可以把问题的求解过程看作是从根节点出发，一路向下做决策，直到抵达叶子节点。

  • 状态的集合：解空间包含了从初始状态开始，经过一系列操作（决策）所能达到的所有状态。
  • 树的隐喻：
    • 根节点：对应初始状态。
    • 边：代表你做了一个选择。
    • 节点：代表经过一系列选择后的状态。
    • 叶子节点：代表一个确定的方案或无法继续的状态。

举个栗子：
如果有 3 个物品 [A, B, C]，求所有的子集，解空间树就是：

1
2
3
4
5
6
7
         { }            <-- 第0层（根节点，空集）
    /     |     \
   A      B      C      <-- 第1层：选了1个元素
  / \     |
 AB  AC   BC            <-- 第2层：选了2个元素
 |
ABC                     <-- 第3层：选了3个元素

因此，解空间 = 整棵树的所有节点（根节点 + 中间分支节点 + 叶子节点）。比如：“({} -> A, A -> AB, AB -> ABC …) 这些所有节点以及它们之间的连线，共同构成了解空间。那么，解空间有什么用呢？

理解解空间的概念，对于算法设计和调试至关重要。它的主要作用体现在以下几点：

  1. 定义搜索的边界：解空间告诉算法去哪里找

    • 如果没有解空间的概念，就不知道循环该怎么写，递归该什么时候停。

    • 在 C++ 代码中，for 循环的范围、递归的深度、起始索引的设置，本质上都是在划定解空间的范围。

  2. 剪枝的依据：这是解空间最主要的作用。

    • 如果解空间很大（比如 2N 或 N! 级别），暴力遍历整个解空间会超时。

    • 通过分析解空间的性质，我们可以提前判断某些分支（解空间的一部分）绝对不可能包含正确答案，从而直接砍掉它，不再进入。

  3. 区分问题类型（集合 vs 树）：理解解空间的结构有助于你使用不同的 C++ 策略。

    • 子集/组合问题：解空间通常是一颗子集树。解空间的元素是无序的，为了避免重复（AB 和 BA 是一样的），我们需要 起始索引来限制解空间的搜索方向（只往右找，不往回找）。

    • 排列问题：解空间通常是一颗排列树。有序，[1, 2] 和 [2, 1] 是两个解。所以解空间的搜索方向包含所有未使用的元素，需要 used 数组来辅助。

  4. 复杂度分析：看到问题，先想象它的解空间树有多大，树叶有多少个。

    • 最坏时间复杂度通常取决于解空间的大小（节点数量）。
      • 排列问题：解空间大小通常是 O(n!)。
      • 子集/组合问题：解空间大小通常是 O(2n)。
      • 如果不加剪枝，回溯算法的时间复杂度就是解空间的大小。

在 C++ 编写回溯代码时，我们大脑里的思维路径应该是这样的：

  1. 构建解空间：想象这棵树长什么样？根节点是什么？子节点是什么？（是排列树还是子集树？）
  2. 遍历解空间：用递归函数和 for 循环来遍历这棵树的节点。
  3. 剪枝解空间：在 if 判断中，把那些不符合条件的树枝折断，缩小搜索范围。

一句话总结：解空间是回溯算法的“地图”，算法是在这张地图上找宝藏的过程，而剪枝是为了抄近路。

2. 回溯算法的抽象结构

回溯法解决的问题都可以抽象为树形结构（N叉树）：

  • 树的宽度：每次可做出的选择数量（for循环）。
  • 树的深度：递归的深度（递归次数）。

在回溯算法的核心逻辑处理流程中，其递归函数的处理一共分三个要点：

  1. 回溯函数返回值及参数：通常是void，参数根据问题来确定。
  2. 回溯函数终止条件：也就是什么时候收集处理的结果。
  3. 单层搜索的过程：
    • for循环遍历
    • 处理节点
    • 递归
    • 回溯操作（撤销处理）

以下为 C++通用的代码模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// result 用于存放最终结果集
// path 用于存放当前递归路径（单次结果）
void backtrack(参数) 
{
    // 1. 终止条件
    if (终止条件) 
    {
        result.push_back(path); // 收集结果
        return;
    }

    // 2. 遍历当前层可做的选择（集合的大小就是树的宽度）
    for (int i = startIndex; i < size; i++) 
    {
        
        // 3. 剪枝操作
        // 如果当前选择明显不符合条件，直接跳过（如重复元素、越界等）
        if (/* 剪枝条件 */) continue;

        // 4. 处理节点：做出选择
        path.push_back(当前元素);

        // 5. 递归：进入下一层决策树
        // 注意：不同问题传入的 i 不同，组合问题传 i+1，排列问题传 i（需配合used数组）
        backtrack(i + 1, 其他参数); 

        // 6. 回溯：撤销处理（关键的一步！）
        // 也就是撤销刚才做的选择，返回上一层，尝试下一个 for 循环的 i
        path.pop_back();
    }
}

3. 经典问题实战

3.1 组合问题

题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

难点解析：

  1. 去重：如何保证 [1, 2] 和 [2, 1] 不重复出现？-> startIndex 的使用。
  2. 剪枝：如果剩余的元素不够凑齐 k 个，循环就没有必要继续了。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 头文件 backtracking.h
#include <iostream>
#include <vector>

using namespace std;

// 组合问题
class Solution 
{
public:         
    void backtrack(int n, int k, int startIndex);
    vector<vector<int>> combine(int n, int k);
    void printCombinations(const vector<vector<int>>& combinations);
    void testCombine();
private:
    vector<vector<int>> result; 
    vector<int> path;  
};

算法策略：

  1. 树形结构建模：
    • 将问题抽象为一棵 n 叉树
    • 树的深度：由递归深度表示，最大深度为 k（组合大小）
    • 树的宽度：由每层的选择数量决定，通过 for 循环遍历
  2. 避免重复的关键 - startIndex：
    • 引入 startIndex 参数，表示当前层从哪个数字开始选择
    • 每次递归调用时传入 i + 1，确保下一层只从更大的数字开始选择
    • 这样就保证了组合的 单调递增 特性，自然避免了 [2, 1] 这种重复
  3. 剪枝优化：
    • 观察：如果剩余可选的数字数量小于还需要选择的数字数量，就没有必要继续了
    • 数学推导：当前最多可以遍历到的索引为 n - (k - path.size()) + 1
    • 效果：大幅减少递归调用次数，提高算法效率
  4. 回溯流程：
    • 选择：将当前数字加入路径
    • 探索：递归处理下一个数字
    • 撤销：回溯到上一层状态，尝试其他选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// 源文件 backtracking.cpp
#include "backtracking.h"
void Solution::backtrack(int n, int k, int startIndex)
{
    // 终止条件：当前路径长度等于要求的组合大小
    if (path.size() == k) 
    {
        result.push_back(path); 
        return;
    }

    // 剪枝优化
    for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) 
    {
        path.push_back(i);      
        backtrack(n, k, i + 1); 
        path.pop_back();        
    }
}

vector<vector<int>> Solution::combine(int n, int k)
{
    result.clear(); 
    path.clear();   
    backtrack(n, k, 1);
    return result;
}

void Solution::printCombinations(const vector<vector<int>>& combinations)
{
    cout << "总共找到 " << combinations.size() << " 个组合：" << endl;
    for (int i = 0; i < combinations.size(); i++) 
    {
        cout << "组合 " << i + 1 << ": [";
        for (int j = 0; j < combinations[i].size(); j++) 
        {
            cout << combinations[i][j];
            if (j < combinations[i].size() - 1) 
            {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }
    cout << "------------------------" << endl;
}

void Solution::testCombine()
{
    Solution sol;
    cout << "=== 测试用例 1: n=4, k=2 ===" << endl;
    vector<vector<int>> result1 = sol.combine(4, 2);
    printCombinations(result1);
    // 预期结果: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]

    cout << "=== 测试用例 2: n=5, k=3 ===" << endl;
    vector<vector<int>> result2 = sol.combine(5, 3);
    printCombinations(result2);
    // 预期结果: 10个组合，如 [1,2,3], [1,2,4], [1,2,5], [1,3,4]...

    cout << "=== 测试用例 3: 边界测试 n=1, k=1 ===" << endl;
    vector<vector<int>> result3 = sol.combine(1, 1);
    printCombinations(result3);
    // 预期结果: [[1]]

    cout << "=== 测试用例 4: k=1 的特殊情况 ===" << endl;
    vector<vector<int>> result4 = sol.combine(3, 1);
    printCombinations(result4);
    // 预期结果: [[1], [2], [3]]

    cout << "=== 测试用例 5: k=n 的特殊情况 ===" << endl;
    vector<vector<int>> result5 = sol.combine(3, 3);
    printCombinations(result5);
    // 预期结果: [[1,2,3]]
}

int main() 
{
    Solution s;
    cout << "组合问题算法测试" << endl;
    cout << "========================" << endl;
    s.testCombine();
    return 0;
}

算法可视化（以 n=4, k=2 为例）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
回溯树结构：
开始 []
|
├── 选择1 [1]
│   ├── 选择2 [1,2] ✓
│   ├── 选择3 [1,3] ✓
│   └── 选择4 [1,4] ✓
|
├── 选择2 [2]
│   ├── 选择3 [2,3] ✓
│   └── 选择4 [2,4] ✓
|
├── 选择3 [3]
│   └── 选择4 [3,4] ✓
|
└── 选择4 [4] (剪枝：需要2个数字，但只剩1个可选)

3.2 排列问题

题目：给定一个不含重复数字的数组 nums，返回其所有可能的全排列。

难点解析：

  1. 每层都是从0开始遍历：因为排列讲究顺序，[1, 2] 和 [2, 1] 是不同的排列。
  2. 使用状态：由于每次都从头遍历，需要记录哪些元素已经在当前路径 path 中被使用过了。

C++ 代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 头文件 backtracking.h
#include <iostream>
#include <vector>
using namespace std;

// 排列问题
class Solution1 
{
public:
    void backtrack(vector<int>& nums, vector<bool>& used);
    vector<vector<int>> permute(vector<int>& nums);
    void printPermutations(const vector<vector<int>>& permutations);
    bool validatePermutations(const vector<vector<int>>& result, vector<int>& nums);
    void testPermute();
private:
    vector<vector<int>> result; // 存储所有排列结果
    vector<int> path;           // 存储当前路径（单个排列）
};

算法策略：

  1. 树形结构建模：
    • 将问题抽象为一棵 n 叉树
    • 树的深度：由递归深度表示，最大深度为 n（数组长度）
    • 树的宽度：每层的宽度都是 n（因为排列中每个位置都可以选择任何未使用的元素）
  2. 避免重复使用的关键 - used 数组：
    • 使用 vector<bool> used 记录每个元素是否已在当前路径中使用
    • 在选择元素前检查 used[i]，确保同一个元素不会被重复选择
    • 这是与组合问题的核心区别：组合用 startIndex，排列用 used 数组
  3. 回溯流程：
    • 选择：将当前未使用的元素加入路径，标记为已使用
    • 探索：递归处理下一个位置
    • 撤销：回溯到上一层状态，取消标记，尝试其他选择
  4. 终止条件：
    • 当路径长度等于数组长度时，说明已生成一个完整的排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// 源文件 backtracking.cpp
#include "backtracking.h"
#include <algorithm>
void Solution1::backtrack(vector<int>& nums, vector<bool>& used)
{
    // 终止条件：当前路径长度等于数组长度，形成一个完整排列
    if (path.size() == nums.size()) 
    {
        result.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) 
    {
        // 剪枝
        if (used[i]) 
        {
            continue;
        }
        used[i] = true;
        path.push_back(nums[i]);
        // 递归
        backtrack(nums, used);
        // 回溯
        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> Solution1::permute(vector<int>& nums)
{
    result.clear();
    path.clear();
    vector<bool> used(nums.size(), false);
    backtrack(nums, used);
    return result;
}

void Solution1::printPermutations(const vector<vector<int>>& permutations)
{
    cout << "总共找到 " << permutations.size() << " 个排列：" << endl;
    for (int i = 0; i < permutations.size(); i++) 
    {
        cout << "排列 " << i + 1 << ": [";
        for (int j = 0; j < permutations[i].size(); j++) 
        {
            cout << permutations[i][j];
            if (j < permutations[i].size() - 1) 
            {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }
    cout << "------------------------" << endl;
}

bool Solution1::validatePermutations(const vector<vector<int>>& result, vector<int>& nums)
{
    int n = nums.size();
    int expectedCount = 1;
    for (int i = 1; i <= n; i++)
    {
        expectedCount *= i;
    }

    if (result.size() != expectedCount) 
    {
        cout << "错误：预期 " << expectedCount << " 个排列，实际找到 " << result.size() << endl;
        return false;
    }

    // 检查每个排列是否包含所有元素且不重复
    for (const auto& perm : result) 
    {
        if (perm.size() != n) 
        {
            cout << "错误：排列长度不正确" << endl;
            return false;
        }

        vector<int> sorted_perm = perm;
        sort(sorted_perm.begin(), sorted_perm.end());
        if (sorted_perm != nums) 
        {
            cout << "错误：排列包含错误元素" << endl;
            return false;
        }
    }

    cout << "√ 验证通过：所有排列都正确" << endl;
    return true;
}

void Solution1::testPermute()
{
    Solution1 s;
    cout << "=== 测试用例 1: [1,2,3] ===" << endl;
    vector<int> nums1 = { 1, 2, 3 };
    vector<vector<int>> result1 = s.permute(nums1);
    printPermutations(result1);
    validatePermutations(result1, nums1);
    // 预期结果: 6个排列，包含所有可能的顺序

    cout << "=== 测试用例 2: [0,1] ===" << endl;
    vector<int> nums2 = { 0, 1 };
    vector<vector<int>> result2 = s.permute(nums2);
    printPermutations(result2);
    validatePermutations(result2, nums2);
    // 预期结果: [[0,1], [1,0]]

    cout << "=== 测试用例 3: 单个元素 [5] ===" << endl;
    vector<int> nums3 = { 5 };
    vector<vector<int>> result3 = s.permute(nums3);
    printPermutations(result3);
    validatePermutations(result3, nums3);
    // 预期结果: [[5]]

    cout << "=== 测试用例 4: 四个元素 [1,2,3,4] ===" << endl;
    vector<int> nums4 = { 1, 2, 3, 4 };
    vector<vector<int>> result4 = s.permute(nums4);
    cout << "4个元素的排列数: " << result4.size() << " (4! = 24)" << endl;
    printPermutations(result4);
    validatePermutations(result4, nums4);
    cout << "------------------------" << endl;
}


int main()
{
    Solution s;
    cout << "排列问题算法测试" << endl;
    // 运行测试
    Solution1 sol;
    sol.testPermute();
    return 0;
}

3.3 棋盘问题(N皇后)

题目：在 n×n 的国际象棋棋盘上放置 n 个皇后，使其不能互相攻击（任意两个皇后不能在同一行、同一列、同一斜线）。

难点解析：

  1. 多维搜索：这是一个二维棋盘，通常可以用一维数组或递归深度来表示行号，循环来表示列号。
  2. 校验逻辑：放入皇后前，需要检查当前位置是否合法（上方、左上角、右上角是否有皇后）。由于我们是一行一行放的，所以不需要检查下方和左右方。
  3. 字符串处理：棋盘的表示通常使用 vector<string>。

C++ 代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 头文件 backtracking.h
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// N皇后问题
class Solution2
{
public:
    // n: 棋盘大小，也是需要放置的皇后数量
    // row: 当前正在处理的行（从0开始）
    // chessboard: 当前的棋盘状态，是一个n×n的字符矩阵
    void backtrack(int n, int row, vector<string>& chessboard);
    // 校验函数：检查在(targetRow, targetCol)位置放置皇后是否合法
    bool isValid(int targetRow, int targetCol, vector<string>& chessboard, int n);
    vector<vector<string>> solveNQueens(int n);
private:
    vector<vector<string>> result;
};

算法策略：

  1. 路径选择：
    • 从棋盘的第一行（Row 0）开始，逐行向下处理。
    • 函数参数通常只传递当前行索引 row。
  2. 合法性校验（剪枝）：
    • 在当前行 row，遍历每一列 col（从 0 到 N-1）。
    • 对于位置(row, col)，检查是否触发冲突：
      • col 列是否有皇后？
      • 主对角线（方向 \）是否有皇后？
      • 副对角线（方向 /）是否有皇后？
    • 策略：如果任何一项检查为“是”，则跳过该列（剪枝），不进行递归。
  3. 递归与状态更新：
    • 如果位置(row, col)合法：
      1. 将皇后放置在该位置（逻辑上）。
      2. 更新状态：标记列 col、主对角 、副对角 为“已占用”。
      3. 递归调用：进入下一行 backtrack(row + 1)。
  4. 回溯与状态撤销：
    • 当子递归返回（无论是因为找到了一个解还是无路可走），需要撤销当前节点的选择，以便尝试当前行的下一列。
    • 撤销状态：将列 col、主对角 、副对角标记回“未占用”。
  5. 终止条件：
    • 当 row == N 时，说明成功在 0 到 N-1 行都放置了皇后，找到一个合法解，计数器加 1 并返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// 源文件 backtracking.cpp
#include "backtracking.h"

void Solution2::backtrack(int n, int row, vector<string>& chessboard)
{
    // 终止条件：已经成功处理完所有n行
    if (row == n) 
    {
        result.push_back(chessboard); // 保存当前有效的棋盘布局
        return;
    }

    // 遍历当前行的所有列位置
    for (int col = 0; col < n; col++) 
    {
        // 关键：检查在(row, col)位置放置皇后是否合法
        if (isValid(row, col, chessboard, n)) 
        {
            // 处理节点：放置皇后
            chessboard[row][col] = 'Q';
            // 递归：处理下一行
            backtrack(n, row + 1, chessboard);
            // 回溯：撤销当前放置，尝试下一个列位置
            chessboard[row][col] = '-';
        }
    }
}

bool Solution2::isValid(int targetRow, int targetCol, vector<string>& chessboard, int n)
{
    // 检查同一列上方是否有皇后（由于按行放置，下方还没有皇后）
    for (int i = 0; i < targetRow; i++) 
    {
        if (chessboard[i][targetCol] == 'Q') 
        {
            return false; // 同一列已有皇后
        }
    }

    // 检查45度对角线（左上角方向）是否有皇后
    for (int i = targetRow - 1, j = targetCol - 1; i >= 0 && j >= 0; i--, j--) 
    {
        if (chessboard[i][j] == 'Q') 
        {
            return false; // 左上对角线已有皇后
        }
    }

    // 检查135度对角线（右上角方向）是否有皇后
    for (int i = targetRow - 1, j = targetCol + 1; i >= 0 && j < n; i--, j++) 
    {
        if (chessboard[i][j] == 'Q') 
        {
            return false; // 右上对角线已有皇后
        }
    }
    return true; // 所有检查都通过，位置合法
}

vector<vector<string>> Solution2::solveNQueens(int n)
{
    // 初始化棋盘：n×n的矩阵，全部用'.'填充
    vector<string> chessboard(n, string(n, '-'));
    backtrack(n, 0, chessboard);
    return result;
}

int main()
{
    cout << "N皇后问题算法测试" << endl;
    Solution2 sol;
    int n = 4; // 测试4皇后问题
    vector<vector<string>> solutions = sol.solveNQueens(n);

    cout << n << "皇后问题共有 " << solutions.size() << " 种解法：" << endl;
    for (int i = 0; i < solutions.size(); i++)
    {
        cout << "解法 " << i + 1 << ":" << endl;
        for (const string& row : solutions[i])
        {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}