LeetCode 51: N-Queens

Problem Restatement

We are given an integer n.

We need to place n queens on an n x n chessboard so that no two queens attack each other.

A queen can attack another queen if they share:

1. The same row
2. The same column
3. The same diagonal

Return all distinct valid board configurations. Each board uses "Q" for a queen and "." for an empty square. The answer may be returned in any order. The official constraint is 1 <= n <= 9.

Input and Output

Function shape:

def solveNQueens(n: int) -> list[list[str]]:
    ...

Examples

For:

n = 4

There are two valid boards:

[
    [".Q..", "...Q", "Q...", "..Q."],
    ["..Q.", "Q...", "...Q", ".Q.."]
]

One board means:

.Q..
...Q
Q...
..Q.

The queens are placed at:

row 0, col 1
row 1, col 3
row 2, col 0
row 3, col 2

No two queens share a row, column, or diagonal.

For:

n = 1

The answer is:

[["Q"]]

A single queen on a 1 x 1 board is valid.

First Thought: Brute Force

The most direct idea is to try all possible queen placements on the board.

The board has n * n cells.

We need to choose n cells and then check whether the placement is valid.

That approach wastes a lot of work because it tries many impossible boards.

For example, if two queens are already in the same row, the board can never become valid. We should reject that path immediately.

Key Insight

Since we need to place n queens on n rows, and no two queens can share a row, every valid board must have exactly one queen in each row.

So we can build the board row by row.

For each row:

1. Try each column.
2. Check whether placing a queen there is safe.
3. If safe, place the queen and move to the next row.
4. After exploring that path, remove the queen and try another column.

This is backtracking.

The important part is the safety check.

A queen at position (row, col) conflicts with an earlier queen if they share:

Why diagonals work:

Cells on the same main diagonal have the same row - col.

(0, 0), (1, 1), (2, 2)
row - col = 0

Cells on the same anti-diagonal have the same row + col.

(0, 2), (1, 1), (2, 0)
row + col = 2

Algorithm

Maintain three sets:

cols = set()
diag1 = set()  # row - col
diag2 = set()  # row + col

Also maintain a board:

board = [["."] * n for _ in range(n)]

Then define a recursive function:

backtrack(row)

Meaning:

Try to place queens from this row onward.

For each column in the current row:

1. Check whether col is already used.
2. Check whether row - col is already used.
3. Check whether row + col is already used.
4. If any check fails, skip this column.
5. Otherwise, place the queen.
6. Recurse to the next row.
7. Remove the queen after recursion returns.

When row == n, we have placed all queens. Convert the board into a list of strings and add it to the answer.

Correctness

The algorithm places exactly one queen per row because each recursive call handles one row and places at most one queen before moving to the next row.

The sets prevent all possible attacks from earlier queens. cols prevents two queens from sharing a column. diag1 prevents two queens from sharing a main diagonal. diag2 prevents two queens from sharing an anti-diagonal.

Whenever the algorithm reaches row == n, it has placed n queens. Since every placement passed the column and diagonal checks, no two queens attack each other. Therefore every board added to the answer is valid.

The algorithm also finds every valid board. For each row, it tries every column. If a placement can belong to a valid board, the safety checks allow it. The recursion then continues to the next row. Since every possible safe row-by-row placement is explored, every valid solution is eventually added.

Complexity

The output itself may contain many boards, so the total returned data can also be large.

Implementation

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        ans = []

        board = [["."] * n for _ in range(n)]

        cols = set()
        diag1 = set()
        diag2 = set()

        def backtrack(row: int) -> None:
            if row == n:
                ans.append(["".join(r) for r in board])
                return

            for col in range(n):
                d1 = row - col
                d2 = row + col

                if col in cols or d1 in diag1 or d2 in diag2:
                    continue

                board[row][col] = "Q"
                cols.add(col)
                diag1.add(d1)
                diag2.add(d2)

                backtrack(row + 1)

                board[row][col] = "."
                cols.remove(col)
                diag1.remove(d1)
                diag2.remove(d2)

        backtrack(0)
        return ans

Code Explanation

We store all answers here:

ans = []

The board starts empty:

board = [["."] * n for _ in range(n)]

The three sets track attacked columns and diagonals:

cols = set()
diag1 = set()
diag2 = set()

The recursive function receives the row we are currently filling:

def backtrack(row: int) -> None:

If row == n, all rows already have queens:

if row == n:
    ans.append(["".join(r) for r in board])
    return

We convert each row from a list of characters into a string because the required output format is list[str].

For each column:

for col in range(n):

We compute the diagonal IDs:

d1 = row - col
d2 = row + col

If the column or diagonal is already attacked, this position cannot be used:

if col in cols or d1 in diag1 or d2 in diag2:
    continue

Otherwise, place the queen:

board[row][col] = "Q"
cols.add(col)
diag1.add(d1)
diag2.add(d2)

Then solve the next row:

backtrack(row + 1)

After that recursive call finishes, undo the move:

board[row][col] = "."
cols.remove(col)
diag1.remove(d1)
diag2.remove(d2)

This undo step allows the algorithm to try the next column cleanly.

Testing

def normalize(ans):
    return sorted(ans)

def run_tests():
    s = Solution()

    assert s.solveNQueens(1) == [["Q"]]

    expected_4 = [
        [".Q..", "...Q", "Q...", "..Q."],
        ["..Q.", "Q...", "...Q", ".Q.."],
    ]
    assert normalize(s.solveNQueens(4)) == normalize(expected_4)

    assert s.solveNQueens(2) == []
    assert s.solveNQueens(3) == []

    for board in s.solveNQueens(5):
        n = len(board)
        queens = []

        for r in range(n):
            for c in range(n):
                if board[r][c] == "Q":
                    queens.append((r, c))

        assert len(queens) == n

        for i in range(len(queens)):
            for j in range(i + 1, len(queens)):
                r1, c1 = queens[i]
                r2, c2 = queens[j]

                assert r1 != r2
                assert c1 != c2
                assert abs(r1 - r2) != abs(c1 - c2)

    print("all tests passed")

run_tests()