N Queens

Place one queen per row by trying every column for every row (n^n full placements), and only after a complete placement is built, scan all C(n,2) pairs of queens to check whether any two attack each other.

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        cols_per_row = [0] * n

        def is_valid_board():
            for r1 in range(n):
                for r2 in range(r1 + 1, n):
                    c1, c2 = cols_per_row[r1], cols_per_row[r2]
                    if c1 == c2 or abs(c1 - c2) == abs(r1 - r2):
                        return False
            return True

        def build(row):
            if row == n:
                if is_valid_board():
                    result.append([
                        '.' * c + 'Q' + '.' * (n - c - 1) for c in cols_per_row
                    ])
                return
            for col in range(n):
                cols_per_row[row] = col
                build(row + 1)

        build(0)
        return result

Places all n^n full boards before ever checking validity, and each check costs O(n^2) — wasted effort, since a queen placed in row 2 might already conflict with row 0, making every one of the n^(n-2) boards built underneath it doomed.

Place queens row by row, but check safety before descending into the next row: track which columns, and which of the two diagonal families, already have a queen. A cell (r, c) lies on the same “/” diagonal as any other cell with the same r + c, and the same “\” diagonal as any other cell with the same r - c — so three sets are enough to check safety in O(1). The moment a row has no safe column left, that whole branch is abandoned immediately instead of being built out fully.

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        cols = set()
        diag1 = set()  # r - c
        diag2 = set()  # r + c
        board = [['.'] * n for _ in range(n)]

        def backtrack(row):
            if row == n:
                result.append([''.join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue  # unsafe: shares a column or diagonal with an existing queen
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = 'Q'

                backtrack(row + 1)

                board[row][col] = '.'  # backtrack: undo the placement
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        backtrack(0)
        return result

Play the search below — the trace is generated by replaying the exact code above, so the board can never disagree with it. Watch the three attack sets in the side panel knock unsafe columns out of a row in one lookup each, and what happens when a row has nowhere left to go:

Both walls the search hits are visible in the trace: row 2 under queens at (0, 0) and (1, 2), then row 3 under (0, 0), (1, 3), and (2, 1), each die with zero placements — the sets judge a whole row before anything beneath it is explored. Backing out of column 0 entirely, row 0’s column 1 sails straight down to solution 1, [".Q..","...Q","Q...","..Q."] — one of the two solutions the example expects. The second solution, ["..Q.","Q...","...Q",".Q.."], is found symmetrically when row 0 backtracks again and tries column 2.

Why it is correct: a queen is only ever placed in a column/diagonal combination not already occupied, so every complete board reaching row == n is conflict-free by construction; conversely every valid board can be built by placing its queens row by row in this order, so nothing is missed. Complexity: row 0 has n choices, row 1 has at most n - 1 remaining safe columns, and so on — bounding the search by O(n!) time in the worst case (far better than the brute force’s n^n full placements, since unsafe branches are cut off immediately rather than fully built and checked afterward). The three sets and the board are O(n) and O(n^2) respectively, but the recursion depth itself — the dominant auxiliary cost per active path — is O(n) space.