52. N-Queens II

📝 Problem Details

• Title: 52. N-Queens II
• **Link:**https://leetcode.com/problems/n-queens-ii/
• Difficulty: Hard
• Tags/Categories: Dynamic-Programming Backtracking

💭What Were My Initial Thoughts?

we need to return the number of distinct solutions to the n queens puzzle. 
- i guess a place to start is to break down what is a valid form of the puzzle 
- for a given queen, for each possible move range (directly up,down,left,right, upleft, upright, downright, downleft) there is not another queen in that point of sight. 
- this means that the queen cannot "attack" another queen given the above rule - now how would we solve this algorithmically? 
- well we arent given a grid array, instead the input is an integer which just represents the number of queens. 
- so this might indicate that we should be constructing an explicity matrix to represent a board. 
- okay lets take a look at the input constaints, the board is always n*n size, and there will be n queens on that board 
	- n is between 1 - 9 inclusive - lets see if starting from the simplest case helps - start at n=1, there can only be one possible position for a n*n board of size 1 with only a size queen 
	- what about n=2 where we now have a board with 4 cells and 2 queens. 
	- based on my observation, the valid output is 0 since there are no conditions where a queen is not attackable by another 
	- n=3 seems to have no possible states either (i am trying to find a pattern but cant seem to find it)

🤔What Did I Struggle With?

could not find pattern with smaller input cases 

forgot about the rule of 1 queen per row as a general requirement

💡 Explanation of Solution

1. use 1D array queens[row] = col to store queen position
2. use three sets to track unsafe positions
	- columns: keeps track of used columns
	- mainDiagonal (row - col): tracks diagonals sloping /
	- antiDiagonal (row + col): tracks diagonals sloping \

3. backtracking strategy
	- place a queen in each row 
	- if a placement is valid, move to the next row:
		- no conflicts in column, diagonal or anti-diagonal
	- if all n queens are placed, increment the count 

⌛ Complexity Analysis

Time Complexity: O(N!)
	- each row has at most N choices initially, then fewer as the board fills up
	- time complexity is acceptable given the input constraints being low

Space Complexity: O(N)
	- for column and diagonal sets

💻 Implementation of Solution

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        unordered_set<int> columns, mainDiagonal, antiDiagonal;
        backtrack(0, n, columns, mainDiagonal, antiDiagonal, count);
        return count;
    }
 
private:
    void backtrack(int row, int n, unordered_set<int>& columns, 
                   unordered_set<int>& mainDiagonal, unordered_set<int>& antiDiagonal, int& count) {
        if (row == n) {
            count++;
            return;
        }
 
        for (int col = 0; col < n; col++) {
            if (columns.count(col) || mainDiagonal.count(row - col) || antiDiagonal.count(row + col))
                continue;
 
            // Place the queen
            columns.insert(col);
            mainDiagonal.insert(row - col);
            antiDiagonal.insert(row + col);
 
            // Recur for the next row
            backtrack(row + 1, n, columns, mainDiagonal, antiDiagonal, count);
 
            // Remove the queen (backtrack)
            columns.erase(col);
            mainDiagonal.erase(row - col);
            antiDiagonal.erase(row + col);
        }
    }
};