Return every way to place n queens on an n × n chessboard so that no two share a row, a column or a diagonal. Each solution is a board of Q and . strings.
Before you code
Place exactly one queen per row; then rows can never conflict. The search is over which column each row's queen takes, and the prune is to reject any column that is already attacked.
Hints
- Keep three sets: used columns, used diagonals (
row - col) and used anti-diagonals (row + col). - For each column in the current row, skip it if it is in any set; otherwise add it to all three, recurse to the next row, then remove it.
- When the row index reaches n, build the board from the chosen columns.
- For 8 queens, count how many placements your search tries. It should be in the tens of thousands, not billions.
Production & complexity notes
When solving N-queens on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Backtracking basics to reinforce the underlying pattern.
What it practices
The choose, explore, unchoose pattern and pruning, from Backtracking basics.