# 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

The same as N-Queens, just need to output size of results.

```java
class Solution {
    public int totalNQueens(int n) {
        List<List<Integer>> ans = new ArrayList<>();

        if (n <= 0) {
            return 0;
        }
        searchHelper(n, new ArrayList<Integer>(), ans);

        return ans.size();
    }

    // Backtracking recursively find the valid solutions
    private void searchHelper(int n, List<Integer> cols, List<List<Integer>> ans) {
        if (cols.size() == n) {
            ans.add(new ArrayList<Integer>(cols));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!isValid(col, cols)) {
                continue;
            }
            cols.add(col);
            searchHelper(n, cols, ans);
            cols.remove(cols.size() - 1);
        }
    }

    // Check if the new position to be placed is invalid
    private boolean isValid(int col, List<Integer> cols) {
        if (cols.size() == 0) {
            return true;
        }

        for (int row = 0; row < cols.size(); row++) {
            if (col == cols.get(row)) {
                return false;
            }
            if (cols.get(row) - row == col - cols.size()) {
                return false;
            }
            if (cols.get(row) + row == col + cols.size()) {
                return false;
            }
        }
        return true;
    }
}
```

Or just use a global variable

```java
class Solution {
    private static int total;
    public int totalNQueens(int n) {
        List<List<Integer>> ans = new ArrayList<>();

        if (n <= 0) {
            return 0;
        }
        total = 0;
        searchHelper(n, new ArrayList<Integer>());

        return total;
    }

    // Backtracking recursively find the valid solutions
    private void searchHelper(int n, List<Integer> cols) {
        if (cols.size() == n) {
            total++;
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!isValid(col, cols)) {
                continue;
            }
            cols.add(col);
            searchHelper(n, cols);
            cols.remove(cols.size() - 1);
        }
    }

    // Check if the new position to be placed is invalid
    private boolean isValid(int col, List<Integer> cols) {
        if (cols.size() == 0) {
            return true;
        }

        for (int row = 0; row < cols.size(); row++) {
            if (col == cols.get(row)) {
                return false;
            }
            if (cols.get(row) - row == col - cols.size()) {
                return false;
            }
            if (cols.get(row) + row == col + cols.size()) {
                return false;
            }
        }
        return true;
    }
}
```

有关全局变量：

> [@mnmunknown](https://mnmunknown.gitbooks.io/algorithm-notes/518_search_&_recursion_3.html)
>
> 既然不需要输出最终解，也就省去了传递 rst 和把棋盘转成 String 的过程。一个问题是，如何在这种dfs + backtracking中维护一个 primitive type 变量，比如有效解的总数？
>
> Java 中默认 primitive type 是 pass by value，而且 Integer type 虽然作为一个 object 存在但是是 immutable, 不能用来作为全局参数多个函数共同更新。
>
> 直接建全局变量太蠢了，也不好看。

Not using global variable

```java
public class Solution {
    public int totalNQueens(int n) {
        return dfs(0, n, new boolean[n], new boolean[2*n - 1], new boolean[2*n - 1]);
    }

    private int dfs(int row, int n, boolean[] cols, boolean[] diag45, boolean[] diag135){
        if(row == n){
            return 1;
        }

        int solutionCount = 0;
        for(int col = 0; col < n; col++){
            if(!cols[col] && !diag45[row + col] && !diag135[row - col + n - 1]){
                cols[col] = true;
                diag45[row + col] = true;
                diag135[row - col + n - 1] = true;

                solutionCount += dfs(row + 1, n, cols, diag45, diag135);

                cols[col] = false;
                diag45[row + col] = false;
                diag135[row - col + n - 1] = false;
            }    
        }
        return solutionCount;
    }
}
```


---

# 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://aaronice.gitbook.io/lintcode/backtracking/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.