> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/n-queens-ii.md).

# 52. N-Queens II

### Description

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

![](/files/-MFCZRbbhGVkP20069Zi)

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

### Constraints

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/n-queens-ii/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** 4

**Output:** 2

**Explanation:** There are two distinct solutions to the 4-queens puzzle as shown below.

\[

// Solution 1

\[ ".Q..", "...Q", "Q...", "..Q." ],

// Solution 2

\[ "..Q.", "Q...", "...Q", ".Q.." ]

]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N!). There is N possibilities to put the first queen, 
 *    not more than N (N - 2) to put the second one, not more than N(N-2)(N-4) 
 *    for the third one etc. In total that results in O(N!) time complexity.
 * Space complexity : O(N) to keep an information about diagonals and rows.
 */

class Solution {
    public int totalNQueens(int n) {
        if(n < 2) return 1;
        if(n > 1 && n < 4) return 0;
        
        boolean[] cols = new boolean[n];
        boolean[] hills = new boolean[n*2 - 1];
        boolean[] dales = new boolean[n*2 - 1];
            
        return backtrack(cols, hills, dales, 0, n, 0);
    }
    
    private int backtrack(boolean[] cols, 
                            boolean[] hills, 
                            boolean[] dales, 
                            int row, 
                            int n, 
                            int count) {
        for(int col = 0; col < n; col++) {
            if(cols[col] || hills[row+col] || dales[row-col+n-1]) {
                continue;
            }
            cols[col] = true;
            hills[row+col] = true;
            dales[row-col+n-1] = true;

            if(row+1 == n) {
                count++;
            } else {
                count = backtrack(cols, hills, dales, row+1, n, count);
            }

            cols[col] = false;
            hills[row+col] = false;
            dales[row-col+n-1] = false;
        }
        return count;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*