N-Queens
N-Queens is a hard recursion & backtracking problem solved with the 2d matrix pattern.
The best approach, optimal (backtracking with o(1) conflict sets), runs in O(n!) time and O(n²) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from backtracking with board scanning up.
Problem
Place n queens on an n × n chessboard so that no two queens attack each other (same row, column or diagonal). Return every distinct board, with Q for a queen and . for an empty square.
Examples
Example 1
- Input
n = 4- Output
[[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]
Example 2
- Input
n = 1- Output
[["Q"]]
Constraints
1 <= n <= 9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 7 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Backtracking with board scanning | O(n! · n) | O(n²) |
| Optimal (backtracking with O(1) conflict sets) | O(n!) | O(n²) |
1Backtracking with board scanning
O(n! · n)Roughly n! placements, each checked in O(n).O(n²)Place a queen row by row. Before placing, scan the column and both diagonals above for another queen.
- For each column in the current row, check safety by scanning upward.
- Place, recurse to the next row, remove.
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> out = new ArrayList<>();
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
place(b, 0, out);
return out;
}
private void place(char[][] b, int r, List<List<String>> out) {
int n = b.length;
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
out.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (!safe(b, r, c)) continue;
b[r][c] = 'Q';
place(b, r + 1, out);
b[r][c] = '.';
}
}
private boolean safe(char[][] b, int r, int c) {
for (int i = r - 1, d = 1; i >= 0; i--, d++) {
if (b[i][c] == 'Q') return false;
if (c - d >= 0 && b[i][c - d] == 'Q') return false;
if (c + d < b.length && b[i][c + d] == 'Q') return false;
}
return true;
}
}class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
out: List[List[str]] = []
b = [['.'] * n for _ in range(n)]
self.place(b, 0, out)
return out
def place(self, b: List[List[str]], r: int, out: List[List[str]]) -> None:
n = len(b)
if r == n:
board = ["".join(row) for row in b]
out.append(board)
return
for c in range(n):
if not self.safe(b, r, c):
continue
b[r][c] = 'Q'
self.place(b, r + 1, out)
b[r][c] = '.'
def safe(self, b: List[List[str]], r: int, c: int) -> bool:
d = 1
for i in range(r - 1, -1, -1):
if b[i][c] == 'Q':
return False
if c - d >= 0 and b[i][c - d] == 'Q':
return False
if c + d < len(b) and b[i][c + d] == 'Q':
return False
d += 1
return Trueclass Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> out;
vector<string> b(n, string(n, '.'));
place(b, 0, out);
return out;
}
private:
void place(vector<string>& b, int r, vector<vector<string>>& out) {
int n = b.size();
if (r == n) {
out.push_back(b);
return;
}
for (int c = 0; c < n; c++) {
if (!safe(b, r, c)) continue;
b[r][c] = 'Q';
place(b, r + 1, out);
b[r][c] = '.';
}
}
bool safe(vector<string>& b, int r, int c) {
int n = b.size();
for (int i = r - 1, d = 1; i >= 0; i--, d++) {
if (b[i][c] == 'Q') return false;
if (c - d >= 0 && b[i][c - d] == 'Q') return false;
if (c + d < n && b[i][c + d] == 'Q') return false;
}
return true;
}
};function solveNQueens(n) {
const out = [];
const b = Array.from({ length: n }, () => new Array(n).fill('.'));
place(b, 0, out);
return out;
}
function place(b, r, out) {
const n = b.length;
if (r === n) {
const board = [];
for (const row of b) board.push(row.join(""));
out.push(board);
return;
}
for (let c = 0; c < n; c++) {
if (!safe(b, r, c)) continue;
b[r][c] = 'Q';
place(b, r + 1, out);
b[r][c] = '.';
}
}
function safe(b, r, c) {
for (let i = r - 1, d = 1; i >= 0; i--, d++) {
if (b[i][c] === 'Q') return false;
if (c - d >= 0 && b[i][c - d] === 'Q') return false;
if (c + d < b.length && b[i][c + d] === 'Q') return false;
}
return true;
}2Optimal (backtracking with O(1) conflict sets)
O(n!)O(n²)The board; the three marker arrays are O(n).Keep boolean arrays for used columns, used main diagonals (index r - c + n - 1) and used anti-diagonals (index r + c). A placement is safe when all three are free, checked in O(1).
- For each column c in row r: skip if cols[c], d1[r - c + n - 1] or d2[r + c] is set.
- Mark all three, place, recurse, unmark.
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> out = new ArrayList<>();
char[][] b = new char[n][n];
for (char[] row : b) Arrays.fill(row, '.');
place(b, 0, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], out);
return out;
}
private void place(char[][] b, int r, boolean[] cols, boolean[] d1, boolean[] d2, List<List<String>> out) {
int n = b.length;
if (r == n) {
List<String> board = new ArrayList<>();
for (char[] row : b) board.add(new String(row));
out.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (cols[c] || d1[r - c + n - 1] || d2[r + c]) continue;
cols[c] = d1[r - c + n - 1] = d2[r + c] = true;
b[r][c] = 'Q';
place(b, r + 1, cols, d1, d2, out);
b[r][c] = '.';
cols[c] = d1[r - c + n - 1] = d2[r + c] = false;
}
}
}class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
out: List[List[str]] = []
b = [['.'] * n for _ in range(n)]
self.place(b, 0, [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1), out)
return out
def place(self, b: List[List[str]], r: int, cols: List[bool], d1: List[bool], d2: List[bool], out: List[List[str]]) -> None:
n = len(b)
if r == n:
board = ["".join(row) for row in b]
out.append(board)
return
for c in range(n):
if cols[c] or d1[r - c + n - 1] or d2[r + c]:
continue
cols[c] = d1[r - c + n - 1] = d2[r + c] = True
b[r][c] = 'Q'
self.place(b, r + 1, cols, d1, d2, out)
b[r][c] = '.'
cols[c] = d1[r - c + n - 1] = d2[r + c] = Falseclass Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> out;
vector<string> b(n, string(n, '.'));
vector<bool> cols(n, false), d1(2 * n - 1, false), d2(2 * n - 1, false);
place(b, 0, cols, d1, d2, out);
return out;
}
private:
void place(vector<string>& b, int r, vector<bool>& cols, vector<bool>& d1, vector<bool>& d2, vector<vector<string>>& out) {
int n = b.size();
if (r == n) {
out.push_back(b);
return;
}
for (int c = 0; c < n; c++) {
if (cols[c] || d1[r - c + n - 1] || d2[r + c]) continue;
cols[c] = d1[r - c + n - 1] = d2[r + c] = true;
b[r][c] = 'Q';
place(b, r + 1, cols, d1, d2, out);
b[r][c] = '.';
cols[c] = d1[r - c + n - 1] = d2[r + c] = false;
}
}
};function solveNQueens(n) {
const out = [];
const b = Array.from({ length: n }, () => new Array(n).fill('.'));
place(b, 0, new Array(n).fill(false), new Array(2 * n - 1).fill(false), new Array(2 * n - 1).fill(false), out);
return out;
}
function place(b, r, cols, d1, d2, out) {
const n = b.length;
if (r === n) {
const board = [];
for (const row of b) board.push(row.join(""));
out.push(board);
return;
}
for (let c = 0; c < n; c++) {
if (cols[c] || d1[r - c + n - 1] || d2[r + c]) continue;
cols[c] = d1[r - c + n - 1] = d2[r + c] = true;
b[r][c] = 'Q';
place(b, r + 1, cols, d1, d2, out);
b[r][c] = '.';
cols[c] = d1[r - c + n - 1] = d2[r + c] = false;
}
}Edge cases to test
- n = 2 and n = 3 have no solutions
Hints
Hint 1
Place one queen per row. For each column you need O(1) checks: is the column, the main diagonal (r - c) or the anti-diagonal (r + c) taken?
FAQ
What is the best time complexity for N-Queens?
Optimal (backtracking with O(1) conflict sets) runs in O(n!) time and O(n²) extra space.
Which pattern does N-Queens use?
It is a recursion & backtracking problem that uses the 2d matrix pattern.
Is there a brute force solution for N-Queens?
Yes. Backtracking with board scanning takes O(n! · n) time and O(n²) space. Place a queen row by row.
Which edge cases should I test for N-Queens?
n = 2 and n = 3 have no solutions.