# 51. N-Queens

• Time: $O(n \cdot n!)$
• Space: $|\texttt{ans}|$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector> solveNQueens(int n) { vector> ans; dfs(n, 0, vector(n), vector(2 * n - 1), vector(2 * n - 1), vector(n, string(n, '.')), ans); return ans; } private: void dfs(int n, int i, vector&& cols, vector&& diag1, vector&& diag2, vector&& board, vector>& 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] = '.'; } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public List> solveNQueens(int n) { List> 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> ans) { if (i == n) { ans.add(construct(board)); 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 construct(char[][] board) { List listBoard = new ArrayList<>(); for (int i = 0; i < board.length; ++i) listBoard.add(String.valueOf(board[i])); return listBoard; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 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