# Shortest C++ solution in 0ms

• Idea is to use vectors to keep track of invalid positions , so validity can be checked in O(1) and put a queen in each column

``````#include<vector>
using namespace std;
class Solution {
public:
int find(int n, int left, int i, int r, vector<int>&rows,vector<int>&d1,vector<int>&d2){
if (left == 0)
return 1;
int j,sum=0;
for (j=r; j<n; j++){
if (rows[j] || d1[i+j] || d2[n-1+i-j])
continue;
rows[j]=d1[i+j]=d2[n-1+i-j]=1;
sum += find(n, left-1, i+1, 0,rows,d1,d2 );
rows[j]=d1[i+j]=d2[n-1+i-j]=0;
}
return sum;
}
int totalNQueens(int n) {
vector<int>  rows(n),d1(2*n-1),d2(2*n-1);
return find(n,n,0,0,rows,d1,d2);
}
};``````

• I share you with the same idea.

Here is my 0ms c++ solution:

``````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;
}
};
``````

• The fourth argument r in find is unnecessary and you can remove it.

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