N-Queens (LeetCode 51 / 52)

The problem

Place n queens on an n × n chessboard so that no two attack each other: no two share a row, a column, or a diagonal. LeetCode 52 asks how many such placements exist. LeetCode 51 asks you to return the boards themselves, each as a list of strings with Q for a queen and . for an empty square.

Input:  n = 4
Output (52): 2
Output (51): [".Q..", "...Q", "Q...", "..Q."]  and  ["..Q.", "Q...", "...Q", ".Q.."]

On a 4×4 board there are exactly two safe arrangements, mirror images of each other.

How to think about it

Start with brute force. Choose any n squares out of n² and check whether the queens are safe. For n = 8 that’s C(64, 8), about 4.4 billion placements. Hopeless.

First cut: one queen per row. Two queens in the same row attack each other, so every solution has exactly one queen in each row. Instead of choosing squares, choose a column for row 0, then a column for row 1, and so on. That shrinks the search to at most nⁿ, and since columns can’t repeat either, to n! (40,320 for n = 8).

The key insight: reject a square the moment it’s attacked, in O(1). Before placing a queen at (r, c), ask: is column c taken? Is the \ diagonal taken? Is the / diagonal taken? Every square on one \ diagonal has the same r - c, and every square on one / diagonal has the same r + c. So keep three sets, cols, d1 (for r - c) and d2 (for r + c), and the check is three set lookups. Any attacked square is skipped, and the whole sub-tree under it is never explored. That pruning is what makes N-Queens finish fast.

Which pattern is this? Backtracking with constraint pruning. The tell is “place items so that no two conflict, return all / count all”. The undo step removes the queen’s column and diagonals from the three sets.

Approach

1. Keep three sets: occupied columns, r - c diagonals, r + c anti-diagonals.
2. bt(r): if r == n, every row has a queen, so count one solution.
3. For each column c in row r: skip it if it’s in any of the three sets.
4. Otherwise add c, r - c, r + c to the sets, recurse into bt(r + 1), then remove them.
5. Call bt(0).

Solution

This version counts the solutions (LeetCode 52):

def solve_n_queens_count(n):
    cols, d1, d2 = set(), set(), set()
    count = 0
    def bt(r):
        nonlocal count
        if r == n: count += 1; return
        for c in range(n):
            if c in cols or (r - c) in d1 or (r + c) in d2: continue   # prune: attacked
            cols.add(c); d1.add(r - c); d2.add(r + c)
            bt(r + 1)
            cols.discard(c); d1.discard(r - c); d2.discard(r + c)      # undo
    bt(0); return count
# solve_n_queens_count(4) -> 2

For LeetCode 51, keep the same search and also remember the column chosen in each row, so you can draw the board at the leaf:

def solve_n_queens(n):
    cols, d1, d2 = set(), set(), set()
    queens = []; res = []                        # queens[r] = column of the queen in row r
    def bt(r):
        if r == n: res.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in queens]); return
        for c in range(n):
            if c in cols or (r - c) in d1 or (r + c) in d2: continue
            cols.add(c); d1.add(r - c); d2.add(r + c); queens.append(c)
            bt(r + 1)
            cols.discard(c); d1.discard(r - c); d2.discard(r + c); queens.pop()
    bt(0); return res
# solve_n_queens(4) -> [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]

Dry run

On n = 4, each queen placed, as (row, col):

Only 16 queens are ever placed, and count ends at 2.

Complexity

• Time: O(n!) in the worst case. Row 0 has n choices, row 1 at most n − 1, and so on. The diagonal pruning cuts far below that in practice. Building boards for LeetCode 51 adds O(n²) per solution.
• Space: O(n) for the recursion depth and the three sets.

Edge cases and pitfalls

• n = 1 has one solution; n = 2 and n = 3 have none. Your code should return 0 (or []) without special cases.
• Mixing up the diagonals. r - c is constant along \, and r + c along /. Using only one set lets diagonal attacks through.
• Checking attacks by scanning the board is O(n) per square. It still works, but the sets make it O(1), and interviewers notice.
• Forgetting to undo all three sets (and queens in the 51 version) corrupts every later branch.

Related problems

• Permutations (LeetCode 46): one queen per row with distinct columns is a permutation of columns.
• Valid Sudoku (LeetCode 36): the same “sets per row, column and box” bookkeeping.
• Word Search (LeetCode 79): another choose, recurse, undo on a board.