In N-Queens, how does the recursion change when you only need to count solutions versus return one?
answer
- what does the recursion hand back
- an integer, a flag, or a collection
- which mode is allowed to stop early
- the working state is reused after backtracking
- short-circuit versus exhaust the tree
basics
~20 sCounting accumulates an integer and must exhaust the whole tree. Returning one solution returns a success flag that short-circuits every frame above it the moment a full placement is reached. Returning all solutions must snapshot each placement, because the working state keeps being mutated.
solid answer
~50 sThree modes, three contracts. **Count**: the base case increments a total and returns; nothing can be skipped, because a solution not visited is a solution not counted, and no copying is needed. **Find one**: the base case returns success, and every caller checks that return and propagates it immediately instead of continuing its loop — the only mode that can stop early. **Find all**: the base case appends a *copy* of the current placement; a stored reference would be wrong, because the search mutates that same working state as it backtracks, so the stored entry would end up describing a later or empty board. Cost-wise, counting saves the `O(n)` snapshot and the memory for the whole solution list, but explores exactly the same tree as find-all. Only find-one gets to stop early, and only when a solution exists: with none, the tree is exhausted anyway.
code
pseudocode · 11 linesSEARCH(row):
if row == n:
return true // a complete placement exists
for col in 0..n-1:
if attacked(row, col):
continue
mark(row, col)
if SEARCH(row + 1):
return true // stop here; do not try further columns
unmark(row, col)
return false // this row has no legal columngo deeper
Know that the same placement logic serves all three goals and that what changes is the return value: a running total, a success flag, or a collection of placements. Recall that a found placement has to be copied out.
Explain where the short-circuit goes and why each caller must test the recursive result, and explain why a stored placement must be a snapshot of the mutated working state rather than a reference to it.
Separate output volume from search volume: counting and enumerating explore the identical tree. Diagnose the classic symptom where the solution count is right but every stored placement looks the same.
Own the API shape. Decide whether callers need a count, the first feasible placement, or a stream of placements, and argue the memory consequence — holding every solution is linear in a number that grows explosively with board size.
## One search, three contracts The placement logic — one queen per row, constant-time column and diagonal tests, mark and unmark around the recursive call — is identical in all three modes. What differs is what the recursion *returns* and what the base case *does*, and those two choices decide whether the search may stop early and whether anything must be copied. ### Counting The base case adds one to a running total and returns; callers ignore the return value or accumulate a sum of child results. Every branch that survives pruning must be visited, because an unvisited complete placement is a solution silently dropped. No solution is ever materialized, so there is no copying and memory stays `O(n)` — the recursion stack and the occupancy state, nothing else. ### Returning a single solution The base case reports success. Each caller must *test* the recursive call's result and propagate success immediately rather than continuing its column loop; forgetting that test is the classic mistake that turns find-one into a full exhaustive search that happens to return the right flag. Two ways to hand the placement back cleanly: - **Snapshot at the base case**: copy the working placement into an output slot before returning success. Undoing on the way up is then harmless. - **Return before undoing**: propagate success without running the unmark step, leaving the working state intact for the caller to read. This is deliberate — the usual "always restore" discipline is a rule about branches that *failed*, and a successful terminal path is not one. What you must not do is return a bare flag and then let every frame undo its placement on the way up: the board is dismantled behind you and the caller receives an empty state. ### Returning all solutions The base case appends the current placement to a collection — and it must append a **snapshot**, not a reference to the live working state. The search continues after the append: it unmarks, tries other columns, and eventually rewrites the same positions. A stored reference would therefore describe whatever the state looked like at the end of the run, so a run finding 92 placements would report 92 identical, usually empty, boards. This is the single most common bug in the find-all shape, and it survives casual testing because the *count* comes out right. ## What each mode actually saves | Mode | Return | Can stop early? | Extra memory | Extra time per solution | |---|---|---|---|---| | Count | integer | no | `O(n)` | none | | Find one | success flag (+ snapshot) | yes | `O(n)` | one copy, once | | Find all | collection | no | `O(n * S)` for `S` solutions | `O(n)` copy each | The row worth internalizing is the middle column. Counting is *not* faster than enumerating because it "prunes more" — it prunes exactly the same, visits exactly the same nodes, and merely skips the copy and the storage. Anyone who claims counting explores a smaller tree has confused output volume with search volume. Equally, the short-circuit in find-one is not a complexity-class improvement. For board sizes with no solution at all — 2 and 3 — the flag is never set, no branch is ever cut, and the full tree is explored before the answer "none" comes back. The short-circuit pays only when a solution is reached early, which depends entirely on the order columns are tried. ## The counting-only shortcut Counting has one trick the other modes cannot borrow directly: the board's left-right mirror symmetry. Placements whose first-row queen sits in column `c` correspond one-to-one with placements whose first-row queen sits in column `n - 1 - c`, so you can search only the first half of the top row and double the result, handling the middle column separately when `n` is odd. That roughly halves the work. It is a constant-factor optimization on a still-exponential search — and it is only sound for a total, since it fabricates no actual placements to return. ## Interview register "Same recursion, different return contract. Counting returns an integer and has to exhaust the tree but never copies. Find-one returns a success flag that each caller propagates immediately, so it is the only mode that stops early — and I either snapshot at the base case or return before undoing, so the placement survives the unwind. Find-all appends a copy of the placement, because the working state is mutated as the search continues."
- How can board symmetry cut the work when you only need the count?Mirroring the board left-to-right maps every solution whose top-row queen sits in column `c` onto one with it in column `n - 1 - c`, and the map is a bijection. So search only the first half of the top row, double the total, and when `n` is odd add the middle column's count separately. That roughly halves the work without changing the exponential growth, and it is only valid for a total, not for producing the placements themselves.
- Does the short-circuit in find-one improve the worst case?No. When no placement exists — board sizes two and three, for instance — the success flag is never set, nothing is cut, and the search exhausts the tree before answering "none". The short-circuit helps only when a solution is reached early, which is a property of the column ordering, not a guarantee. The worst case is the same exponential search as counting.
saying these in an interview costs you the question
- Says counting is faster because it explores fewer nodes
- Stores a reference to the live placement instead of a copy
- Ignores the recursive call's result and keeps looping after success
- Thinks the short-circuit improves the worst case
- Claims find-all and count differ in complexity class