LeetCode 51 - N-Queens

LeetCode Problem 51

Difficulty: 🔴 Hard
Topics: Array, Backtracking

Solution

Problem Understanding

The N-Queens problem asks us to place n queens on an n x n chessboard such that no two queens can attack each other. In chess, a queen can attack horizontally, vertically, and diagonally. This means that for any valid arrangement:

• No two queens can share the same row
• No two queens can share the same column
• No two queens can share the same diagonal

The input is a single integer n, representing the size of the chessboard. The goal is to return every possible valid board configuration.

Each returned board configuration is represented as a list of strings. Every string corresponds to one row of the board:

• 'Q' represents a queen
• '.' represents an empty square

For example, when n = 4, one valid board is:

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

This means:

• Row 0 has a queen in column 1
• Row 1 has a queen in column 3
• Row 2 has a queen in column 0
• Row 3 has a queen in column 2

The constraints are relatively small, 1 <= n <= 9, which strongly suggests that exhaustive search with pruning is acceptable. However, the number of possible queen placements grows extremely quickly, so a naive brute-force solution would still be inefficient.

An important observation is that every valid solution must place exactly one queen in each row. This significantly reduces the search space because we never need to consider multiple queens in the same row.

Several edge cases are important:

• n = 1 is the smallest possible board and has exactly one solution
• n = 2 and n = 3 have no valid solutions
• Larger values of n generate many recursive states, so efficient conflict checking is essential
• Diagonal conflicts are easy to implement incorrectly because they require coordinate relationships rather than direct equality

Approaches

Brute Force Approach

A brute-force solution would generate every possible arrangement of queens on the board and then check whether the arrangement is valid.

One way to think about this is:

• For every row, try every possible column
• Generate all possible combinations
• After generating a full board, verify whether any queens attack each other

If we allow every row to choose any of n columns, then there are n^n possible placements. For each placement, validating the board requires checking pairs of queens, which adds additional overhead.

This approach is correct because it explores every possible configuration. If a valid arrangement exists, brute force will eventually find it.

However, it is far too slow because most generated configurations are obviously invalid. For example, many boards will contain queens sharing columns or diagonals, yet the brute-force method wastes time constructing the entire board before rejecting it.

Optimal Approach, Backtracking with Pruning

The key insight is that we do not need to build invalid configurations completely.

Instead, we can construct the board row by row and immediately stop exploring a path as soon as it becomes invalid.

This technique is called backtracking.

At each row:

• Try placing a queen in every column
• Check whether the position is safe
• If safe, continue recursively to the next row
• If not safe, skip that position immediately

To make conflict checking efficient, we maintain three sets:

• Used columns
• Used main diagonals (row - col)
• Used anti-diagonals (row + col)

This allows constant-time safety checks.

The pruning effect is enormous because invalid partial configurations are discarded immediately instead of being expanded further.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^n * n²)	O(n²)	Generates all possible boards and validates afterward
Optimal	O(n!)	O(n²)	Backtracking with early pruning and constant-time conflict checks

Algorithm Walkthrough

1. Initialize an empty chessboard represented as a list of strings or character arrays.

We need a mutable structure because queens will be placed and removed repeatedly during recursion. 2. Create three sets to track attacked positions.

We maintain:

• columns for occupied columns
• diag1 for main diagonals identified by row - col
• diag2 for anti-diagonals identified by row + col

These sets allow constant-time conflict detection. 3. Start recursive backtracking from row 0.

Since each row must contain exactly one queen, recursion naturally progresses row by row. 4. For the current row, iterate through every column.

Each column represents a candidate position for the queen. 5. Before placing a queen, check whether the position is safe.

A position is invalid if:

• The column already contains a queen
• The main diagonal already contains a queen
• The anti-diagonal already contains a queen

6. If the position is safe, place the queen.

This involves:

• Updating the board
• Adding the column to columns
• Adding row - col to diag1
• Adding row + col to diag2

7. Recursively process the next row.

The recursive call attempts to place a queen in the next row while respecting all existing constraints. 8. If all rows are processed, record the current board.

Reaching row n means we successfully placed all queens without conflicts. 9. After recursion returns, remove the queen.

This is the "backtracking" step. We undo all changes so the algorithm can explore alternative placements. 10. Continue exploring remaining columns.

Every possible valid arrangement will eventually be explored.

Why it works

The algorithm maintains an invariant that all queens already placed on the board are non-attacking. Before placing any new queen, the algorithm verifies that the new position does not violate this invariant.

Because every row is explored systematically and every safe placement is considered, the algorithm eventually generates every valid configuration exactly once.

Python Solution

from typing import List

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

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

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

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

            for col in range(n):
                if (
                    col in columns
                    or (row - col) in diag1
                    or (row + col) in diag2
                ):
                    continue

                board[row][col] = "Q"
                columns.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                backtrack(row + 1)

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

        backtrack(0)

        return results

The implementation begins by initializing the board as a 2D grid filled with dots. This board is modified in place during recursion.

The results list stores all valid solutions. Each completed solution is converted from a character grid into the required list-of-strings format.

The three sets are the core optimization:

• columns tracks occupied columns
• diag1 tracks main diagonals
• diag2 tracks anti-diagonals

The recursive backtrack function processes one row at a time.

The base case occurs when row == n. At that point, every queen has been placed successfully, so the current board configuration is copied into the result list.

Inside the loop, every column is tested. If the column or either diagonal is already occupied, the position is skipped immediately.

When a valid position is found:

• The queen is placed
• The tracking sets are updated
• Recursion continues to the next row

After recursion finishes, the queen is removed and the tracking sets are restored. This ensures the board state is correct for future exploration.

Go Solution

