# 52. N-Queens II

#### Hard

***

The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.

Given an integer `n`, return *the number of distinct solutions to the **n-queens puzzle***.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)

```
Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
```

**Example 2:**

```
Input: n = 1
Output: 1
```

 

**Constraints:**

* `1 <= n <= 9`

```python
class Solution:
    def totalNQueens(self, n: int) -> int:
        col = set()
        posDia = set()
        negDia = set()
        board = [["."]*n for _ in range(n)]
        count = 0
        def backtrack(r):
            nonlocal count
            if r == n:
                count += 1
                return
            for c in range(n):
                if c in col or (r+c) in posDia or (r-c) in negDia:
                    continue
                col.add(c)
                posDia.add(r+c)
                negDia.add(r-c)
                backtrack(r+1)
                col.remove(c)
                posDia.remove(r+c)
                negDia.remove(r-c)
        backtrack(0)
        return count

```