Hard！
题目描述：
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."], ["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解题思路：
这道题是之前那道N-Queens N皇后问题 的延伸，说是延伸其实我觉得两者顺序应该颠倒一下，上一道题比这道题还要稍稍复杂一些，二者本质上没有什么区别，都是要用回溯法Backtracking来解，如果理解了之前那道题的思路，此题只要做很小的改动即可，不再需要求出具体的皇后的摆法，只需要每次生成一种解法时，计数器加一即可。
C++解法一：
class Solution {
public:
int totalNQueens(int n) {
int res = ;
vector<int> pos(n, -);
totalNQueensDFS(pos, , res);
return res;
}
void totalNQueensDFS(vector<int> &pos, int row, int &res) {
int n = pos.size();
if (row == n) ++res;
else {
for (int col = ; col < n; ++col) {
if (isValid(pos, row, col)) {
pos[row] = col;
totalNQueensDFS(pos, row + , res);
pos[row] = -;
}
}
}
}
bool isValid(vector<int> &pos, int row, int col) {
for (int i = ; i < row; ++i) {
if (col == pos[i] || abs(row - i) == abs(col - pos[i])) {
return false;
}
}
return true;
}
};
C++解法二：
class Solution {
private:
int res;
public:
int totalNQueens(int n) {
vector<int> state(n, -);
res = ;
helper(state, );
return res;
}
void helper(vector<int> &state, int row)
{//放置第row行的皇后
int n = state.size();
if(row == n)
{
res++;
return;
}
for(int col = ; col < n; col++)
if(isValid(state, row, col))
{
state[row] = col;
helper(state, row+);
state[row] = -;;
}
}
//判断在row行col列位置放一个皇后，是否是合法的状态
//已经保证了每行一个皇后，只需要判断列是否合法以及对角线是否合法。
bool isValid(vector<int> &state, int row, int col)
{
for(int i = ; i < row; i++)//只需要判断row前面的行，因为后面的行还没有放置
if(state[i] == col || abs(row - i) == abs(col - state[i]))
return false;
return true;
}
};