# N-Queens Leetcode Solution

#### ByBrokenprogrammers

Nov 30, 2022

In this post, you will know how to solve the N-Queens Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

## Problem

The n-queens puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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

```Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
```

Example 2:

```Input: n = 1
Output: [["Q"]]
```

Constraints:

• `1 <= n <= 9`

### N-Queens Leetcode Solutions in 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
```

### N-Queens Leetcode Solutions in CPP

```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] = '.';
}
}
};
```

### N-Queens Leetcode Solutions in 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;
}
}
```

Note: This problem N-Queens is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.