> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/recursion-and-backtracking/n-queens-ii.md).

# 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.."]
]
```

```java
public class Solution {
    int count = 0;

    public int totalNQueens(int n) {
        boolean[] columnMarker = new boolean[n]; // columns |
        boolean[] d1 = new boolean[2 * n]; // diagonals \
        boolean[] d2 = new boolean[2 * n]; // diagonals /
        backtracking(0, columnMarker, d1, d2, n);
        return count;
    }

    public void backtracking(int row, boolean[] columnMarker, boolean[] d1marker, boolean[] d2marker, int n) {
        if (row == n)
            count++;

        for (int col = 0; col < n; col++) {
            int id1 = col - row + n;
            int id2 = col + row;
            if (columnMarker[col] || d1marker[id1] || d2marker[id2])
                continue;

            columnMarker[col] = true;
            d1marker[id1] = true;
            d2marker[id2] = true;
            backtracking(row + 1, columnMarker, d1marker, d2marker, n);
            columnMarker[col] = false;
            d1marker[id1] = false;
            d2marker[id2] = false;
        }
    }
}
```