# N-Queens II
**Difficulty:** HARD
[External](https://leetcode.com/problems/n-queens-ii)
Canonical: https://scaleengineer.com/dsa/problems/n-queens-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Companies:** [Amazon](https://scaleengineer.com/companies/amazon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Microsoft](https://scaleengineer.com/companies/microsoft), [Snowflake](https://scaleengineer.com/companies/snowflake), [Zenefits](https://scaleengineer.com/companies/zenefits), [Liftoff](https://scaleengineer.com/companies/liftoff)
---
## Problem
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**_.

**Example 1:**

![](https://assets.glich.co/dsa/n-queens-ii/image0.jpg) 

**Input:** n = 4
**Output:** 2
**Explanation:** There are two distinct solutions to the 4-queens puzzle as shown.

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

* `1 <= n <= 9`

# Approaches
## Backtracking with Helper Arrays
This approach uses a standard backtracking algorithm to explore all possible placements of queens. We build the solution row by row, ensuring that each new queen placed does not attack any previously placed queens. To efficiently check for attacks, we use helper boolean arrays to keep track of which columns and diagonals are already occupied.
**Time:** O(N!) · **Space:** O(N)
**Pros:** The logic is straightforward and closely follows the definition of the N-Queens problem.; It's a general backtracking template that can be adapted to similar constraint satisfaction problems.
**Cons:** Slightly less performant than the bitmasking approach due to the overhead of array indexing and assignments compared to fast bitwise operations.; Uses more memory to store the boolean arrays compared to a few integers.
### Explanation
The core idea is to place one queen in each row, starting from row 0. For each row, we iterate through all columns to find a safe square. A square `(row, col)` is considered safe if no other queen (in rows `0` to `row-1`) is in the same column, same main diagonal, or same anti-diagonal.

We use three boolean arrays to maintain the state:
- `cols[c]` is `true` if a queen is already placed in column `c`.
- `diag1[r-c+n-1]` is `true` if a queen is on the main diagonal identified by `r-c`. We add `n-1` to map the result (which can be negative) to a valid array index.
- `diag2[r+c]` is `true` if a queen is on the anti-diagonal identified by `r+c`.

When the recursive function `backtrack(row)` is called, it tries to place a queen in each column of that `row`. If a safe column is found, it marks the corresponding column and diagonals as occupied, and then makes a recursive call for the next row, `backtrack(row + 1)`. After the recursive call returns, it backtracks by un-marking the column and diagonals, allowing the exploration of placing the queen in other columns of the current row. If the recursion reaches `row == n`, a valid solution has been found, and we increment a counter.

```java
class Solution {
    private int count = 0;
    private boolean[] cols;
    private boolean[] diag1;
    private boolean[] diag2;
    private int n;

    public int totalNQueens(int n) {
        this.n = n;
        this.cols = new boolean[n];
        this.diag1 = new boolean[2 * n - 1];
        this.diag2 = new boolean[2 * n - 1];
        backtrack(0);
        return count;
    }

    private void backtrack(int row) {
        if (row == n) {
            count++;
            return;
        }

        for (int col = 0; col < n; col++) {
            int d1_idx = row - col + n - 1;
            int d2_idx = row + col;

            if (cols[col] || diag1[d1_idx] || diag2[d2_idx]) {
                continue;
            }

            // Place the queen
            cols[col] = true;
            diag1[d1_idx] = true;
            diag2[d2_idx] = true;

            // Recurse for the next row
            backtrack(row + 1);

            // Backtrack (remove the queen)
            cols[col] = false;
            diag1[d1_idx] = false;
            diag2[d2_idx] = false;
        }
    }
}
```
### Algorithm
- Initialize a global or member variable `count` to store the number of solutions.
- Create three boolean arrays to keep track of occupied columns and diagonals:
  - `cols` of size `n`.
  - `diag1` of size `2*n - 1` for main diagonals (`row - col`).
  - `diag2` of size `2*n - 1` for anti-diagonals (`row + col`).
- Implement a recursive backtracking function, say `backtrack(row)`.
- **Base Case:** If `row == n`, it means we have successfully placed `n` queens. Increment `count` and return.
- **Recursive Step:** Iterate through each column `col` from `0` to `n-1` for the current `row`.
  - Calculate the indices for the two diagonals: `d1 = row - col + n - 1` and `d2 = row + col`.
  - Check if the current position `(row, col)` is safe by checking if `cols[col]`, `diag1[d1]`, and `diag2[d2]` are all `false`.
  - If the position is safe:
    1.  **Place Queen:** Mark `cols[col]`, `diag1[d1]`, and `diag2[d2]` as `true`.
    2.  **Recurse:** Call `backtrack(row + 1)` to solve for the next row.
    3.  **Backtrack:** Un-place the queen by resetting `cols[col]`, `diag1[d1]`, and `diag2[d2]` to `false`. This allows exploration of other possibilities.
- Start the process by calling `backtrack(0)`.
- Return the final `count`.

## Backtracking with Bitmasking Optimization
This approach refines the standard backtracking algorithm by using bitmasks (integers) instead of boolean arrays to track the state of the board. Each bit in an integer can represent a column or a diagonal, allowing for extremely fast state updates and checks using bitwise operations. This significantly improves the performance of the algorithm, even though the time complexity remains the same in Big-O terms.
**Time:** O(N!) · **Space:** O(N)
**Pros:** Extremely fast and efficient due to the use of bitwise operations.; Very low memory usage, as it only requires a few integer variables for state tracking.
**Cons:** The logic, especially the shifting of diagonal masks, can be less intuitive and harder to debug than the array-based approach.; Requires familiarity with bit manipulation techniques.
### Explanation
The fundamental backtracking structure is the same, but the implementation of state tracking is optimized. We use three integers as bitmasks:
- `cols`: A bitmask where the `i`-th bit is 1 if column `i` is occupied.
- `diag1`: A bitmask for the main diagonals (`row - col`).
- `diag2`: A bitmask for the anti-diagonals (`row + col`).

In the recursive function `solve(row, cols, diag1, diag2)`, we first compute a bitmask of all safe columns for the current `row`. The combined mask of all attacked columns is `cols | diag1 | diag2`. We can find the safe columns by inverting this mask and ensuring we only consider `n` bits: `availablePositions = ((1 << n) - 1) & ~(cols | diag1 | diag2)`.

We then iterate through each set bit in `availablePositions`. For each safe column (represented by a bit `position`), we make a recursive call for the next row. The key insight is how the diagonal masks are updated for the next row:
- The main diagonal (`row - col`) values increase by 1 for each column as we move to the next row, which corresponds to a left shift (`<< 1`) of the bitmask.
- The anti-diagonal (`row + col`) values also change consistently, which corresponds to a right shift (`>> 1`) of the bitmask.

This method avoids array lookups and replaces them with highly efficient bitwise operations, resulting in a much faster solution.

```java
class Solution {
    private int size;

    public int totalNQueens(int n) {
        this.size = n;
        return solve(0, 0, 0, 0);
    }

    private int solve(int row, int cols, int diag1, int diag2) {
        // Base case: If all rows are filled, we found one solution.
        if (row == size) {
            return 1;
        }

        int count = 0;
        // Calculate available positions in the current row.
        // ((1 << size) - 1) creates a mask with 'size' number of 1s.
        int availablePositions = ((1 << size) - 1) & (~(cols | diag1 | diag2));

        // Iterate through all available positions.
        while (availablePositions != 0) {
            // Get the least significant bit (the rightmost available column).
            int position = availablePositions & -availablePositions;

            // Remove this position from the available set for the next iteration.
            availablePositions -= position;

            // Recurse for the next row with updated masks.
            count += solve(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);
        }

        return count;
    }
}
```
### Algorithm
- Define a recursive function, say `solve(row, cols, diag1, diag2)`, where the integer parameters are bitmasks representing the occupied columns and diagonals.
- **Base Case:** If `row == n`, a valid placement has been found. Return 1.
- **Recursive Step:**
  1.  Calculate a bitmask of all available positions in the current row. The mask for all attacked columns is `(cols | diag1 | diag2)`. The mask for available columns is `((1 << n) - 1) & ~(cols | diag1 | diag2)`.
  2.  Initialize a local counter for solutions found from this state: `solutions = 0`.
  3.  Loop as long as there are available positions in the `availablePositions` mask.
  4.  In each iteration, pick one available position. A common trick is to isolate the least significant bit (rightmost '1'): `position = availablePositions & -availablePositions`.
  5.  Remove this position from the set of available positions for the current loop: `availablePositions -= position`.
  6.  Make a recursive call for the next row with updated masks and add the result to `solutions`:
     - New column mask: `cols | position`
     - New main diagonal mask: `(diag1 | position) << 1` (shifted left for the next row)
     - New anti-diagonal mask: `(diag2 | position) >> 1` (shifted right for the next row)
     - `solutions += solve(row + 1, new_cols, new_diag1, new_diag2)`.
  7.  Return the total `solutions` found.
- The initial call to start the process is `solve(0, 0, 0, 0)`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int TotalNQueens(int n) {
        bool[] cols = new bool[10];
        bool[] dg = new bool[20];
        bool[] udg = new bool[20];
        int ans = 0;
        void dfs(int i) {
            if (i == n) {
                ans++;
                return;
            }
            for (int j = 0; j < n; j++) {
                int a = i + j, b = i - j + n;
                if (cols[j] || dg[a] || udg[b]) {
                    continue;
                }
                cols[j] = dg[a] = udg[b] = true;
                dfs(i + 1);
                cols[j] = dg[a] = udg[b] = false;
            }
        }
        dfs(0);
        return ans;
    }
}
```

### Java

```java
class Solution {
private
  int n;
private
  int ans;
private
  boolean[] cols = new boolean[10];
private
  boolean[] dg = new boolean[20];
private
  boolean[] udg = new boolean[20];
public
  int totalNQueens(int n) {
    this.n = n;
    dfs(0);
    return ans;
  }
private
  void dfs(int i) {
    if (i == n) {
      ++ans;
      return;
    }
    for (int j = 0; j < n; ++j) {
      int a = i + j, b = i - j + n;
      if (cols[j] || dg[a] || udg[b]) {
        continue;
      }
      cols[j] = true;
      dg[a] = true;
      udg[b] = true;
      dfs(i + 1);
      cols[j] = false;
      dg[a] = false;
      udg[b] = false;
    }
  }
}

```

### JavaScript

```javascript
function totalNQueens ( n ) { const cols = Array ( 10 ). fill ( false ); const dg = Array ( 20 ). fill ( false ); const udg = Array ( 20 ). fill ( false ); let ans = 0 ; const dfs = i => { if ( i === n ) { ++ ans ; return ; } for ( let j = 0 ; j < n ; ++ j ) { let [ a , b ] = [ i + j , i - j + n ]; if ( cols [ j ] || dg [ a ] || udg [ b ]) { continue ; } cols [ j ] = dg [ a ] = udg [ b ] = true ; dfs ( i + 1 ); cols [ j ] = dg [ a ] = udg [ b ] = false ; } }; dfs ( 0 ); return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int totalNQueens(int n) {
    bitset<10> cols;
    bitset<20> dg;
    bitset<20> udg;
    int ans = 0;
    function<void(int)> dfs = [&](int i) {
      if (i == n) {
        ++ans;
        return;
      }
      for (int j = 0; j < n; ++j) {
        int a = i + j, b = i - j + n;
        if (cols[j] || dg[a] || udg[b])
          continue;
        cols[j] = dg[a] = udg[b] = 1;
        dfs(i + 1);
        cols[j] = dg[a] = udg[b] = 0;
      }
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def totalNQueens(self, n: int) -> int: def dfs(i: int): if i == n: nonlocal ans ans += 1 return for j in range(n): a, b = i + j, i - j + n if cols[j] or dg[a] or udg[b]: continue cols[j] = dg[a] = udg[b] = True dfs(i + 1) cols[j] = dg[a] = udg[b] = False cols = [False] * 10 dg = [False] * 20 udg = [False] * 20 ans = 0 dfs(0) return ans

```