# 30. N-Queen Problem

The problem can be found at the following link: [Problem Link](https://practice.geeksforgeeks.org/problems/n-queen-problem/1)

## **Problem Description**

The N-Queen problem is a classic combinatorial problem where you are tasked with placing `N` queens on an `N x N` chessboard such that no two queens threaten each other. This means:

* No two queens share the same row.
* No two queens share the same column.
* No two queens share the same diagonal.

Your task is to return a list of all possible solutions, where each solution represents the board configuration as a list of integers. Each integer in the list represents the column index (1-based) of the queen for each row.

![image](https://github.com/user-attachments/assets/ec8facf8-b951-4455-8a96-4e6dbdab1936)

## **Examples**

### Example 1

**Input:**\
`N = 4`

**Output:**\
`[[2, 4, 1, 3], [3, 1, 4, 2]]`

**Explanation:**\
For `N = 4`, two solutions exist:

* Solution 1:

  ```
  . Q . .
  . . . Q
  Q . . .
  . . Q .
  ```
* Solution 2:

  ```
  . . Q .
  Q . . .
  . . . Q
  . Q . .
  ```

### Example 2

**Input:**\
`N = 1`

**Output:**\
`[[1]]`

**Explanation:**\
For `N = 1`, only one solution exists:

* Solution 1:

  ```
  Q
  ```

## **Constraints**

* `1 <= N <= 10`

## **My Approach**

The N-Queen problem can be efficiently solved using **bitwise operations** to track occupied columns and diagonals:

1. Use three bitmasks:
   * `cols`: Tracks occupied columns.
   * `d1`: Tracks occupied left diagonals (sum of row and column indices is constant).
   * `d2`: Tracks occupied right diagonals (difference of row and column indices is constant).
2. Backtrack recursively:
   * Place a queen in a valid column of the current row.
   * Mark the column and diagonals as occupied.
   * Move to the next row.
   * If a solution is found, add it to the result.
   * Backtrack by unmarking the column and diagonals.

This method reduces unnecessary checks and speeds up the solution.

## Time and Auxiliary Space Complexity

* **Expected Time Complexity:**
* **O(N!)**, where **N** is the number of queens.\
  Each row has **N** possibilities initially, and this reduces with each row.
* **Worst-Case Time Complexity:** **O(N!)**
  * For the first queen, there are `N` choices.
  * For the second queen, there are `N-1` choices, and so on.
  * Thus, the total complexity is `O(N * (N-1) * (N-2) * ... * 1) = O(N!)`.
* **Expected Auxiliary Space Complexity:** **O(N)**, where **N** is the space used for recursive calls and the row configuration array.

## Code (C++)

```cpp
class Solution {
public:
    vector<vector<int>> nQueen(int n) {
        if (n < 4 && n != 1) return {};
        vector<vector<int>> res;
        vector<int> row(n);

        auto solve = [&](auto&& self, int c, int cols, int d1, int d2) -> void {
            if (c == n) { res.push_back(row); return; }
            for (int r = 0, pos = 1; r < n; ++r, pos <<= 1)
                if (!(cols & pos || d1 & (pos << c) || d2 & (pos << (n - 1 - c))))
                    row[c] = r + 1, self(self, c + 1, cols | pos, d1 | (pos << c), d2 | (pos << (n - 1 - c)));
        };

        solve(solve, 0, 0, 0, 0);
        return res;
    }
};
```

<details>

<summary>👨‍💻 Alternative Approaches</summary>

### **1️⃣ Bitmasking + Backtracking (Most Optimized)**

This approach uses **bitwise operations** to efficiently track columns and diagonals.

```cpp
class Solution {
public:
    vector<vector<int>> nQueen(int n) {
        if (n == 2 || n == 3) return {};
        vector<vector<int>> result;
        vector<int> row(n);

        auto solve = [&](auto&& self, int c, int cols, int d1, int d2) -> void {
            if (c == n) { result.push_back(row); return; }
            for (int pos = ((1 << n) - 1) & ~(cols | d1 | d2); pos; pos &= pos - 1) {
                int r = __builtin_ctz(pos);
                row[c] = r + 1;
                self(self, c + 1, cols | (1 << r), (d1 | (1 << r)) << 1, (d2 | (1 << r)) >> 1);
            }
        };

        solve(solve, 0, 0, 0, 0);
        return result;
    }
};
```

#### **Key Optimizations**

✅ **Bitwise tracking** of column, left-diagonal, and right-diagonal.\
✅ **Eliminates extra loops** for checking conflicts.\
✅ **Fastest pruning** using `__builtin_ctz(pos)` (extracts least significant set bit).

### **2️⃣ One-Dimensional Array + Backtracking**

This approach eliminates the need for extra space for diagonal checks.

```cpp
class Solution {
public:
    vector<vector<int>> nQueen(int n) {
        if (n == 2 || n == 3) return {};
        vector<vector<int>> result;
        vector<int> row(n);

        function<void(int, vector<bool>&, vector<bool>&, vector<bool>&)> solve = [&](int c, vector<bool>& cols, vector<bool>& d1, vector<bool>& d2) {
            if (c == n) { result.push_back(row); return; }
            for (int r = 0; r < n; r++) {
                if (cols[r] || d1[c - r + n - 1] || d2[c + r]) continue;
                row[c] = r + 1;
                cols[r] = d1[c - r + n - 1] = d2[c + r] = true;
                solve(c + 1, cols, d1, d2);
                cols[r] = d1[c - r + n - 1] = d2[c + r] = false;
            }
        };

        vector<bool> cols(n, false), d1(2 * n - 1, false), d2(2 * n - 1, false);
        solve(0, cols, d1, d2);
        return result;
    }
};
```

#### **Key Optimizations**

✅ Uses **three boolean arrays** instead of nested loops.\
✅ Reduces **O(n) conflict checks** per column to **O(1) using precomputed indices**.\
✅ **Backtracks efficiently** without unnecessary calculations.

#### **Comparison of Approaches**

| Approaches                              | Time Complexity | Space Complexity | Best For            |
| --------------------------------------- | --------------- | ---------------- | ------------------- |
| **Bitmasking + Recursion (1️⃣)**        | **O(n!)**       | **O(n)**         | Large `n` (Fastest) |
| **Boolean Arrays (Backtracking) (2️⃣)** | **O(n!)**       | **O(n)**         | Simplicity          |

#### **Final Recommendation**

* **For Competitive Coding** → Use **Bitmasking (1️⃣)**
* **For Readability + Optimization** → Use **Boolean Arrays (2️⃣)**

🚀 **The fastest approach for large `n` is 1️⃣ (Bitmasking + Backtracking).**

</details>

## Code (Java)

```java
class Solution {
    public ArrayList<ArrayList<Integer>> nQueen(int n) {
        if (n < 4 && n != 1) return new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int[] row = new int[n];
        solve(0, 0, 0, 0, n, row, res);
        return res;
    }

    private void solve(int c, int cols, int d1, int d2, int n, int[] row, ArrayList<ArrayList<Integer>> res) {
        if (c == n) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int r : row) temp.add(r + 1);
            res.add(temp);
            return;
        }
        for (int r = 0, pos = 1; r < n; ++r, pos <<= 1)
            if ((cols & pos) == 0 && (d1 & (pos << c)) == 0 && (d2 & (pos << (n - 1 - c))) == 0) {
                row[c] = r;
                solve(c + 1, cols | pos, d1 | (pos << c), d2 | (pos << (n - 1 - c)), n, row, res);
            }
    }
}
```

## Code (Python)

```python
class Solution:
    def nQueen(self, n):
        if n < 4 and n != 1:
            return []
        res = []
        row = [0] * n

        def solve(c, cols, d1, d2):
            if c == n:
                res.append([r + 1 for r in row])
                return
            for r in range(n):
                pos = 1 << r
                if not (cols & pos or d1 & (pos << c) or d2 & (pos << (n - 1 - c))):
                    row[c] = r
                    solve(c + 1, cols | pos, d1 | (pos << c), d2 | (pos << (n - 1 - c)))

        solve(0, 0, 0, 0)
        return res
```

## Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

***

#### 📍Visitor Count

<div align="center"><img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" alt=""></div>
