C++ solution - DFS - easy understanding

• ``````int totalNQueens(int n) {
vector<bool> col(n, true);
vector<bool> anti(2*n-1, true);
vector<bool> main(2*n-1, true);
vector<int> row(n, 0);
int count = 0;
dfs(0, row, col, main, anti, count);
return count;
}
void dfs(int i, vector<int> &row, vector<bool> &col, vector<bool>& main, vector<bool> &anti, int &count) {
if (i == row.size()) {
count++;
return;
}
for (int j = 0; j < col.size(); j++) {
if (col[j] && main[i+j] && anti[i+col.size()-1-j]) {
row[i] = j;
col[j] = main[i+j] = anti[i+col.size()-1-j] = false;
dfs(i+1, row, col, main, anti, count);
col[j] = main[i+j] = anti[i+col.size()-1-j] = true;
}
}
}``````

• Nice job!
I think row is useless, delete it is ok.

``````class Solution {
public:
int totalNQueens(int n) {

int count = 0;
vector<bool> cols(n, true);
vector<bool> main(2 * n - 1, true);
vector<bool> anti(2 * n - 1, true);
helper(0, count, cols, main, anti);
return count;
}
private:
void helper(int s, int& count, vector<bool>& cols, vector<bool>& main, vector<bool>& anti)
{
if (s == cols.size())
{
count++;
return;
}
for (int i = 0; i < cols.size(); i++)
{
if (cols[i] && main[s + i] && anti[s + cols.size() - 1 - i])
{
cols[i] = main[s + i] = anti[s + cols.size() - 1 - i] = false;
helper(s + 1, count, cols, main, anti);
cols[i] = main[s + i] = anti[s + cols.size() - 1 - i] = true;
}
}
}
};
``````

And I want to share my 4ms Solution. The ideas are same but the diagonal conflict checking method diffes.

``````class Solution {
public:
int totalNQueens(int n) {

int count = 0;
vector<bool> mark(n);
vector<int> cols(n, -1);
for (int i = 0; i < n; i++)
{
cols[0] = i;
mark[i] = true;
helper(1, n, count, mark, cols);
cols[0] = -1;
mark[i] = false;
}
return count;
}
private:
void helper(int s, int n, int& count, vector<bool>& mark, vector<int>& cols)
{
if (s == n)
{
count++;
return;
}
for (int i = 0; i < n; i++)
{
if (!mark[i])
{
bool mark2 = true;
for (int k = 0; k < s; k++)
{
if (abs(s - k) == abs(i - cols[k]))
{
mark2 = false;
break;
}
}
if (mark2)
{
cols[s] = i;
mark[i] = true;
helper(s + 1, n, count, mark, cols);
cols[s] = -1;
mark[i] = false;
}
}
}
}
};
``````

• Why can (i+j) and (i+col.size()-1-j) prove two elements are on the diagonal ?Could you prove this formula?

• @lchen77
I find a mistake , if (col[j] && main[i+j] && anti[i+col.size()-1-j])should be if (col[j] && anti[i+j] && main[i+col.size()-1-j])
it means that your main and anti should exchange .

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