Skip to content

Latest commit

 

History

History
290 lines (214 loc) · 8.42 KB

Day 3 - N-Queen Problem.md

File metadata and controls

290 lines (214 loc) · 8.42 KB
Difficulty Source Tags
Hard
160 Days of Problem Solving
Backtracking

🚀 Day 3. N-Queen Problem 🧠

The problem can be found at the following link: Problem Link

💡 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

🔍 Example Walkthrough:

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.

📝 Solution Code

Code (C++)

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;
    }
};

👨‍💻 Alternative Approaches

1️⃣ Bitmasking + Backtracking (Most Optimized)

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

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.

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).

Code (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)

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. Let’s make this learning journey more collaborative!

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

📍Visitor Count