LeetCode上面关于N皇后有两道题目：
51 N-Queens：https://leetcode.com/problems/n-queens/description/
52 N-Queens II：https://leetcode.com/problems/n-queens-ii/description/
两道题目其实差不多，一题是只要返回解的个数就可以了，一题是返回所有的解，做起来一模一样。
什么是N皇后问题？我们需要在一个N*N的棋盘上，放置N个皇后，使这些皇后不能互相攻击（即两个皇后之间不能处于同一行、同一列或者是同一斜线上），我们要求满足这个条件的所有解。
我采用的是回溯法去解决N皇后问题：
我们先在第一列放置一个皇后，然后在第二列与第一列不冲突的位置再放皇后，在第三列与第一列、第二列不冲突的位置放皇后……执行这样的操作，一直到第N列，我们就得到一个解了。
怎么回溯呢？我们可以想象成一棵树。假设我们在第一列的第一行放置了皇后，然后递归模拟了所有情况后，把第一列的第一行的皇后放到第二行，继续递归模拟所有情况。一直到把所有解都得出来。
下面看看LeetCode的具体题目：
51 N-Queens：
题目：
代码：
class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<string> queens(n); for (int i = 0; i < n; i++) { queens[i] = ""; for (int j = 0; j < n; j++) { queens[i] += "."; } } helper(res, queens, 0, n); return res; } void helper(vector<vector<string>> &res, vector<string> queens, int j, int n) { if (j == n) { res.push_back(queens); return; } for (int i = 0; i < n; i++) { if (isValid(queens, i, j)) { queens[i][j] = 'Q'; helper(res, queens, j + 1, n); queens[i][j] = '.'; } } } bool isValid(vector<string> s, int i, int j) { for (int k = 0; k < s.size(); k++) { if (i != k && s[k][j] == 'Q') return false; } for (int k = 0; k < s.size(); k++) { if (j != k && s[i][k] == 'Q') return false; } for (int m = i + 1, n = j + 1; m < s.size() && n < s.size(); m++, n++) { if (s[m][n] == 'Q') return false; } for (int m = i + 1, n = j - 1; m < s.size() && n >= 0; m++, n--) { if (s[m][n] == 'Q') return false; } for (int m = i - 1, n = j - 1; m >= 0 && n >= 0; m--, n--) { if (s[m][n] == 'Q') return false; } for (int m = i - 1, n = j + 1; m >= 0 && n < s.size(); m--, n++) { if (s[m][n] == 'Q') return false; } return true; } };