#51
N-Queens
Hard Backtracking row by row
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Place n queens on an n×n board so that no two attack each other (same row, column or diagonal). Return all such boards.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: place n queens so none attack each other; list all boards.
Why this works: one queen per row; track used columns and both diagonals (r - c and r + c) so each check is O(1).
Example: n = 4
row 0 col 1, row 1 col 3, row 2 col 0, row 3 col 2 ✓and its mirror: cols 2, 0, 3, 1
✦Hints open one at a time
Place exactly one queen per row; recurse row by row.
Track used columns and both diagonals: r − c (one direction) and r + c (the other).
↗Approach
At row r, try each column c that's free in cols, diag1[r − c + n − 1] and diag2[r + c]. Mark, recurse to r + 1, unmark. When r == n, convert the queen positions to strings.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
solve(0, n, new int[n], new boolean[n], new boolean[2 * n], new boolean[2 * n], res);
return res;
}
private void solve(int r, int n, int[] queenCol, boolean[] cols, boolean[] d1, boolean[] d2,
List<List<String>> res) {
if (r == n) {
List<String> board = new ArrayList<>();
for (int c : queenCol) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[c] = 'Q';
board.add(new String(row));
}
res.add(board);
return;
}
for (int c = 0; c < n; c++) {
if (cols[c] || d1[r - c + n] || d2[r + c]) continue; // attacked
cols[c] = d1[r - c + n] = d2[r + c] = true;
queenCol[r] = c;
solve(r + 1, n, queenCol, cols, d1, d2, res);
cols[c] = d1[r - c + n] = d2[r + c] = false;
}
}
}!Common mistake
Checking attacks by scanning the whole board each time — O(n) per check. The three boolean arrays make it O(1).
Complexity
- Time: O(n!).
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon