N-Queens Problem: How Would You Solve It?
Learn how to solve the N-Queens problem with backtracking, constraint tracking, and pruning, plus a full Python implementation.
Expected Interview Answer
The N-Queens problem is solved with backtracking: place queens column by column, and at each row try every column, only proceeding if the position is not attacked by any previously placed queen, backtracking immediately when no column works.
You track which columns and which two diagonals are already occupied, usually with three boolean sets or bitmasks, so each placement check is O(1) instead of rescanning the board. Placing a queen in a given row means trying each column left to right, skipping any column already under attack, then recursing into the next row with that column and its diagonals marked used. If a row runs out of valid columns the recursion backtracks, un-marking the last placement and trying the next option in the previous row. This prunes the search space far below the naive n^n placements, giving a working solution even though the worst case is still exponential.
- Explores only valid partial boards, pruning early
- O(1) attack checks via column/diagonal sets
- Generalizes to counting or listing all solutions
- Classic template for constraint-satisfaction backtracking
AI Mentor Explanation
Placing queens row by row is like a fielding coach assigning one fielder to each row of the ground, one row at a time, skipping any spot already covered by an existing fielder's throwing lane. If a row has no safe spot left, the coach undoes the last fielder placed and tries a different spot in the row before it, exactly like backtracking. The coach never plans the whole field at once; each assignment only checks the fielders already on the ground. This row-by-row, undo-when-stuck process is what keeps the search efficient instead of testing every possible arrangement.
Step-by-Step Explanation
Step 1
Place row by row
Recurse one board row at a time, choosing which column to place a queen in for that row.
Step 2
Track constraints in O(1) sets
Maintain used columns, and used "row+col" and "row-col" diagonals to check attacks instantly.
Step 3
Recurse or backtrack
If a column is safe, mark it used and recurse to the next row; if no column works, backtrack to the previous row.
Step 4
Collect solutions
When all n rows are filled, record the board; unmark constraints as you unwind to explore other placements.
What Interviewer Expects
- Recognize this as backtracking, not brute force
- Explain the O(1) column/diagonal constraint tracking
- Describe when and how backtracking happens
- State the time complexity is exponential but heavily pruned in practice
Common Mistakes
- Rescanning the whole board on every placement instead of tracking sets
- Forgetting to unmark constraints when backtracking (leaves stale state)
- Confusing row/col diagonal formulas (row+col vs row-col)
- Not handling the case where no solution exists for certain small n (n=2, n=3)
Best Answer (HR Friendly)
“N-Queens is about placing queens one row at a time so none of them attack each other, and if I get stuck partway through, I undo just the last decision and try something else instead of starting over. I keep track of which columns and diagonals are already used so I can check a new spot instantly, which is what makes the search fast enough to actually work.”
Code Example
def solve_n_queens(n):
solutions = []
cols, diag1, diag2 = set(), set(), set()
placement = []
def backtrack(row):
if row == n:
solutions.append(placement[:])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col); diag1.add(row - col); diag2.add(row + col)
placement.append(col)
backtrack(row + 1)
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
placement.pop()
backtrack(0)
return solutionsFollow-up Questions
- How would you count solutions without storing every board?
- How would you solve this with bitmasks instead of sets for speed?
- How is N-Queens an example of the general backtracking template?
- How would you find just one valid solution instead of all of them?
MCQ Practice
1. What two extra diagonal identifiers are tracked alongside columns in N-Queens backtracking?
Every cell on the same "/" diagonal shares row+col, and every cell on the same "\" diagonal shares row-col.
2. What triggers a backtrack step in the N-Queens search?
When no column in the current row is free of column/diagonal conflicts, the algorithm undoes the previous row's placement and tries again.
3. Why is tracking columns and diagonals as sets an improvement over rescanning the board?
Set membership checks are O(1), so verifying a candidate column is safe no longer requires scanning all previously placed queens.
Flash Cards
What search technique solves N-Queens? — Backtracking: place one queen per row, undo and retry when a row has no safe column.
What three things must a placement avoid? — Sharing a column, or either diagonal, with any already-placed queen.
How are diagonals identified in O(1)? — row+col identifies one diagonal direction, row-col identifies the other.
Is N-Queens worst-case polynomial? — No, it is exponential in the worst case, but pruning makes it practical for real board sizes.