# Simple yet efficient solution 4ms in C++

• ``````class Solution {
private:
void search(int n, int r, vector<string>& v, vector<vector<string>>& vv, vector<int>& forward, vector<int>& backward,
vector<int>& columns)
{
if(r == n) vv.push_back(v);
for(int c = 0; c < n; c++)
{
if(!forward[c+r] && !backward[r+n-c-1] && !columns[c])
{
v[r][c] = 'Q';
forward[c+r] = backward[r+n-c-1] = columns[c] = 1;
search(n, r+1, v, vv, forward, backward, columns);
forward[c+r] = backward[r+n-c-1] = columns[c] = 0;
v[r][c] = '.';
}
}
}
public:
//AC - 4ms - best submission;
vector<vector<string>> solveNQueens(int n)
{
vector<int> forward(2*n-1), backward(2*n-1), columns(n); //using int instead of bool accelerate from 16ms to 8ms;
vector<vector<string>> vv;
vector<string> v(n, string(n, '.')); //using predefined board instead of creating a new string each time, accelerating from 8ms to 4ms;
search(n, 0, v, vv, forward, backward, columns);
return vv;
}
};``````

• #### Primitive

test

``````class Solution {
private:
void search(int n, int r, vector<string>& v, vector<vector<string>>& vv, vector<int>& forward, vector<int>& backward,
vector<int>& columns) {
if(r == n) vv.push_back(v);
for(int c = 0; c < n; c++) {
if(!forward[c+r] && !backward[r+n-c-1] && !columns[c]) {
v[r][c] = 'Q';
forward[c+r] = backward[r+n-c-1] = columns[c] = 1;
search(n, r+1, v, vv, forward, backward, columns);
forward[c+r] = backward[r+n-c-1] = columns[c] = 0;
v[r][c] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<int> forward(2*n-1), backward(2*n-1), columns(n);
vector<vector<string>> vv;
vector<string> v(n, string(n, '.'));
search(n, 0, v, vv, forward, backward, columns);
return vv;
}
};
``````

#### Follow-up

test

``````class Solution {
private:
int search(int n, int r, vector<int>& forward, vector<int>& backward, vector<int>& cols) {
if(n == r) return 1;
int sum = 0;
for(int c = 0; c < n; ++c) {
if(!forward[r+c] && !backward[n+r-c-1] && !cols[c]) {
forward[r+c] = backward[n+r-c-1] = cols[c] = 1;
sum += search(n, r+1, forward, backward, cols);
forward[r+c] = backward[n+r-c-1] = cols[c] = 0;
}
}
return sum;
}

public:
int totalNQueens(int n) {
vector<int> forward(2*n-1), backward(2*n-1), cols(n);
return search(n, 0, forward, backward, cols);
}
};
``````

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