func solveNQueens(n int) [][]string {
    results := [][]string{}

    board := make([][]byte, n)
    for i := 0; i < n; i++ {
        board[i] = make([]byte, n)
        for j := 0; j < n; j++ {
            board[i][j] = '.'
        }
    }

    columns := map[int]bool{}
    diag1 := map[int]bool{}
    diag2 := map[int]bool{}

    var backtrack func(int)

    backtrack = func(row int) {
        if row == n {
            solution := make([]string, n)

            for i := 0; i < n; i++ {
                solution[i] = string(board[i])
            }

            results = append(results, solution)
            return
        }

        for col := 0; col < n; col++ {
            if columns[col] || diag1[row-col] || diag2[row+col] {
                continue
            }

            board[row][col] = 'Q'

            columns[col] = true
            diag1[row-col] = true
            diag2[row+col] = true

            backtrack(row + 1)

            board[row][col] = '.'

            delete(columns, col)
            delete(diag1, row-col)
            delete(diag2, row+col)
        }
    }

    backtrack(0)

    return results
}

The Go implementation follows the same recursive backtracking strategy as the Python solution.

One important difference is that Go strings are immutable, so the board is represented as a 2D slice of bytes instead of strings. This allows efficient in-place updates during recursion.

Maps with boolean values are used instead of Python sets because Go does not provide a built-in set type.

When a solution is found, each row is converted from []byte to string before being appended to the result list.

Go does not require special handling for integer overflow here because all diagonal values remain small within the given constraints.

Worked Examples

Example 1

Input:

n = 4

Initial state:

Row	Board
0	....
1	....
2	....
3	....

Start with row 0.

Step 1, Place queen at (0,0)

Structure	Value
columns	{0}
diag1	{0}
diag2	{0}

Board:

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

Step 2, Process row 1

Try column 0:

• Same column conflict

Try column 1:

• Diagonal conflict

Try column 2:

• Valid placement

State becomes:

Structure	Value
columns	{0,2}
diag1	{0,-1}
diag2	{0,3}

Board:

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

Step 3, Process row 2

Every column produces a conflict.

Since no valid placement exists, backtrack.

Remove queen from (1,2).

Step 4, Continue row 1

Try column 3.

Board:

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

Continue recursively.

Eventually this branch also fails.

Backtrack again.

Step 5, Try different starting positions

The algorithm continues exploring systematically until it finds:

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

and:

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

These are the only valid solutions.

Example 2

Input:

n = 1

Initial board:

.

Place queen at (0,0).

Board:

Q

All rows are processed, so the solution is added.

Final output:

[["Q"]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n!)	Each row chooses among remaining valid columns, heavily pruned by constraints
Space	O(n²)	Board storage plus recursion stack and tracking sets

The time complexity is commonly approximated as O(n!) because each recursive level reduces the number of available columns. Although pruning significantly reduces actual runtime, the worst-case search space still grows factorially.

The space complexity includes:

• The board itself, which uses O(n²)
• Recursion depth up to O(n)
• Tracking sets storing at most O(n) entries

The board dominates overall memory usage.

Test Cases

from typing import List

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

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

        columns = set()
        diag1 = set()
        diag2 = set()

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

            for col in range(n):
                if (
                    col in columns
                    or (row - col) in diag1
                    or (row + col) in diag2
                ):
                    continue

                board[row][col] = "Q"

                columns.add(col)
                diag1.add(row - col)
                diag2.add(row + col)

                backtrack(row + 1)

                board[row][col] = "."

                columns.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        backtrack(0)

        return results

solution = Solution()

# Example case n = 1
assert solution.solveNQueens(1) == [["Q"]]  # smallest valid board

# Example case n = 4
result_4 = solution.solveNQueens(4)
assert len(result_4) == 2  # exactly two valid solutions

# No solution for n = 2
assert solution.solveNQueens(2) == []  # impossible configuration

# No solution for n = 3
assert solution.solveNQueens(3) == []  # impossible configuration

# Verify n = 5 solution count
assert len(solution.solveNQueens(5)) == 10  # known number of solutions

# Verify n = 6 solution count
assert len(solution.solveNQueens(6)) == 4  # known number of solutions

# Ensure all rows have correct length
solutions = solution.solveNQueens(4)
for board in solutions:
    for row in board:
        assert len(row) == 4  # proper board width

# Ensure every row contains exactly one queen
for board in solutions:
    for row in board:
        assert row.count("Q") == 1  # valid row structure

Test	Why
n = 1	Validates smallest possible input
n = 4	Confirms standard example and multiple solutions
n = 2	Verifies impossible configuration handling
n = 3	Verifies another impossible configuration
n = 5	Tests larger recursive search space
n = 6	Validates correctness against known counts
Row length checks	Ensures proper board formatting
Queen count checks	Ensures valid row construction

Edge Cases

Edge Case 1, n = 1

This is the smallest valid board size. A naive implementation may accidentally reject the only available position because diagonal or column logic is implemented incorrectly.

The solution handles this naturally because the recursion starts at row 0, places a queen successfully, and immediately reaches the base case.

Edge Case 2, n = 2 and n = 3

These board sizes have no valid solutions.

A common bug is assuming every board size must produce at least one configuration. Incorrect implementations may return partially completed boards or invalid placements.

The backtracking approach handles this correctly because every recursive branch eventually fails conflict checks, resulting in an empty result list.

Edge Case 3, Diagonal Conflicts

Diagonal checking is often the trickiest part of the problem.

Two queens share a main diagonal if row - col is equal. They share an anti-diagonal if row + col is equal.

A common mistake is attempting to scan the entire board repeatedly or computing diagonal identifiers incorrectly.

The implementation avoids these issues by storing diagonal identifiers directly in hash sets, allowing constant-time conflict detection and guaranteeing correctness.