# N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

## Example

For n=4, there are 2 distinct solutions.

Solution:

这道题的区别就是不需要把具体方案打印出来，但是还是需要usedColumns变量来动态的存储方案的情况。

```
class Solution:
    """
    Calculate the total number of distinct N-Queen solutions.
    @param n: The number of queens.
    @return: The total number of distinct solutions.
    """
    def __init__(self):
        self.sum = 0
    def totalNQueens(self, n):
        # write your code here
        usedColumns = [0] * n
        self.dfs(usedColumns, 0)
        return self.sum
    def dfs(self, usedColumns, row):
        n = len(usedColumns)
        if n == row:
            self.sum += 1
            return
        for i in range(n):
            if self.isValid(usedColumns, row, i):
                usedColumns[row] = i 
                self.dfs(usedColumns, row + 1)
    def isValid(self, usedColumns, row, col):
        for i in range(row):
            if usedColumns[i] == col:
                return False
            if row - i == abs(col - usedColumns[i]):
                return False
        return True
```

回溯法：

```
class Solution:
    def totalNQueens(self, n: int) -> int:

        attack_zone = []
        directions = [(0,-1), (0,1), (-1,0), (1,0), (-1,1), (1,-1), (1,1), (-1,-1)]

        def is_not_under_attack(row = 0, col = 0):

            if (row, col) in attack_zone:
                return False

            return True

        def place_queen(row = 0, col = 0):

            attack_zone.append((row, col))

            for x, y in directions:

                moveX = row + x
                moveY = col + y

                while moveX >= 0 and moveX < n and moveY >= 0 and moveY < n:

                    attack_zone.append((moveX, moveY))

                    moveX += x
                    moveY += y

        def remove_queen(row = 0, col = 0):

            attack_zone.remove((row, col))

            for x, y in directions:

                moveX = row + x
                moveY = col + y

                while moveX >= 0 and moveX < n and moveY >= 0 and moveY < n:

                    attack_zone.remove((moveX, moveY))

                    moveX += x
                    moveY += y

        def backtrack_nqueen(row = 0, count = 0):

            for col in range(n):

                # iterate through columns at the curent row.
                if is_not_under_attack(row, col):

                    # explore this partial candidate solution, and mark the attacking zone
                    place_queen(row, col)

                    if row + 1 == n:
                        # we reach the bottom, i.e. we find a solution!
                        count += 1
                    else:
                        # we move on to the next row
                        count = backtrack_nqueen(row + 1, count)

                    # backtrack, i.e. remove the queen and remove the attacking zone.
                    remove_queen(row, col)

            return count

        if n == 0:
            return 1

        return backtrack_nqueen()
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuxue2010.gitbook.io/data-structure-and-algorithms/graph/n-queens-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.