# Accepted 4ms c++ solution use backtracking and bitmask, easy understand.

• In this problem, we can go row by row, and in each position, we need to check if the `column`, the `45° diagonal` and the `135° diagonal` had a queen before.

Solution A: Directly check the validity of each position, 12ms:

``````class Solution {
public:
std::vector<std::vector<std::string> > solveNQueens(int n) {
std::vector<std::vector<std::string> > res;
std::vector<std::string> nQueens(n, std::string(n, '.'));
solveNQueens(res, nQueens, 0, n);
return res;
}
private:
void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col)
if (isValid(nQueens, row, col, n)) {
nQueens[row][col] = 'Q';
solveNQueens(res, nQueens, row + 1, n);
nQueens[row][col] = '.';
}
}
bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) {
//check if the column had a queen before.
for (int i = 0; i != row; ++i)
if (nQueens[i][col] == 'Q')
return false;
//check if the 45° diagonal had a queen before.
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
if (nQueens[i][j] == 'Q')
return false;
//check if the 135° diagonal had a queen before.
for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
if (nQueens[i][j] == 'Q')
return false;
return true;
}
};
``````

Solution B: Use flag vectors as bitmask, 4ms:

The number of columns is `n`, the number of 45° diagonals is `2 * n - 1`, the number of 135° diagonals is also `2 * n - 1`. When reach `[row, col]`, the column No. is `col`, the 45° diagonal No. is `row + col` and the 135° diagonal No. is `n - 1 + col - row`. We can use three arrays to indicate if the column or the diagonal had a queen before, if not, we can put a queen in this position and continue.

NOTE: Please don't use `vector<bool> flag` to replace `vector<int> flag` in the following C++ code. In fact, `vector<bool>` is not a STL container. You should avoid to use it. You can also get the knowledge from here and here.

``````/**    | | |                / / /             \ \ \
*    O O O               O O O               O O O
*    | | |              / / / /             \ \ \ \
*    O O O               O O O               O O O
*    | | |              / / / /             \ \ \ \
*    O O O               O O O               O O O
*    | | |              / / /                 \ \ \
*   3 columns        5 45° diagonals     5 135° diagonals    (when n is 3)
*/
class Solution {
public:
std::vector<std::vector<std::string> > solveNQueens(int n) {
std::vector<std::vector<std::string> > res;
std::vector<std::string> nQueens(n, std::string(n, '.'));
std::vector<int> flag_col(n, 1), flag_45(2 * n - 1, 1), flag_135(2 * n - 1, 1);
solveNQueens(res, nQueens, flag_col, flag_45, flag_135, 0, n);
return res;
}
private:
void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag_col, std::vector<int> &flag_45, std::vector<int> &flag_135, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col)
if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 + col - row]) {
flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 0;
nQueens[row][col] = 'Q';
solveNQueens(res, nQueens, flag_col, flag_45, flag_135, row + 1, n);
nQueens[row][col] = '.';
flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 1;
}
}
};
``````

But we actually do not need to use three arrays, we just need one. Now, when reach `[row, col]`, the subscript of column is `col`, the subscript of 45° diagonal is `n + row + col` and the subscript of 135° diagonal is `n + 2 * n - 1 + n - 1 + col - row`.

``````class Solution {
public:
std::vector<std::vector<std::string> > solveNQueens(int n) {
std::vector<std::vector<std::string> > res;
std::vector<std::string> nQueens(n, std::string(n, '.'));
/*
flag[0] to flag[n - 1] to indicate if the column had a queen before.
flag[n] to flag[3 * n - 2] to indicate if the 45° diagonal had a queen before.
flag[3 * n - 1] to flag[5 * n - 3] to indicate if the 135° diagonal had a queen before.
*/
std::vector<int> flag(5 * n - 2, 1);
solveNQueens(res, nQueens, flag, 0, n);
return res;
}
private:
void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag, int row, int &n) {
if (row == n) {
res.push_back(nQueens);
return;
}
for (int col = 0; col != n; ++col)
if (flag[col] && flag[n + row + col] && flag[4 * n - 2 + col - row]) {
flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 0;
nQueens[row][col] = 'Q';
solveNQueens(res, nQueens, flag, row + 1, n);
nQueens[row][col] = '.';
flag[col] = flag[n + row + col] = flag[4 * n - 2 + col - row] = 1;
}
}
};``````

• Thank you very for your solution-sharing and explanation. I have learned a lot from you.

• Very clear explanation~!!

