## N-Queens

• Time:O(n \cdot n!)
• Space:|\texttt{ans}|

## C++

class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
dfs(n, 0, vector<bool>(n), vector<bool>(2 * n - 1), vector<bool>(2 * n - 1),
vector<string>(n, string(n, '.')), ans);
return ans;
}

private:
void dfs(int n, int i, vector<bool>&& cols, vector<bool>&& diag1,
vector<bool>&& diag2, vector<string>&& board,
vector<vector<string>>& ans) {
if (i == n) {
ans.push_back(board);
return;
}

for (int j = 0; j < n; ++j) {
if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
continue;
board[i][j] = 'Q';
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
dfs(n, i + 1, move(cols), move(diag1), move(diag2), move(board), ans);
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
board[i][j] = '.';
}
}
};


## JAVA

class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> ans = new ArrayList<>();
char[][] board = new char[n][n];

for (int i = 0; i < n; ++i)
Arrays.fill(board[i], '.');

dfs(n, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], board, ans);
return ans;
}

private void dfs(int n, int i, boolean[] cols, boolean[] diag1, boolean[] diag2, char[][] board,
List<List<String>> ans) {
if (i == n) {
return;
}

for (int j = 0; j < cols.length; ++j) {
if (cols[j] || diag1[i + j] || diag2[j - i + n - 1])
continue;
board[i][j] = 'Q';
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = true;
dfs(n, i + 1, cols, diag1, diag2, board, ans);
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = false;
board[i][j] = '.';
}
}

private List<String> construct(char[][] board) {
List<String> listBoard = new ArrayList<>();
for (int i = 0; i < board.length; ++i)
return listBoard;
}
}


## Python

class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
cols = [False] * n
diag1 = [False] * (2 * n - 1)
diag2 = [False] * (2 * n - 1)

def dfs(i: int, board: List[int]) -> None:
if i == n:
ans.append(board)
return

for j in range(n):
if cols[j] or diag1[i + j] or diag2[j - i + n - 1]:
continue
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = True
dfs(i + 1, board + ['.' * j + 'Q' + '.' * (n - j - 1)])
cols[j] = diag1[i + j] = diag2[j - i + n - 1] = False

dfs(0, [])
return ans