# My code : 40ms 1.Using row,column,diagonal bit map for fast check. 2. Using stack for DFS.

• ``````class Solution {
public:
struct Point
{
int x;
int y; // row
int state;
// 0 push next level node or end
// 1 try same level next node
Point(int px, int py):
x(px),
y(py)
{
state = 0;
}
};
int m_n;
std::vector<int> col;
std::vector<int> row;
std::vector<int> dia[2];
// 0 y- x = n
// 1 y + x = n
void Set(const Point& p)
{
int x = p.x;
int y = p.y;
col[x] = 1;
row[y] = 1;
int d0 = y - x + m_n -1;
int d1 = x + y;
dia[0][d0] = 1;
dia[1][d1] = 1;
}
bool Check(const Point& p)
{
int x = p.x;
int y = p.y;
int d0 = y - x + m_n -1;
int d1 = x + y;
if (col[x] == 0 && row[y] == 0 && dia[0][d0] == 0 && dia[1][d1] == 0)
{
return true;
}
return false;
}
void Remove(const Point& p)
{
int x = p.x;
int y = p.y;
int d0 = y - x + m_n -1;
int d1 = x + y;

col[x] = 0;
row[y] = 0;
dia[0][d0] = 0;
dia[1][d1] = 0;
}
void Add(vector<vector<string> >& res, std::stack<Point> S)
{
vector<string> vec1;
res.push_back(vec1);
vector<string>& vec = res[res.size() - 1];

vector<Point> vp;
while(!S.empty())
{
vp.push_back(S.top());
S.pop();
}
vec.resize(m_n);
for (int i = 0; i < vp.size(); i++)
{

string& s = vec[i];
s.resize(m_n);
for(int j = 0; j < m_n; j++)
{
if (j == vp[i].x)
{
s[j] = 'Q';
}
else
{
s[j] = '.';
}
}

}
}
vector<vector<string> > solveNQueens(int n) {
std::stack<Point> S;
vector<vector<string> > res;
m_n = n;
if (n < 1)
{
return res;
}
if (n == 1)
{
vector<string> vec;
vec.push_back("Q");
res.push_back(vec);
return res;
}
col.resize(n);
row.resize(n);
dia[0].resize(2*n);
dia[1].resize(2*n);
for (int i = 0; i < n; i++)
{
col[i] = 0;
row[i] = 0;

}
for (int i = 0; i < 2*n; i++)
{
dia[0][i] = 0;
dia[1][i] = 0;
}

S.push(Point(0,0));
Set(S.top());
while(!S.empty())
{
Point& p = S.top();
if (p.state == 0)
{
p.state = 1;
if (p.y == n - 1)
{
}
else
{
int y = p.y + 1;
for (int x = 0; x < n; x++)
{
if (Check(Point(x, y)))
{
S.push(Point(x, y));
Set(S.top());
break;
}
}
}
}
else if (p.state == 1)
{
int y = p.y;
int x = p.x + 1;
Remove(p);
S.pop();
for (; x < n; x++)
{
if (Check(Point(x, y)))
{
S.push(Point(x, y));
Set(S.top());
break;
}
}
}
}
return res;
}
};``````

• This post is deleted!

• Space complexity : Instead of using a 2D array to represent the chess board, i am using a 1D array , the index of which would represent the row number and the value of arr at row index will be the column number for the correct position of the queen.

i.e

``````       Instead of doing  arr[row][col]=1
i am using arr[row]=col ;               where queen is positioned at (row,col);
``````

Logic : DFS for every column number ,ranging from 0 to n-1, for all the rows from 0 to n-1 and check the validity of queen position for every row,col combination(using isSafe function)

isSafe function : It checks whether the queen in current position(r,c) is being attacked by any of the r-1 queens positioned in row numbers 0 through r-1.

`````` class Solution {
public:
vector < vector <string> > sol;
int limit;

vector<string> toChessString(vector<int> arr)
{
string s(arr.size(),'.');
vector<string> ans(arr.size(),s);

for(int i=0 ; i<arr.size() ; i++)
ans[i][arr[i]]='Q';

return ans;
}

bool isSafe(vector<int> arr, int r , int c )
{
int check;
for(int row=r-1,ldia=c-1,rdia=c+1 ; row>=0 ; row--,ldia--,rdia++)
{
check=arr[row];

if(check==c || check==ldia || check==rdia)
return false;
}
return true;
}

void solveNqueen(vector<int> arr , int r , int c)
{
if(r==limit)
sol.push_back(toChessString(arr));

else
{
for(int col=c ; col<limit ; col++)
{
arr[r]=col;

if(isSafe(arr,r,col))
solveNqueen(arr,r+1,0);
}
}
}

vector<vector<string> > solveNQueens(int n) {
vector<int> arr(n,0);
limit=n;
solveNqueen(arr,0,0);

return sol;
}
};``````

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