Canonical Deep-Dive: N-Queens

Problem: N-Queens (https://leetcode.com/problems/n-queens/) The lesson: the make-choice / recurse / undo skeleton, and pruning that turns a hopeless search into an instant one.

This is a guided walk-through, not an answer key. It explains how to think about the backtracking skeleton, the one-queen-per-row insight, and the conflict-set trick that makes pruning O(1). It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: place n queens on an n by n chessboard so that no two attack each other. Queens attack along rows, columns, and both diagonals. Return every distinct board configuration that works (LeetCode wants each board drawn as a list of strings with Q for a queen and . for an empty square). For n = 4 there are two solutions; for n = 8 there are 92.

Why brute force is hopeless, and what saves it

The naive idea is to try every way to drop n queens onto n * n squares and keep the arrangements with no conflict. That is an astronomically large number of placements even for small boards, and almost all of them are conflicts you could have ruled out immediately. This is the situation backtracking exists for: build a placement one queen at a time, and the instant a partial placement has a conflict, abandon it and back out rather than finishing a board that is already doomed. That early abandonment is pruning, and it is what makes N-Queens tractable.

Insight 1: one queen per row

The first reduction comes from the rules themselves. No two queens can share a row, so in any valid solution every row holds exactly one queen. That means you do not need to consider arbitrary square-by-square placements at all: you can place queens row by row, deciding only which column the queen in each row occupies. Now the search is “for row 0, pick a column; for row 1, pick a column that does not conflict; and so on”, and a complete placement is reached exactly when you have successfully placed a queen in every row.

This single observation collapses the branching factor from “any of the remaining squares” to “one of n columns per row”, and it gives the recursion its natural shape: recurse on the row index, and you are done when the row index reaches n.

Insight 2: conflicts are three set lookups

With one queen per row, two queens conflict only if they share a column or a diagonal. The trick that makes the check O(1) is recognizing how to name a diagonal with a single number.

Columns. Keep a set of columns that already hold a queen. A new queen at column c conflicts if c is in that set.
The “down-right” diagonals (r - c). Walk down-and-right on the board and r - c stays constant: (0,0), (1,1), (2,2) all have r - c == 0. Each distinct value of r - c names one such diagonal. So keep a set of occupied r - c values; a queen at (r, c) conflicts on this family if r - c is already in the set.
The “down-left” diagonals (r + c). Walk down-and-left and r + c stays constant: (0,2), (1,1), (2,0) all have r + c == 2. Keep a set of occupied r + c values; a queen at (r, c) conflicts on this family if r + c is already in the set.

Why the diagonal-set trick matters: without it, checking whether a square is safe means scanning previously placed queens or sweeping the board’s diagonals, which is O(n) work at every placement and buries the search in bookkeeping. With the three sets, a safety check is three O(1) membership tests, and you place a queen only on a square that passes all three. You are pruning before you recurse, never even entering a branch you would have to abandon one step later. That is the difference between “place, then discover the conflict deep in the subtree” and “never place a conflicting queen at all”.

The skeleton, in words

Walk the three-beat skeleton on this problem. You write the code; this is the shape.

State you carry: the current row index, a path recording the column chosen in each placed row (or a partially filled board), and the three conflict sets (cols, the r - c set, the r + c set).

1. Base case. If the row index equals n, every row has a queen, so the placement is complete. Record a snapshot of the solution (build the board of strings from path, and append it to results). Then return. There is no “dead branch” base case to write explicitly here, because the loop below only ever recurses into safe squares.

2. Make a choice. For the current row, loop over every column c from 0 to n - 1. Skip c immediately if c is in cols, or r - c is in the down-right set, or r + c is in the down-left set: that square is attacked, so it is pruned. Otherwise, place the queen: add c to cols, add r - c and r + c to their sets, and append c to path.

3. Recurse. Solve the next row (recurse on r + 1) with the queen in place.

4. Undo the choice. After the recursive call returns, remove c from cols, remove r - c and r + c from their sets, and pop c off path. Now the state is exactly what it was before you tried column c, so the next column in the loop starts clean.

The undo is the beat to guard. If you add to the three sets but forget to remove on the way back, the first solved branch poisons every later one and you get far too few solutions (or none). Make-choice, recurse, undo, every time.

The key insight, in one sentence

Place one queen per row, and at each row try only the columns that are not already threatened on the column or either diagonal (each checked in O(1) against a set); recurse with the queen placed, then remove it so the next column starts from a clean board. The three sets turn the safety test into three constant-time lookups, and pruning at placement time means you never walk into a branch you would only have to abandon.

Exact complexity

Time: the unconstrained search tree has n choices at the first row, n at the second, and so on, which is O(n^n) nodes; the column constraint alone bounds the leaves at n! (a permutation of columns), and the diagonal pruning cuts that dramatically further on real boards. The honest characterization is roughly O(n!) placements explored, far fewer in practice because of diagonal pruning. There is no known polynomial bound, because the number of solutions itself grows super-polynomially; this is an enumeration problem and the cost is dominated by how many partial and full placements survive pruning. Each node also does O(n) work scanning the columns of one row (and O(n) to render a solved board), but that linear factor is swamped by the size of the tree.
Space: O(n) for the recursion stack (depth equals the number of rows, at most n), plus O(n) for path and O(n) for the three conflict sets combined (each holds at most one entry per placed queen). That is O(n) of working memory, ignoring the output. The output itself can be large, since there can be many solutions, each an n by n board, but that is the answer you were asked to produce, not overhead you chose.

State the time bound carefully in an interview: say “exponential, on the order of n! after the one-queen-per-row reduction, and much less than that in practice because the diagonal sets prune most branches before they grow”. Naming both the worst case and why pruning helps is exactly the discrimination interviewers are listening for.

Your work this week

Implement N-Queens yourself, in your own work repo (for example n-queens.py). Build the recursion on the row index, carry the three conflict sets, prune at placement time, and undo every choice on the way back. Render each completed path into the list-of-strings board the problem asks for. Do not copy a solution; build it from the skeleton above.
Test the edge cases yourself: n = 1 (one trivial solution), n = 2 and n = 3 (no solutions, so an empty result), n = 4 (exactly two solutions), and n = 8 (92 solutions) to feel the search and confirm your conflict logic.
Then write the related variant N-Queens II (count the solutions instead of listing them) by returning a running count rather than building boards; convince yourself it is the same search with cheaper bookkeeping at the base case.
Commit with a five-question debrief in the message. In answer 3, state the complexity above and explain, in one sentence each, why the worst case is roughly n! and why the diagonal sets make the practical cost far smaller.

When you can explain, from memory and with no AI open, the make-choice / recurse / undo skeleton, why one queen per row is safe to assume, and why r - c and r + c name the two diagonal families, you own this problem. That explanation is exactly what an interviewer will ask for, and the skeleton is the template you will reuse on every backtracking problem this week and again in Word Search II next week.