# 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

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | A list of valid boards |
| Board format | Each board is a list of `n` strings |
| Cell format | `"Q"` means queen, `"."` means empty |
| Constraint | No two queens may attack each other |

Function shape:

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

## Examples

For:

```python
n = 4
```

There are two valid boards:

```python
[
    [".Q..", "...Q", "Q...", "..Q."],
    ["..Q.", "Q...", "...Q", ".Q.."]
]
```

One board means:

```text
.Q..
...Q
Q...
..Q.
```

The queens are placed at:

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

```python
n = 1
```

The answer is:

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

| Conflict | How to detect |
|---|---|
| Same column | `col` already used |
| Same main diagonal | `row - col` already used |
| Same anti-diagonal | `row + col` already used |

Why diagonals work:

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

## Algorithm

Maintain three sets:

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

Also maintain a board:

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

Then define a recursive function:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n!)` approximately | One queen is placed per row, and used columns shrink the choices |
| Space | `O(n^2)` | The board stores `n * n` cells |
| Extra recursion space | `O(n)` | The recursion depth is `n` |
| Sets | `O(n)` | At most `n` columns and diagonals are active |

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

## Implementation

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

```python
ans = []
```

The board starts empty:

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

The three sets track attacked columns and diagonals:

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

The recursive function receives the row we are currently filling:

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

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

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

```python
for col in range(n):
```

We compute the diagonal IDs:

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

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

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

Otherwise, place the queen:

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

Then solve the next row:

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

After that recursive call finishes, undo the move:

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

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

| Test | Why |
|---|---|
| `n = 1` | Smallest valid board |
| `n = 4` | Standard example with two solutions |
| `n = 2` | No valid arrangement |
| `n = 3` | No valid arrangement |
| `n = 5` validation loop | Checks every returned board mechanically |