leetExpert
Practice

N-Queens

Module 16 · Recursion & Backtracking

Problem

Place n chess queens on an n × n board so that no two queens attack each other — no two share a row, a column, or a diagonal. Return all distinct solutions, each as a board configuration. (LeetCode 51.)

Examples

Example 1

Inputn = 4Output[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2

Inputn = 1Output[["Q"]]

The two boards, drawn out:

text
.Q..    ..Q.
...Q    Q...
Q...    ...Q
..Q.    .Q..

Constraints

1 ≤ n ≤ 9.

Attempt it first

This is the module's capstone because it's the first problem where the pruning check itself is non-trivial — it's not a single counter (Generate Parentheses) or a single predicate on one substring (Palindrome Partitioning), but three simultaneous conflict conditions. Before opening anything, work out two things: (1) why can you assume, without loss of generality, exactly one queen per row (so the choice at each recursion level is which column in that row, not whether to place a queen), and (2) how would you check, in O(1), that placing a queen at (row, col) doesn't share a diagonal with any already-placed queen?