N-Queens in Coding Interviews: Backtracking with Pruning

by linkjobai

HTML

<!DOCTYPE html><html><head><meta charset="utf-8"><title>N-Queens in Coding Interviews: Backtracking with Pruning</title></head><body style="font-family:sans-serif;max-width:760px;margin:auto;line-height:1.6">
<h1>N-Queens in Coding Interviews: Backtracking with Pruning</h1>
<p>N-Queens asks you to place n queens on an n x n board so that no two attack each other, and to return every valid board (or just the count). Interviewers like it because it tests whether you can turn a brute-force search into a clean, pruned backtracking solution and explain why it is fast enough.</p>
<h2>The key observation</h2>
<p>Each row holds exactly one queen, so you place queens row by row. For each row you only need to know which columns and which diagonals are already taken. Cells on the same "down-right" diagonal share the value row - col, and cells on the same "down-left" diagonal share row + col. Three sets (cols, diag1, diag2) give O(1) conflict checks.</p>
<h2>Template</h2>
<pre>def solve_n_queens(n):
    res, board = [], []
    cols, d1, d2 = set(), set(), set()
    def place(r):
        if r == n:
            res.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
            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); board.append(c)
            place(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
    place(0)
    return res</pre>
<h2>What to say about complexity</h2>
<p>The search is bounded by roughly O(n!) placements, far below the naive n^n, and pruning by diagonals cuts it much further in practice. Space is O(n) for the sets and recursion, plus the output. If the interviewer asks only for the count (N-Queens II), mention the bitmask version: keep three integers for columns and diagonals and take the lowest free bit with avail &amp; -avail. It is the same idea with faster...