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 }