Backtracking

N-Queens

Place queens row by row. For each row, try each column. Check if the position conflicts with already-placed queens (same column or diagonal). If valid, recurse to the next row. If not, try the next column.

O(n!)

O(n)

say this out loud

One queen per row by construction, so I only need to track occupied columns and the two diagonals, and each of those is an O(1) lookup.

How It Works

N-Queens places one queen per row, which automatically satisfies the row constraint and reduces each recursive level to picking a column. For the current row, try each column; a placement is valid if no earlier queen shares its column, its main diagonal, or its anti-diagonal. Rather than scanning the board, keep three hash sets (columns, row - col values, and row + col values) so validity checks are O(1). Place, add to the sets, recurse to the next row, then remove and try the next column.

The diagonal encoding is the key insight: all cells on the same main diagonal share row - col, and all cells on an anti-diagonal share row + col. Search remains exponential in the worst case, roughly O(n!) branching, but constraint propagation through the three sets prunes most branches within a few rows. Space is O(n) for the sets and recursion stack.

Step-by-Step Visualization

Place 4 queens on a 4 by 4 board so none attack each other. One row at a time, so rows can never clash by construction

placed0

1/11

Code

Java

static List<List<String>> solveNQueens(int n) {
  List<List<String>> result = new ArrayList<>();
  Set<Integer> cols = new HashSet<>(), diag1 = new HashSet<>(), diag2 = new HashSet<>();
  char[][] board = new char[n][n];
  for (char[] row : board) Arrays.fill(row, '.');

  backtrack(0, n, board, cols, diag1, diag2, result);
  return result;
}

static void backtrack(int row, int n, char[][] board, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, List<List<String>> result) {
  if (row == n) { result.add(Arrays.stream(board).map(String::new).collect(java.util.stream.Collectors.toList())); return; }
  for (int col = 0; col < n; col++) {
    if (cols.contains(col) || d1.contains(row-col) || d2.contains(row+col)) continue;
    board[row][col] = 'Q';
    cols.add(col); d1.add(row-col); d2.add(row+col);
    backtrack(row + 1, n, board, cols, d1, d2, result);
    board[row][col] = '.';
    cols.remove(col); d1.remove(row-col); d2.remove(row+col);
  }
}

Tips & Gotchas

1Place queens row by row

2Track columns, left diagonals (r-c), right diagonals (r+c)

3If no valid column in a row, backtrack

Practice Problems

1N-Queens
2N-Queens II
3Sudoku Solver
4Beautiful Arrangement

About the Backtracking Pattern

Systematically explore all possible solutions by making choices one at a time. If a choice leads to a dead end, undo it (backtrack) and try the next option. You are exploring a decision tree: go deep, come back up when stuck.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

Why place queens row by row instead of trying arbitrary cells?

Exactly one queen must occupy each row, so fixing one row per recursion level bakes the row constraint into the search structure and shrinks the space from choosing n cells among n^2 to choosing one column per row. It also makes the depth of recursion exactly n, simplifying termination.

How do row - col and row + col identify diagonals?

Moving one step down-right leaves row - col unchanged, so every cell on a main diagonal shares that value; moving down-left leaves row + col unchanged for anti-diagonals. Storing these two numbers in hash sets turns diagonal-conflict checks into O(1) lookups instead of scanning the board.