# 52\_N-Queens II

The *n*-queens puzzle is the problem of placing *n \_queens on an \_n*×\_n \_chessboard such that no two queens attack each other.

![](https://assets.leetcode.com/uploads/2018/10/12/8-queens.png)

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

**Example:**

```
Input: 4

Output: 2

Explanation:
 There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
```

## Solution: Backtracking

**Idea**:

* The idea is the same as in 51\_N-Queens.
* The only difference is return the number of solution instead of all the solutions.
* Make sure output is a global variable to be updated in the helper function.

```python
class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        def helper(row):
            if row == n:
                # global output
                self.output += 1
                return
            for col in range(n):
                if all(abs(col-b) not in (0, row-a) 
                       for a, b in enumerate(col_index[ :row])):
                    col_index[row] = col
                    helper(row + 1)


        self.output = 0
        col_index = [0] * n
        helper(0)
        return self.output
```