Solution: N-Queens II
Tags: algorithms, javascript, java, python
Published: 2021-05-29 08:00:21

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/n-queens-ii/discuss/1237780).*

---

#### [Leetcode Problem #52 (*Hard*): N-Queens II](https://leetcode.com/problems/n-queens-ii/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.
>
Given an integer `n`, return _the number of distinct solutions to the **n-queens puzzle**_.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| n = 4
Output:| 2
Explanation:| There are two distinct solutions to the 4-queens puzzle as shown.
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)
>
Example 2:||
|---:|---|
Input:| n = 1
Output:| 1

---

#### ***Constraints:***
>
 - `1 <= n <= 9`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

_(**Note**: This problem is an easier duplicate to the previous problem, [**51: N-Queens**](https://leetcode.com/problems/n-queens), except that it doesn't require us to return the actual boards, just the count.)_

A naive approach here would attempt every possible combination of locations, but there are **(N^2)! / (N^2 - N)!** different combinations, which is up to **~1e17** when **N = 9**. Instead, we need to make sure we only attempt to place queens where it's feasible to do so, based on the instructions. This would seem to call for a **depth first search** (**DFS**) approach with a **recursive** helper function (**place**), so that we only pursue workable combinations without wasting time on known dead-ends.

First, we should consider how the queens will be placed. Since each row can only have one queen, our basic process will be to **place** a queen and then recurse to the next row. On each row, we'll have to iterate through the possible options, check the cell for validity, then **place** the queen on the board.

Rather than store the whole board, we can save on **space complexity** if we only keep track of the different axes of attack in which a queen might be placed. Since a queen has four axes of attack, we'll need to check the three remaining axes (other than the horizontal row, which our iteration will naturally take care of) for validity.

There are **N** possible columns and **2 * N - 1** possible left-downward diagonals and right-downward diagonals. With a constraint of **1 <= N <= 9,** each of the two diagonal states represents up to **17 bits**' worth of data and the vertical state up to **9 bits**, so we can use **bit manipulation** to store these states efficiently.

So for each recursive call to **place** a queen, we should pass along the board state in the form of only three integers (**vert, ldiag, rdiag**). We can then use **bitmasks** to check for cell validity before attempting to recurse to the next row.

If we successfully reach the end of the board without failing, we should increment our answer counter (**ans**).

 - _**Time Complexity: O(N!)** which represents the maximum number of queens placed_
 - _**Space Complexity: O(N)** for the recursion stack_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var totalNQueens = function(N) {
    let ans = 0
    
    const place = (i, vert, ldiag, rdiag) => {
        if (i === N) ans++
        else for (let j = 0; j < N; j++) {
            let vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j)
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
        }
    }

    place(0,0,0,0)
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def totalNQueens(self, N: int) -> int:
        self.ans = 0
        
        def place(i: int, vert: int, ldiag: int, rdiag:int) -> None:
            if i == N: self.ans += 1
            else:
                for j in range(N):
                    vmask, lmask, rmask = 1 << j, 1 << (i+j), 1 << (N-i-1+j)
                    if vert & vmask or ldiag & lmask or rdiag & rmask: continue
                    place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask)
            
        place(0,0,0,0)
        return self.ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    int ans;
    
    public int totalNQueens(int N) {
        ans = 0;
        place(0,0,0,0,N);
        return ans;
    }
    
    private void place(int i, int vert, int ldiag, int rdiag, int N) {
        if (i == N) ans++;
        else for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if ((vert & vmask) + (ldiag & lmask) + (rdiag & rmask) > 0) continue;
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
        }
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int totalNQueens(int N) {
        ans = 0;
        place(0,0,0,0,N);
        return ans;
    }
    
private:
    int ans;
    
    void place(int i, int vert, int ldiag, int rdiag, int N) {
        if (i == N) ans++;
        else for (int j = 0; j < N; j++) {
            int vmask = 1 << j, lmask = 1 << (i+j), rmask = 1 << (N-i-1+j);
            if (vert & vmask || ldiag & lmask || rdiag & rmask) continue;
            place(i+1, vert | vmask, ldiag | lmask, rdiag | rmask, N);
        }
    }
};
```