``````public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res=new ArrayList<List<String>>();
String[] queens=new String[n];
char[] initial=new char[n];
Arrays.fill(initial,'.');
Arrays.fill(queens,String.valueOf(Arrays.copyOf(initial,n)));
int[] flag=new int[5*n-2];
Arrays.fill(flag,1);
slove(res,queens,flag,0,n);
return res;
}
private void slove(List<List<String>> res,String[] queens,int[] flag,int row,int n){
if(row==n){
return;
}
for(int col=0;col!=n;col++){
if(flag[col]==1 && flag[n+col+row]==1 && flag[4*n-2+col-row]==1){
flag[col]=0;
flag[n+col+row]=0;
flag[4*n-2+col-row]=0;
char[] chars=queens[row].toCharArray();

chars[col]='Q';
queens[row]=String.valueOf(chars);

slove(res,queens,flag,row+1,n);

chars=queens[row].toCharArray();
chars[col]='.';
queens[row]=String.valueOf(chars);

flag[col]=1;
flag[n+col+row]=1;
flag[4*n-2+col-row]=1;
}
}
}
}``````

• Similar to sudoko solution.

• This post is deleted!

• Thanks for sharing, very clear and easy to understand !

• with reference, the program won't need to allocate memory can copy to generate a new vector<string>

• Thanks for sharing your solution. What is (and how to analyze) the time complexity of it?

• I changed the `int` to `bool` type, I thought it won't make any difference, but result shows that `bool` is slower (about 12ms).

• In fact, `vector<bool>` is not a STL container. You should avoid to use it. You can also get the knowledge from `http://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container` and `http://stackoverflow.com/questions/670308/alternative-to-vectorbool`

• This post is deleted!

• @qkhhly
The time complexity of the improved solution which is the one with line indicators, is

• This post is deleted!

• 34 lines, 6ms. A little improvement based on your idea.
Using an int array to record the column of queens in previous rows.

class Solution {
public:

``````vector<vector<string>> solveNQueens(int n) {
vector<vector<string> > res;
vector<string> temp(n, string(n,'.'));
int dp[n];
helper(res, temp, dp, 0, n);
return res;
}
``````

private:

``````void helper(vector<vector<string> > &res, vector<string> &temp, int dp[], int row, int n){
if(row==n){
res.push_back(temp);
return;
}
for(int col=0;col<n;++col){
if(valid(dp, row, col, n)){
dp[row]=col;
temp[row][col]='Q';
helper(res, temp, dp, row+1,n);
temp[row][col]='.';
}
}
}

bool valid(int dp[], int row, int col, int n){
for(int i=0;i<row;++i){
if(dp[i]==col || abs(row-i)==abs(dp[i]-col)){
return false;
}
}
return true;
}
``````

};

• abs(row-i) == abs(dp[i]-col) is very smart.

• How is my code too slow? It applies the same logic except that it is written in java.

``````public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<List<String>>();
char[][] curr = new char[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
curr[i][j] = '.';
backtrack(ans, curr, n, 0, 0);
return ans;
}
private static void backtrack(List<List<String>>ans, char[][] curr, int left, int row, int col){
if(left==0){
List<String> temp = new ArrayList<String>();
for(int i=0;i<curr.length;i++)
}
else{
for(int i=row;i<curr.length;i++){
for(int j=col;j<curr.length;j++){
if(isValid(curr, i, j)){
curr[i][j] = 'Q';
backtrack(ans,curr,left-1, row+1, 0);
curr[i][j] = '.';
}
}
}
}
}
private static boolean isValid(char[][] curr, int row, int col){
for(int i=0;i<curr.length;i++){
if(curr[row][i]=='Q')
return false;
if(curr[i][col]=='Q')
return false;
}
int i = 1;
int n = curr.length;
while(row+i<n || col+i<n || col-i>=0 || row-i>=0){
if(row+i<n && col+i<n && curr[row+i][col+i]=='Q'
|| row+i<n && col-i>=0 && curr[row+i][col-i]=='Q'
|| row-i>=0 && col-i>=0 && curr[row-i][col-i]=='Q'
|| row-i>=0 && col+i<n && curr[row-i][col+i]=='Q')
return false;
i++;
}
return true;
}
``````

• Nice solution. Here is a 4ms Java solution, beats 99%.

Any suggestions that make it faster will be appreciated.

``````public class Solution {
// pie = row + col;
// na = n - 1 + col - row;
int[] sol;
public List<List<String>> solveNQueens(int n) {
sol = new int[n];
List<List<String>> res = new ArrayList();
DFS(res, n, 0, 0, 0, 0);
return res;
}
private void DFS(List<List<String>> res, int N, int row, int shu, int pie, int na) {
int ok = ((1 << N) - 1) & ~(shu | pie | na);
while (ok != 0) {
int p = ok & -ok;
ok ^= p;
sol[row] = p;
if (row == N - 1) {
List<String> list = new ArrayList();
for (int i = 0; i < N; i++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < N; c++) {
if ((1 << c) == sol[i]) sb.append("Q");
else sb.append(".");
}
}
} else {
DFS(res, N, row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
}
}
}
}
``````

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