LeetCode Problem 52

Difficulty: 🔴 Hard
Topics: Backtracking

Solution

LeetCode 52, N-Queens II

Problem Statement

The n-queens puzzle asks us to place n queens on an n x n chessboard so that no two queens can attack each other. In chess, a queen can move horizontally, vertically, and diagonally. That means any two queens sharing the same row, same column, or same diagonal would be attacking one another, which is not allowed.

The input consists of a single integer n, which represents both the number of queens and the dimensions of the board. The task is not to return the actual board configurations, but instead to return the total number of valid arrangements.

For example, when n = 4, there are exactly two distinct ways to place four queens safely on a 4 x 4 board. Therefore, the answer is 2.

The constraints are relatively small:

1 <= n <= 9

Even though n is at most 9, the search space grows extremely quickly because every row can potentially branch into many column choices. A naive brute-force solution would become prohibitively expensive. This strongly suggests that pruning invalid states early is essential.

Several important edge cases should be considered immediately:

• When n = 1, the board contains a single cell, so there is exactly one valid placement.
• Small values like n = 2 and n = 3 have no valid solutions at all.
• Larger values require efficient conflict checking because repeated board scans become costly during deep recursive exploration.

Problem Understanding

The key observation is that each row must contain exactly one queen. If we process the board row by row, then we only need to decide which column to place the queen in for the current row.

Suppose we are placing queens row by row from top to bottom. Once we place queens in earlier rows, the next queen cannot use:

• Any column already occupied by another queen
• Any diagonal already occupied

Two queens share a diagonal if either of these expressions is equal:

• row - col
• row + col

This property allows us to efficiently track attacked diagonals using sets.

The goal is to count all valid configurations, not to construct or return them.

Approaches

Brute Force Approach

A brute-force solution would attempt to place queens in every possible cell combination on the board and then verify whether the arrangement is valid.

One possible brute-force strategy is:

• Generate all possible placements of n queens on the board
• For each arrangement, scan the board to determine whether any queens attack each other

This approach is correct because it eventually examines every possible configuration. However, it is extremely inefficient.

An n x n board has n² cells. Choosing n queen positions from those cells leads to a massive number of combinations. Additionally, validating each configuration requires repeated scanning across rows, columns, and diagonals.

Even if we improve slightly by forcing exactly one queen per row, we still explore n! possible column permutations. Many of these become invalid early, but brute force does not prune them efficiently.

Optimal Backtracking Approach

The better solution uses backtracking with pruning.

Instead of generating full boards and validating afterward, we build the configuration incrementally. As soon as a queen placement becomes invalid, we stop exploring that branch.

The core insight is that when placing queens row by row:

• Each recursive call handles exactly one row
• We only need to test whether a column or diagonal is already occupied
• Invalid states can be rejected immediately

We maintain three sets:

• columns tracks occupied columns
• diagonals tracks occupied main diagonals using row - col
• anti_diagonals tracks occupied anti-diagonals using row + col

This allows conflict detection in constant time.

Because invalid branches are pruned early, the search becomes dramatically faster than brute force.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * n) or worse	O(n²)	Generates many invalid states and validates repeatedly
Optimal Backtracking	O(n!)	O(n)	Prunes invalid branches immediately using sets

Algorithm Walkthrough

1. Initialize three empty sets:

• columns stores columns already containing queens
• diagonals stores values of row - col
• anti_diagonals stores values of row + col

2. Start a recursive backtracking function beginning at row 0.
3. For the current row, iterate through every column from 0 to n - 1.
4. For each candidate position (row, col), compute:

• diagonal = row - col
• anti_diagonal = row + col

5. Check whether:

• col already exists in columns
• diagonal already exists in diagonals
• anti_diagonal already exists in anti_diagonals

If any of these conditions is true, placing a queen here would create a conflict, so skip this position. 6. If the position is valid:

• Add the column and diagonals to their respective sets
• Recursively process the next row

7. If the recursion reaches row == n, it means queens were successfully placed in all rows. Increment the solution counter.
8. After exploring a branch, remove the current placement from all sets. This is the backtracking step, which restores the board state so other possibilities can be explored.
9. Continue exploring until all rows and columns have been processed.

Why it works

The algorithm maintains an important invariant: before processing a row, all previously placed queens are guaranteed to be non-conflicting.

Each recursive call only attempts placements that preserve this invariant. Since every valid arrangement is explored exactly once and every invalid arrangement is pruned immediately, the algorithm correctly counts all distinct solutions.

Python Solution

class Solution:
    def totalNQueens(self, n: int) -> int:
        columns = set()
        diagonals = set()
        anti_diagonals = set()

        solutions = 0

        def backtrack(row: int) -> None:
            nonlocal solutions

            if row == n:
                solutions += 1
                return

            for col in range(n):
                diagonal = row - col
                anti_diagonal = row + col

                if (
                    col in columns or
                    diagonal in diagonals or
                    anti_diagonal in anti_diagonals
                ):
                    continue

                columns.add(col)
                diagonals.add(diagonal)
                anti_diagonals.add(anti_diagonal)

                backtrack(row + 1)

                columns.remove(col)
                diagonals.remove(diagonal)
                anti_diagonals.remove(anti_diagonal)

        backtrack(0)

        return solutions

The implementation follows the recursive backtracking strategy directly.

The three sets provide constant-time conflict detection. This is much more efficient than scanning the board repeatedly.

