## 51.N-Queens

Then-queens puzzle is the problem of placingn_queens on an_n×_n_chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where`'Q'`and`'.'`both indicate a queen and an empty space respectively.

Example:

``````Input:
4

Output:[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
``````

Thoughts:

1. 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.

2. Optimization: Merge all arrays into one: only need one boo array flag for size 5*n - 1:n for col; 2n -1 for col + row -> diag; 2n - 1 for n - 1 - row + row for anti_diag.

Code: T: O(n^2) S: O(n)

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>>res;
vector<string>nQueens(n, string(n,'.'));
vector<int> flag_col (n , 1), flag_45(2*n -1, 1), flag_135( 2*n - 1, 1);
dfs(res, nQueens, flag_col, flag_45, flag_135, 0, n);
return res;
}
private:
void dfs(vector<vector<string>>&res, vector<string>&nQueens, vector<int> &flag_col ,vector<int> &flag_45 ,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 - row + col]){
flag_col[col] = flag_45[row + col] = flag_135[n - 1 - row + col] = 0;
nQueens[row][col] = 'Q';
dfs(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 - row + col] = 1;
}
}

}
};
``````

Code: merged T: O(n^2) S: O(n)

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>>res;
vector<string>nQueens(n, string(n,'.'));
vector<int> flag (5*n -2, 1); // n for col; 2n -1  for col + row -> diag; 2n - 1 for n - 1 - row + row for anti_diag
dfs(res, nQueens, flag, 0, n);
return res;
}
private:
void dfs(vector<vector<string>>&res, vector<string>&nQueens, 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[3*n - 1 + n - 1 - row + col]){
flag[col] = flag[n + row + col] = flag[3*n - 1 + n - 1 - row + col] = 0;
nQueens[row][col] = 'Q';
dfs(res, nQueens, flag, row + 1, n);
nQueens[row][col] = '.';
flag[col] = flag[n + row + col] = flag[3*n - 1 + n - 1 - row + col] = 1;
}
}
}
};
``````