Why does N-Queens search place exactly one queen per row instead of trying every board square?
answer
- count the queens against the rows
- no two queens can share a row
- constraints you never have to check
- one choice at each recursion level
- columns per row, not squares per queen
basics
~20 sEvery valid placement holds exactly one queen per row, so the search fixes the rows and chooses only a column at each level. Row conflicts become unrepresentable rather than checked, and the space shrinks from choosing n squares anywhere to n per row.
solid answer
~50 sWith n queens and n rows and no two queens allowed to share a row, the pigeonhole argument says every solution has exactly one queen in each row. So instead of choosing n squares out of the n-squared available, the recursion is indexed by row: level `r` picks a column for row `r`, and the recursion bottoms out at row `n`. This encodes the row constraint into the shape of the search rather than testing it, so it can never be violated and never has to be checked. The candidate space drops from an astronomically large set of square subsets to at most `n` branches at each of `n` levels, and once column repetition is rejected the live branches are exactly the permutations of columns. It is still exponential work — the encoding buys a much smaller tree, not a different complexity class.
go deeper
Be ready to state, in one sentence, that every solution holds exactly one queen per row and that this lets the recursion use the row as its level. Know that only a column is chosen at each step.
Explain the size difference concretely: choosing n squares out of n-squared versus n choices at each of n levels, narrowing to column permutations once repeats are rejected. Name what is left to test after the encoding.
Show that you generalize the idea: identify which constraints of a placement problem can be folded into the state representation for free, and which must remain runtime tests. Say out loud that the encoding does not change the complexity class.
Own the framing decision. Argue when a search-space encoding is worth the loss of generality — a row-indexed encoding is rigid if requirements later allow a variable number of pieces per row — and how you would keep the representation change reviewable by the team.
## The problem, stated as constraints The puzzle asks for `n` queens on an `n`-by-`n` board such that no two attack each other. A queen attacks along its row, its column, and both diagonals, so a placement is valid when all four constraints hold: no shared row, no shared column, no shared "\\" diagonal, no shared "/" diagonal. ## The naive framing, and why nobody searches that way Read literally, the task is "choose `n` of the `n^2` squares". That candidate space has `C(n^2, n)` members — for an 8-by-8 board that is `C(64, 8)`, roughly 4.4 billion candidates, almost all of which fail on the very first pair you inspect. Generating candidates and filtering them afterwards is the beginner's shape of the algorithm and it is hopeless. ## The observation that reshapes the search There are `n` queens and `n` rows, and no two queens may share a row. By the pigeonhole principle each row holds exactly one queen — not "at most", exactly, because `n` items distributed over `n` rows with no row holding two leaves no room for an empty row. That is not a heuristic or an approximation; it is a property of every solution, so committing to it loses nothing. So the recursion is indexed by row. At depth `r` the only decision is which column the queen in row `r` occupies; reaching depth `n` means a full placement has been built. Recursion depth is exactly `n`, and the auxiliary state is `O(n)` — the partial placement plus whatever occupancy structures you keep. ## What this actually buys Two distinct wins are easy to conflate: 1. **The row constraint disappears.** It is not checked at all, because the representation cannot express a violation. A constraint you can encode into the state representation costs zero to enforce. This is the transferable lesson of this family: before writing a validity test, ask whether the choice structure can make the violation unrepresentable. 2. **The space collapses.** Choosing one column per row gives `n^n` complete assignments — for `n = 8` that is about 16.7 million rather than 4.4 billion. Rejecting a column already used further restricts the live branches to permutations of `0..n-1`, of which there are `n!` (40,320 for `n = 8`). The diagonal constraints then prune most of those: only 92 valid placements exist on the standard 8-by-8 board. Seen through this lens the whole problem restates cleanly: **find a permutation `c` of the columns such that no two positions `i != j` satisfy `i + c[i] == j + c[j]` or `i - c[i] == j - c[j]`.** Every row-and-column constraint is now structural, and only the diagonals remain as a genuine test. ## What it does not buy The encoding does not make the problem tractable in the complexity-theory sense. The search tree is still exponential in `n`; the count of solutions grows fast (1, 0, 0, 2, 10, 4, 40, 92 for `n = 1..8`) and the number of nodes explored grows faster. Rows-as-levels is a constant-and-polynomial-factor massacre of the naive space, not a change of class. Nor does it order the search: it says nothing about which column to try first, and it does not by itself detect that a partial placement is already doomed several rows ahead. ## The common wrong answers - "One queen per row is an optimization that might skip solutions." It cannot skip any: every solution has that shape. - "You could equally fix one queen per column." True, and completely symmetric — the board's transpose is the same problem. The point is that fixing *either* axis is free; fixing both is what the column-occupancy test does during the search. - "Since rows are fixed, the search is polynomial." No. Fixing rows leaves `n!` orderings before diagonals prune, which is worse than exponential. ## How to say it in an interview "Every solution puts exactly one queen in each row, so I make the row the recursion level and only choose a column. That makes the row constraint unrepresentable rather than checked, cuts the candidate space from choosing `n` squares out of `n^2` down to a column per row, and reduces the problem to finding a column permutation with no two entries on a shared diagonal."
- If rows and columns are both forced to be distinct, what is left for the search to actually test?Only the two diagonal families. A row-indexed search that also rejects repeated columns is walking permutations of the columns, so the sole remaining question at each candidate is whether the new queen shares a `row + col` or `row - col` value with an already-placed one. That is why the diagonal test, not the row or column test, is the interesting part of the implementation.
- Does fixing one queen per row make the algorithm polynomial?No. Even after rows are fixed and repeated columns rejected, the live branches correspond to permutations, and there are `n!` of those. Diagonal pruning cuts the explored tree hard in practice — an 8-by-8 board has only 92 solutions — but the growth is still worse than exponential. The encoding shrinks the constant and the base, not the complexity class.
Seating one person per numbered row of a theatre: you never have to check for two people in the same row, because the seating plan cannot express it.
saying these in an interview costs you the question
- Thinks one-queen-per-row is a heuristic that may miss solutions
- Generates all n-square subsets and filters afterwards
- Claims fixing the rows makes the search polynomial
- Cannot say why the row constraint never needs checking
- Confuses the number of valid placements with the number of candidates