```
class Solution {
public:
vector<bool> columns;
vector<bool> cross_right;
vector<bool> cross_left;
int solve(int i, int n, int queens) {
if (queens == 0) {
return 1;
}
int count = 0;
for (int j = 0; j < n; j++) {
if (!columns[j] && !cross_right[j - i + n - 1] && !cross_left[i + j]) {
columns[j] = cross_right[j - i + n - 1] = cross_left[i + j] = true;
count += solve(i + 1, n, queens - 1);
columns[j] = cross_right[j - i + n - 1] = cross_left[i + j] = false;
}
}
return count;
}
int totalNQueens(int n) {
columns.resize(n, false);
cross_right.resize(2 * n - 1, false);
cross_left.resize(2 * n - 1, false);
return solve(0, n, n);
}
};
```