Preamble

N-Queens is classic constraint satisfaction: place N queens on an N×N board so no two share a row, column, or diagonal. Eight and nine differ only in search width—the pattern is DFS + pruning (backtracking).

State representation

Rows are placed one at a time; store column index per row. Conflicts check columns in O(1) with a set, and diagonals via r - c and r + c families—also O(1) membership with sets.

def n_queens(n):
    # Each solution: length-n list — index = row, value = column.
    out = []

    def backtrack(row, cols, diag, anti, board):
        if row == n:
            out.append(board[:])
            return
        for c in range(n):
            d1, d2 = row - c, row + c
            if c in cols or d1 in diag or d2 in anti:
                continue
            cols.add(c)
            diag.add(d1)
            anti.add(d2)
            board.append(c)
            backtrack(row + 1, cols, diag, anti, board)
            board.pop()
            cols.remove(c)
            diag.remove(d1)
            anti.remove(d2)

    backtrack(0, set(), set(), set(), [])
    return out

Pruning beats brute force

Clarity beats micro-optimizations until N forces bitmask tricks. The lesson generalizes: search with cheap rejection wins naive enumeration.

Conclusion

Backtracking is DFS with undo. Dijkstra’s Algorithm with heapq in Python implements Dijkstra with heapq.