HARD

N-Queens

Place n queens on an n×n chessboard so no two queens attack each other (no shared row, column, or diagonal). Return every distinct board arrangement, each as a list of strings using "Q" for a queen and "." for an empty square.

Example

Input n = 4

Output 2 distinct valid arrangements

Key Pointers

Placing queens row by row, one per row, automatically satisfies the "no shared row" rule — only columns and diagonals need checking.
Track occupied columns and diagonals with sets instead of rescanning the board: a column set, plus two diagonal sets keyed by row - col and row + col, which are constant for every cell on the same diagonal.
A complete, valid placement is found exactly when a queen has been placed in every row without conflict.

Step-by-Step Analysis

Create empty sets for used columns and both diagonal directions.
Define backtrack(row): if row == n, record a copy of the board's string rows.
Loop col from 0 to n: skip if col, or the diagonal keys row - col / row + col, are already in use.
Otherwise mark the column/diagonals used, place "Q" at board[row][col], recurse with backtrack(row + 1), then undo the marks and reset the cell to ".".
Call backtrack(0) on an all-"." board and return the recorded results.

Complexity

Time: O(n!) — Space: O(n²) for the board, plus O(n) recursion depth

Code

def solveNQueens(n: int) -> list[list[str]]:
    result = []
    board = [["."] * n for _ in range(n)]
    cols, diag1, diag2 = set(), set(), set()

    def backtrack(row: int) -> None:
        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
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = "Q"

            backtrack(row + 1)

            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
            board[row][col] = "."

    backtrack(0)
    return result

Code Explanation

How the solution above works, piece by piece.

Place exactly one queen per row, going row by row, so only columns and diagonals need checking.
Every square on the same ↘ diagonal has the same row - col; every square on the same ↙ diagonal has the same row + col. Three sets turn "is this square attacked?" into O(1) lookups.
For each column in the current row, skip it if attacked; otherwise record the queen in all three sets and on the board, then recurse into the next row.
After returning, remove the queen from the sets and the board (backtrack) and try the next column.
When row == n, all queens are placed: save the board as strings. Roughly O(n!) time.

Visual Walkthrough

The result for n = 4:

Queens are placed one row at a time, so rows never clash. A square is allowed only if its column, r − c diagonal and r + c anti-diagonal are all unused. For n = 4, exactly these two boards survive.

queen

Video Explanation

NeetCode — Backtracking, LeetCode 51