N-Queens via Backtracking

N-Queens places one queen per row with bitmask or set tracking for columns and diagonals—textbook backtracking with heavy pruning.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Place row by row; for each column test attacks against previous rows only—O(n) check or O(1) with bit tricks for speed contests.

Try this in Python

def total_n_queens(n: int) -> int:
    cols: set[int] = set()
    diag1: set[int] = set()
    diag2: set[int] = set()

    def dfs(r: int) -> int:
        if r == n:
            return 1
        cnt = 0
        for c in range(n):
            if c in cols or (r + c) in diag1 or (r - c) in diag2:
                continue
            cols.add(c)
            diag1.add(r + c)
            diag2.add(r - c)
            cnt += dfs(r + 1)
            cols.remove(c)
            diag1.remove(r + c)
            diag2.remove(r - c)
        return cnt

    return dfs(0)


print(total_n_queens(4))

Common mistakes

• Diagonal indexing wrong: use r+c and r-c with offset for negatives.
• Returning strings vs lists—match required output format.

Key takeaways

• Start with set-based clarity, optimize to bits if needed.
• Preallocate list of strings builder for speed in some langs; Python list join is fine.