LeetCode 51 · Hard · Backtracking

N-Queens

Place n queens on an n × n chessboard so that no two share a row, a column or a diagonal, and return every such board, drawn with Q and ..

O(n!)time
O(n²)space for the board
3 setscol, r + c, r − c in O(1)

n from 1 to 4 · every tried square is a tree node, so n = 4 already grows 61 nodes and n = 5 would need 221

colposDiagnegDiag

board green Q = queen · faded = attacked · yellow row = row r · arrow = the queen that blocks the square

board rows so far the partial answer

decision tree depth r places the queen of row r · node = (row, col) · dashed = attacked, skipped

res 0 boards · queen column per row

private Set<Integer> col = new HashSet<>();private Set<Integer> posDiag = new HashSet<>();private Set<Integer> negDiag = new HashSet<>();private List<List<String>> res;private char[][] board;private int n;public List<List<String>> solveNQueens(int n) { this.n = n; res = new ArrayList<>(); board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, '.'); } backtrack(0); return res;}private void backtrack(int r) { if (r == n) { List<String> copy = new ArrayList<>(); for (char[] row : board) { copy.add(new String(row)); } res.add(copy); return; } for (int c = 0; c < n; c++) { if (col.contains(c) || posDiag.contains(r + c) || negDiag.contains(r - c)) { continue; } col.add(c); posDiag.add(r + c); negDiag.add(r - c); board[r][c] = 'Q'; backtrack(r + 1); col.remove(c); posDiag.remove(r + c); negDiag.remove(r - c); board[r][c] = '.'; }}
r, c
—
col
{}
posDiag (r+c)
{}
negDiag (r−c)
{}
res.size()
0

Why it works

  1. Brute force picks n squares out of n² and checks every pair: C(n², n) boards, already 1.9 million for n = 6. Even one queen per row (nⁿ boards) checked at the end is far too many.
  2. One queen per row, checked as you go. Row r only tries columns that no earlier queen attacks. A conflict cuts the whole subtree below that square, so the search never builds an invalid prefix.
  3. Diagonals have a constant. Squares on one ↗ diagonal share r + c; on one ↘ diagonal they share r − c. Three sets make each safety check O(1). Row r has at most n − r safe columns, so the tree is bounded by n!; the board costs O(n²).
  4. Pitfall: undo all four changes. After the call returns, remove c, r + c and r − c and reset the square to '.'. Missing one leaves a phantom attacker and later rows lose valid squares.
  5. Follow-up, N-Queens II (52): return only the count. Same search with a counter; bitmasks for the three sets make it very fast.