N皇后问题源于著名的八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！

将8x8扩展为NxN即为N皇后问题，要解决此问题，最简单的方法就是暴力枚举，此时的时间复杂度为N^2，回溯算法与简单暴力枚举类似，不同点在于当判定某种状态不符合答案时，便不再继续枚举此状态的后续状态，而是回溯到该状态之前，继续遍历其他的可能值。

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 using namespace std;
 5 
 6 bool check(const vector<vector<int>> &vec, int row, int col, int n)
 7 {
 8     // 检查列冲突
 9     for (int i = 0; i < n; i++)
10     {
11         if (vec[i][col] == 1)
12             return false;
13     }
14 
15     // 检查左上对角线
16     for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
17     {
18         if (vec[i][j] == 1)
19             return false;
20     }
21     for (int i = row + 1, j = col + 1; i < n &&j < n; i++, j++)
22     {
23         if (vec[i][j] == 1)
24             return false;
25     }
26 
27     // 检查左下对角线
28     for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
29     {
30         if (vec[i][j] == 1)
31             return false;
32     }
33     for (int i = row + 1, j = col - 1; i < n&&j >= 0; i++, j--)
34     {
35         if (vec[i][j] == 1)
36             return false;
37     }
38 
39     return true;
40 }
41 
42 void findQueen(vector<vector<int>> &vec, int row, int n, vector<vector<string>> &res)
43 {
44     if (row == n)
45     {
46         vector<string> queenResult;
47         for (auto &i : vec)
48         {
49             string str;
50             for (auto j : i)
51             {
52                 if (j == 1)
53                     str += 'O';
54                 else
55                     str += '+';
56             }
57             queenResult.push_back(str);
58         }
59         res.push_back(queenResult);
60     }
61 
62     for (int col = 0; col < n; col++)
63     {
64         // 回溯
65         if (check(vec, row, col, n))
66         {
67             vec[row][col] = 1;
68             findQueen(vec, row + 1, n, res);
69             vec[row][col] = 0;    // 遍历下一列时，将当前列重置
70         }
71     }
72 }
73 
74 // N皇后
75 vector<vector<string>> NQueen(int n)
76 {
77     vector<vector<int>> vec(n, vector<int>(n, 0));
78     vector<vector<string>> res;
79     findQueen(vec, 0, n, res);
80     return res;
81 }
82 
83 int main()
84 {
85     auto res = NQueen(8);
86     for (int i = 0; i < res.size(); i++)
87     {
88         cout << "result " << i << ":" << endl;
89         for (auto &s : res[i])
90             cout << s << endl;
91     }
92     return 0;
93 }