LeetCode 52: N-Queens II

Problem Restatement

We are given an integer n.

We need to count how many ways we can 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 are in the same row, same column, or same diagonal.

Unlike LeetCode 51, we do not need to return the boards. We only return the number of valid arrangements.

The official constraint is 1 <= n <= 9.

Input and Output

Function shape:

def totalNQueens(n: int) -> int:
    ...

Examples

For:

n = 4

The answer is:

2

There are two valid ways to place four queens on a 4 x 4 board.

For:

n = 1

The answer is:

1

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

For:

n = 2

The answer is:

0

No matter where we place the queens, two queens will attack each other.

First Thought: Brute Force

A direct brute force approach would try placing queens on many combinations of board cells, then check whether each board is valid.

That is too much work.

We can do better by using the structure of the problem.

Since no two queens can share a row, every valid solution must place exactly one queen in each row.

So instead of choosing arbitrary cells, we build the board row by row.

Key Insight

At each row, we only need to choose the queen’s column.

Once we choose a column, we need to know whether that position conflicts with an earlier queen.

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

The diagonal formulas are the main trick.

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

So we keep three sets:

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

These sets allow constant-time conflict checks.

Algorithm

Use a recursive function:

backtrack(row)

This means:

Count all valid ways to place queens starting from row.

For each column in the current row:

1. Compute row - col.
2. Compute row + col.
3. If the column or either diagonal is already used, skip this position.
4. Otherwise, place a queen by marking the column and diagonals.
5. Recurse into row + 1.
6. After recursion, remove the queen by unmarking the column and diagonals.

When row == n, all queens have been placed. That gives one valid arrangement, so increment the count.

Correctness

The algorithm places queens one row at a time. Because each recursive call handles exactly one row, no solution can contain two queens in the same row.

Before placing a queen at (row, col), the algorithm checks whether col, row - col, or row + col has already been used. These three checks cover all ways a queen can attack another queen from a previous row: same column, main diagonal, and anti-diagonal.

So every placement accepted by the algorithm keeps the board valid.

When row == n, the algorithm has placed one queen in each of the n rows. Since every placement was checked before being made, no two queens attack each other. Therefore each counted arrangement is valid.

The algorithm also counts every valid arrangement. For each row, it tries every column. Any column that can appear in a valid solution will pass the conflict checks at that point, so the recursive search continues along that valid path. Therefore every valid arrangement is eventually reached and counted.

Complexity

We do not store full boards, so this version uses less memory than LeetCode 51.

Implementation

class Solution:
    def totalNQueens(self, n: int) -> int:
        count = 0

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

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

            if row == n:
                count += 1
                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

                cols.add(col)
                diag1.add(d1)
                diag2.add(d2)

                backtrack(row + 1)

                cols.remove(col)
                diag1.remove(d1)
                diag2.remove(d2)

        backtrack(0)
        return count

Code Explanation

We start with a counter:

count = 0

Every time we finish placing n queens, we increase this counter.

The three sets store blocked columns and diagonals:

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

The recursive function receives the row currently being processed:

def backtrack(row: int) -> None:

Because count belongs to the outer function, we mark it as nonlocal:

nonlocal count

When row == n, all queens have been placed:

if row == n:
    count += 1
    return

For each possible column, we compute both diagonal IDs:

d1 = row - col
d2 = row + col

If the position is attacked, skip it:

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

Otherwise, mark the queen’s column and diagonals:

cols.add(col)
diag1.add(d1)
diag2.add(d2)

Then move to the next row:

backtrack(row + 1)

After recursion returns, undo the placement:

cols.remove(col)
diag1.remove(d1)
diag2.remove(d2)

This reset is what allows the next column choice to be tried cleanly.

Testing

def run_tests():
    s = Solution()

    assert s.totalNQueens(1) == 1
    assert s.totalNQueens(2) == 0
    assert s.totalNQueens(3) == 0
    assert s.totalNQueens(4) == 2
    assert s.totalNQueens(5) == 10
    assert s.totalNQueens(6) == 4
    assert s.totalNQueens(7) == 40
    assert s.totalNQueens(8) == 92
    assert s.totalNQueens(9) == 352

    print("all tests passed")

run_tests()