Hints — p40 N-Queens

Hint 1. Place queens row by row: row 0 first, then row 1, etc. This guarantees exactly one queen per row by construction — no row-attacker check needed.

Hint 2. For column safety: maintain a set cols of occupied columns. Before placing at (r, c), check c not in cols. After backtrack, remove.

Hint 3. For diagonal safety, two key invariants:

• Squares on the same / diagonal share the same r + c.
• Squares on the same \ diagonal share the same r - c.

So maintain two more sets: diag (values r + c) and anti (values r - c).

Hint 4. Skeleton:

def backtrack(r):
    if r == n:
        record solution; return
    for c in range(n):
        if c in cols or r+c in diag or r-c in anti: continue
        place; backtrack(r+1); unplace

Store queens[r] = c (a list of column indices). Build the board strings ONLY on success.

Hint 5. Bitmask optimization (Knuth): replace the three sets with three ints. Shift diag << 1 and anti >> 1 between recursion levels so diagonal attacks propagate naturally. bit & -bit extracts the lowest set bit; free ^= bit clears it. 2–3× faster.

If still stuck: see solution.py.