Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: N-Queens
• Main tags: Array, Backtracking

What the problem is really asking

The board details can make this problem look more complicated than it is.

At a higher level, the task is:

• place exactly one queen in each row
• never reuse a column
• never place two queens on the same diagonal
• return every full placement that satisfies those rules

That “one queen per row” reframing is the key simplification.

Because every valid answer must use n queens on an n x n board, there is no reason to think about arbitrary squares in arbitrary order. The clean way to search is row by row.

How to derive the optimal approach

A brute-force mindset would try many board states and repeatedly ask, “Is this board still valid?”

That is too expensive.

The better way is to notice that when placing a queen in row r and column c, only three constraints matter:

• column c must be unused
• descending diagonal r - c must be unused
• ascending diagonal r + c must be unused

If those three checks are fast, then each recursive step becomes simple:

1. Pick the next row.
2. Try each column in that row.
3. Skip columns that violate one of the three constraints.
4. Place the queen, recurse, then undo the placement.

That is classic backtracking, but with strong pruning.

Instead of building full boards and validating later, the algorithm builds only partial boards that are still legal. That is why it performs well enough for a hard interview problem.

Optimal solution and practical variants

The standard optimal interview solution is row-by-row backtracking with O(1) conflict checks.

There are two common ways to implement those checks:

• Sets: store used columns, row - column, and row + column. This is the easiest version to explain and debug.
• Bitmasks: represent the same constraints with integers. This keeps the same search strategy but reduces constant factors and usually runs faster in practice.

Both versions explore essentially the same search tree. The important optimization is not a fancy data structure on its own. It is the decision to prune immediately when a row-column-diagonal conflict appears.

This note uses the clearer set-based version for the final code and explains the bitmask version as a realistic interview follow-up.

Complexity

• Time: commonly described as O(n!) in the worst case because the branching factor shrinks as columns get consumed, but the exact count depends on how much pruning happens
• Extra space: O(n) for the recursion stack, current placement, and constraint sets, excluding the returned boards
• Output space: proportional to the number of valid boards returned

For this problem, exponential search is unavoidable because the algorithm may need to enumerate many full solutions. The goal is to make each partial-state check as cheap as possible and cut dead branches early.

Python solution

class NQueensSolver:
    """Backtracking solver that builds every valid N-Queens board."""

    def __init__(self, board_size: int) -> None:
        self.board_size = board_size
        self.occupied_columns: set[int] = set()
        self.occupied_descending_diagonals: set[int] = set()
        self.occupied_ascending_diagonals: set[int] = set()
        self.queen_column_by_row: list[int] = [-1] * board_size
        self.solutions: list[list[str]] = []

    def solve(self) -> list[list[str]]:
        if self.board_size <= 0:
            return []

        self._search(row_index=0)
        return self.solutions

    def _search(self, row_index: int) -> None:
        if row_index == self.board_size:
            self.solutions.append(self._build_board())
            return

        for column_index in range(self.board_size):
            if not self._can_place_queen(
                row_index=row_index,
                column_index=column_index,
            ):
                continue

            self._place_queen(
                row_index=row_index,
                column_index=column_index,
            )
            self._search(row_index=row_index + 1)
            self._remove_queen(
                row_index=row_index,
                column_index=column_index,
            )

    def _can_place_queen(self, row_index: int, column_index: int) -> bool:
        descending_diagonal = row_index - column_index
        ascending_diagonal = row_index + column_index

        return (
            column_index not in self.occupied_columns
            and descending_diagonal not in self.occupied_descending_diagonals
            and ascending_diagonal not in self.occupied_ascending_diagonals
        )

    def _place_queen(self, row_index: int, column_index: int) -> None:
        self.queen_column_by_row[row_index] = column_index
        self.occupied_columns.add(column_index)
        self.occupied_descending_diagonals.add(row_index - column_index)
        self.occupied_ascending_diagonals.add(row_index + column_index)

    def _remove_queen(self, row_index: int, column_index: int) -> None:
        self.queen_column_by_row[row_index] = -1
        self.occupied_columns.remove(column_index)
        self.occupied_descending_diagonals.remove(row_index - column_index)
        self.occupied_ascending_diagonals.remove(row_index + column_index)

    def _build_board(self) -> list[str]:
        board_rows: list[str] = []

        for queen_column in self.queen_column_by_row:
            row_characters = ["."] * self.board_size
            row_characters[queen_column] = "Q"
            board_rows.append("".join(row_characters))

        return board_rows


class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        """LeetCode entry point."""
        solver = NQueensSolver(board_size=n)
        return solver.solve()

Interview follow-ups

How would you count the number of solutions instead of returning every board?

Use the exact same row-by-row backtracking, but replace the output list with an integer counter. Each time the recursion reaches row n, increment the counter and return. That works because the real hard part of the problem is searching only legal placements; whether the algorithm stores boards or just counts them is a separate concern.

The benefit is lower memory use and less string-building overhead. The time complexity is still exponential because the search tree is essentially the same, but the constant factors improve because completed boards do not need to be materialized.

How would you optimize this for larger n?

The usual next step is to replace the three sets with bitmasks for columns, descending diagonals, and ascending diagonals. The recursive structure does not change. The improvement comes from representing used positions with integer bits, so checking availability and marking or unmarking a placement becomes a few bit operations instead of several hash set lookups.

This works because the same three constraints still define legal positions. The asymptotic complexity does not fundamentally change, since the algorithm still explores combinations of placements, but bitmasks usually make the implementation noticeably faster and more space-efficient in practice.

What if the interviewer asks for only one valid board, not all of them?

Keep the same depth-first search, but stop as soon as the first full placement is found. In code, that usually means returning a boolean from the recursive helper to signal that the search can short-circuit upward once a solution exists.

This works because every recursive path already represents a legal partial board. As soon as one path reaches row n, the requirement is satisfied. In the best case, this can finish much earlier than enumerating every board. In the worst case, it is still exponential if the first valid solution appears late or if no valid solution exists.

What if some queens are pre-placed or some cells are blocked?

Start by validating the fixed queens against each other and inserting their columns and diagonals into the same tracking structures used by the normal solution. Then, when processing each row, skip blocked cells and skip rows that already contain a fixed queen. The rest of the search remains unchanged.

This works because the core invariant is still the same: each row must end up with a legal queen placement that does not conflict with previously committed choices. The search can even become faster in practice because pre-placed queens and blocked cells reduce the number of candidate positions, although the worst-case complexity remains exponential.