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)

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

4-Queens: place queens so none attack each other

Board4×4 grid

1/3

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. Think of it as exploring a decision tree — you go deep, and 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.