# 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

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | Number of distinct valid queen arrangements |
| Board size | `n x n` |
| Constraint | No two queens may attack each other |

Function shape:

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

## Examples

For:

```python
n = 4
```

The answer is:

```python
2
```

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

For:

```python
n = 1
```

The answer is:

```python
1
```

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

For:

```python
n = 2
```

The answer is:

```python
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:

| Conflict | Check |
|---|---|
| Same column | `col` was used before |
| Same main diagonal | `row - col` was used before |
| Same anti-diagonal | `row + col` was used before |

The diagonal formulas are the main trick.

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

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

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

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

So we keep three sets:

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

These sets allow constant-time conflict checks.

## Algorithm

Use a recursive function:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n!)` approximately | We place one queen per row and never reuse a column |
| Space | `O(n)` | The sets and recursion stack each grow with the number of rows |

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

## Implementation

```python
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:

```python
count = 0
```

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

The three sets store blocked columns and diagonals:

```python
cols = set()
diag1 = set()
diag2 = set()
```

The recursive function receives the row currently being processed:

```python
def backtrack(row: int) -> None:
```

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

```python
nonlocal count
```

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

```python
if row == n:
    count += 1
    return
```

For each possible column, we compute both diagonal IDs:

```python
d1 = row - col
d2 = row + col
```

If the position is attacked, skip it:

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

Otherwise, mark the queen's column and diagonals:

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

Then move to the next row:

```python
backtrack(row + 1)
```

After recursion returns, undo the placement:

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

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

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `n = 1` | Smallest valid input |
| `n = 2` | No valid arrangement |
| `n = 3` | No valid arrangement |
| `n = 4` | Official example |
| `n = 5` to `n = 9` | Checks known counts within the constraint range |