The nested backtrack function processes one row at a time. If row == n, then queens have been successfully placed in every row, so a valid solution has been found.

For each column in the current row, the algorithm computes the two diagonal identifiers:

diagonal = row - col
anti_diagonal = row + col

These values uniquely identify diagonals across the board.

If a placement is valid, the queen's column and diagonals are added to the sets before recursively exploring the next row.

After recursion finishes, the sets are restored using remove. This is the essence of backtracking, the algorithm temporarily commits to a choice, explores all consequences, then undoes the choice so other possibilities can be tested.

Go Solution

func totalNQueens(n int) int {
    columns := make(map[int]bool)
    diagonals := make(map[int]bool)
    antiDiagonals := make(map[int]bool)

    solutions := 0

    var backtrack func(int)

    backtrack = func(row int) {
        if row == n {
            solutions++
            return
        }

        for col := 0; col < n; col++ {
            diagonal := row - col
            antiDiagonal := row + col

            if columns[col] || diagonals[diagonal] || antiDiagonals[antiDiagonal] {
                continue
            }

            columns[col] = true
            diagonals[diagonal] = true
            antiDiagonals[antiDiagonal] = true

            backtrack(row + 1)

            delete(columns, col)
            delete(diagonals, diagonal)
            delete(antiDiagonals, antiDiagonal)
        }
    }

    backtrack(0)

    return solutions
}

The Go implementation mirrors the Python logic closely. Since Go does not have a built-in set type, maps with boolean values are used instead.

Backtracking state restoration uses delete to remove entries from the maps after recursion completes.

Integer overflow is not a concern because the maximum number of solutions for n <= 9 easily fits within Go's int type.

Worked Examples

Example 1

Input:

n = 4

We process row by row.

Initial State

Variable	Value
columns	{}
diagonals	{}
anti_diagonals	{}
solutions	0

Place Queen at (0, 0)

Variable	Value
columns	{0}
diagonals	{0}
anti_diagonals	{0}

Move to row 1.

Possible columns:

• Column 0 conflicts vertically
• Column 1 conflicts diagonally
• Column 2 is valid
• Column 3 is valid

Suppose we place at (1, 2).

State After (1, 2)

Variable	Value
columns	{0, 2}
diagonals	{0, -1}
anti_diagonals	{0, 3}

Move to row 2.

Every column now conflicts, so this branch fails.

The algorithm backtracks and tries (1, 3) instead.

Eventually, the algorithm discovers these two valid arrangements:

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

The final answer becomes:

2

Example 2

Input:

n = 1

Initial State

Variable	Value
columns	{}
diagonals	{}
anti_diagonals	{}

Place queen at (0, 0):

Variable	Value
columns	{0}
diagonals	{0}
anti_diagonals	{0}

Now row == n, so a valid configuration is found.

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n!)	Each row explores remaining column possibilities recursively
Space	O(n)	Recursion depth and tracking sets grow linearly with n

The time complexity is exponential because the algorithm explores combinations of queen placements. However, pruning dramatically reduces the number of explored states compared to brute force.

The space complexity is linear because:

• The recursion stack can grow to depth n
• The sets store at most n columns and diagonals

No full board storage is required.

Test Cases

solution = Solution()

assert solution.totalNQueens(1) == 1  # Single cell board
assert solution.totalNQueens(2) == 0  # No valid arrangement
assert solution.totalNQueens(3) == 0  # No valid arrangement
assert solution.totalNQueens(4) == 2  # Example case
assert solution.totalNQueens(5) == 10  # Standard known result
assert solution.totalNQueens(6) == 4  # Larger board
assert solution.totalNQueens(7) == 40  # Increased branching
assert solution.totalNQueens(8) == 92  # Classic chess puzzle
assert solution.totalNQueens(9) == 352  # Upper constraint boundary

Test Summary

Test	Why
n = 1	Smallest valid input
n = 2	No possible solution
n = 3	Another impossible configuration
n = 4	First non-trivial solvable board
n = 5	Verifies recursive branching
n = 6	Tests deeper recursion
n = 7	Larger search tree validation
n = 8	Classic benchmark case
n = 9	Maximum constraint stress test

Edge Cases

Edge Case 1, n = 1

This is the smallest possible input. A naive implementation might accidentally return 0 because it assumes multiple queens are needed for a valid configuration.

The implementation handles this naturally because the recursive search successfully places one queen and immediately reaches the base case row == n.

Edge Case 2, n = 2 and n = 3

These board sizes have no valid solutions. Incorrect implementations sometimes mistakenly count partial placements as valid.

The backtracking approach correctly explores every possible configuration and only increments the solution counter when all rows are successfully filled. Since no valid arrangement exists, the result remains 0.

Edge Case 3, Diagonal Collisions

Diagonal conflicts are the most common source of bugs in N-Queens solutions. Many incorrect implementations check only rows and columns.

This solution uses two distinct diagonal identifiers:

row - col
row + col

Any queens sharing one of these values are on the same diagonal. This guarantees constant-time diagonal conflict detection and ensures invalid placements are rejected immediately.

Edge Case 4, Backtracking State Restoration

A common mistake in recursive solutions is forgetting to remove state after recursion returns. That causes placements from one branch to incorrectly affect later branches.

This implementation explicitly removes entries from all tracking sets after each recursive call:

columns.remove(col)
diagonals.remove(diagonal)
anti_diagonals.remove(anti_diagonal)

This guarantees every recursive branch starts with the correct board state.