N-Queens

The Idea

Two queens in the same row always attack, so a solution has exactly one queen per row. That turns the board into a sequence of decisions: which column for row 0, then row 1, and so on.

A square is illegal if its column, its down-diagonal row - col or its up-diagonal row + col is already claimed. Three sets answer that in constant time. When a row has no legal square, the partial board above it is hopeless, so the search returns and slides the previous queen along.

Real-World Example

Assigning exam invigilators where no two may share a room, a time slot or a subject group. The same shape of constraint, and the same rescue: the moment a slot has no legal person, back up rather than continue.

The Code

def place(n, row, cols, diag, anti):
    if row == n:
        return 1                            # all rows filled: a solution
    found = 0
    for c in range(n):
        if c in cols or row - c in diag or row + c in anti:
            continue                        # square is attacked: prune
        cols.add(c); diag.add(row - c); anti.add(row + c)
        found += place(n, row + 1, cols, diag, anti)
        cols.discard(c); diag.discard(row - c); anti.discard(row + c)
    return found

print(place(4, 0, set(), set(), set()))     # -> 2
print(place(6, 0, set(), set(), set()))     # -> 4