# Accepted 0ms c++ solution use backtracking and bitmask, easy understand.

• You can get the idea from my solution for N-Queens:

``````class Solution {
public:
int totalNQueens(int n) {
std::vector<int> flag(5 * n - 2, 1);
int res = 0;
totalNQueens(flag, 0, n, res);
return res;
}
private:
void totalNQueens(std::vector<int> &flag, int row, int &n, int &res) {
if (row == n) {
++res;
return;
}
for (int col = 0; col != n; ++col)
if (flag[col] && flag[col + row + n] && flag[col - row + 4 * n - 2]) {
flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 0;
totalNQueens(flag, row + 1, n, res);
flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 1;
}
}
};
``````

Or:

``````class Solution {
public:
int totalNQueens(int n) {
std::vector<int> flag(5 * n - 2, 1);
}
private:
int totalNQueens(std::vector<int> &flag, int row, int &n) {
if (row == n)
return 1;
int res = 0;
for (int col = 0; col != n; ++col)
if (flag[col] && flag[col + row + n] && flag[col - row + 4 * n - 2]) {
flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 0;
res += totalNQueens(flag, row + 1, n);
flag[col] = flag[col + row + n] = flag[col - row + 4 * n - 2] = 1;
}
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.