N-Queens LeetCode 51 — Backtracking Guide

LeetCode 51 — N-Queens — asks you to place n queens on an n × n chessboard such that no two queens attack each other. Two queens attack each other if they share the same row, the same column, or the same diagonal (either direction). You must return all distinct solutions as board configurations, where each configuration is a list of n strings using "Q" for a queen and "." for an empty cell.

The output for n = 4 contains two solutions: [".Q..", "...Q", "Q...", "..Q."] and ["..Q.", "Q...", "...Q", ".Q.."]. For larger n the number of solutions grows quickly — n = 8 has 92 distinct solutions. The problem tests your ability to enumerate all valid configurations systematically without missing any or generating duplicates.

This is a classic constraint satisfaction problem and one of the canonical examples for backtracking. Unlike problems with a single optimal answer, N-Queens requires exploring the entire solution space while pruning branches that violate constraints as early as possible.

The brute-force approach would try placing queens in every possible subset of n cells on the n × n board and checking validity — roughly C(n², n) combinations. For n = 8 that is over 4 billion subsets. Backtracking dramatically reduces this by placing queens one row at a time and pruning the search tree the moment a constraint is violated.

At each row we try placing a queen in each of the n columns. Before placing, we check whether that column or either diagonal is already threatened by a previously placed queen. If yes, we skip that column immediately. If no, we place the queen, recurse to the next row, and then remove the queen when we backtrack. This reduces the search space from exponential to roughly n! explored states.

The key insight is that we never need to try more than n columns per row, and many of those are pruned before recursing. For n = 8, the actual number of nodes explored is in the thousands, not billions — a dramatic improvement from the naive approach.

The efficient implementation uses three sets to track which columns and diagonals are currently threatened by placed queens. A naive approach would scan all previously placed queens to check conflicts — O(n) per check. With sets, every conflict check becomes O(1) average, and placing or removing a queen from the tracking structures is also O(1).

The three sets are: cols (threatened columns), diag (threatened diagonals identified by row - col), and anti_diag (threatened anti-diagonals identified by row + col). When placing a queen at (row, col), we add col to cols, row - col to diag, and row + col to anti_diag. When backtracking, we remove all three. Before placing, we check that none of the three values are already in their respective sets.

This set-based approach scales well because set membership tests in Python and Java hash sets are O(1) amortized. The total work per placement and removal is constant regardless of how many queens are already on the board — a significant improvement over scanning all prior placements.

The most elegant part of this solution is how diagonals are identified. A standard chessboard diagonal runs from top-left to bottom-right. Along any such diagonal, as you move one cell right (col + 1), you also move one cell down (row + 1). The difference row - col remains constant for all cells on the same diagonal. So the value row - col uniquely identifies a top-left-to-bottom-right diagonal.

Anti-diagonals run from top-right to bottom-left. Along any anti-diagonal, as you move one cell right (col + 1), you move one cell up (row - 1). The sum row + col remains constant for all cells on the same anti-diagonal. So the value row + col uniquely identifies a top-right-to-bottom-left anti-diagonal.

These two observations compress the 2D diagonal problem into two 1D set lookups. Instead of checking whether two cells (r1, c1) and (r2, c2) lie on the same diagonal — which requires comparing r1 - c1 == r2 - c2 and r1 + c1 == r2 + c2 — you just store the identifier in a set when placing and look it up when checking. The set contains at most n identifiers at any time, one per row already processed.

When the recursion reaches row == n, all n queens have been placed successfully. At this point we need to convert the current placement into the required output format: a list of n strings, each of length n, with "Q" at the queen's column position and "." everywhere else.

The placement state is typically tracked as a list queens[] where queens[row] = col records which column the queen in that row occupies. To build the board, iterate over each row, create a string of n dots, replace the character at position queens[row] with "Q", and append the string to the current board. A compact Python one-liner is ["." * c + "Q" + "." * (n - c - 1) for c in queens].

The board construction is O(n²) per solution since we write n strings of length n. This is acceptable because the number of valid solutions is at most O(n!) and each requires O(n²) to record. The board building step does not affect the asymptotic complexity of the backtracking search itself.

In Python, the solve function initializes three sets and an empty results list, then calls backtrack(0). The backtrack(row) function loops over columns 0 to n-1, skips threatened positions using set membership checks, places the queen by updating all three sets and a queens[] list, recurses with backtrack(row + 1), and removes the queen when done. When row == n, it appends the board construction result to results. Time complexity is O(n!) for the backtracking and O(n²) per solution for board building. Space complexity is O(n²) for all solutions stored, plus O(n) for the recursion stack.

In Java, the same logic applies using HashSet<Integer> for cols, diag, and antiDiag, and a List<String> for results. The private void backtrack(int row, int n, int[] queens) method follows the same pattern. Board construction uses a char array of n dots, places the queen character, and creates a new String from the array for each row. The public List<List<String>> solveNQueens(int n) method initializes the data structures and returns results after calling backtrack.

Both implementations use iterative board construction and recursive backtracking. There is no memoization because no subproblems repeat — each path through the search tree is unique. The algorithm is purely exploratory with constraint-based pruning, not dynamic programming.

Sudoku Solver (LeetCode 37) uses the same three-set conflict tracking idea applied to a 9 × 9 grid with rows, columns, and 3 × 3 boxes instead of diagonals. The structure is nearly identical — try a digit, check for conflicts using sets, recurse, backtrack. Understanding N-Queens makes Sudoku Solver significantly easier to approach.

Generate Parentheses (LeetCode 22), Combination Sum (LeetCode 39), and Permutations (LeetCode 46) are all backtracking problems where the choice space at each step is small and constraints are checked before recursing. The pattern of "make choice, recurse, undo choice" is the universal template shared by all these problems and by N-Queens.

Palindrome Partitioning (LeetCode 131) combines backtracking with string constraint checking. The backtracking family — N-Queens, Sudoku, permutations, combinations, palindrome partitioning, generate parentheses — is one of the most important problem families for coding interviews. Mastering the set-based conflict tracking pattern in N-Queens provides a strong foundation for all of them.