51. N-Queens

📝 Problem Details

• Title: 51. N-Queens
• Link: https://leetcode.com/problems/n-queens/
• Difficulty: Hard
• Tags/Categories: Backtracking

placing n queens on an n x n chessboard such that no two queens attack each other input integer n, return all distinct solutions to the n-queen puzzle a board is represented as a single-dimension vector<string> , where a single string represents one row of the board Q and . indicate the placement of a queen and empty space respectively

💭What Were My Initial Thoughts?

- important rules and observations to clarify / identify
	- queens can attack anything to the left,right,up,down or diagonal of them
	- given n queens, and an n*n board, that would mean that there would have to be exactly 1 queen placement per row of the board 
- "all-possible" indicates an enumeration backtracking problem 

- choices:
	- for each column in a given row, choose to either place a queen or leave it empty
	- the constraint could be whether the queen is attackable from that position by another queen

🤔What Did I Struggle With?

how to track constraints (whether a queen placement is in danger of being attacked) without re-scanning the board each time 

💡 Explanation of Solution

- create nxn board (initialized with dots ".")
- use sets to track conflicts
	- cols: columns where queens are placed
	- mainDiags: `row - col` tracks left diagonals
	- antiDiags: `row + col` tracks right diagonals
- start DFS (row = 0)
	- for each column, check if placing a queen is valid
	- if valid, place the queen and mark its column and diagonals
	- recurse to the next row
	- backtrack by removing the queen and unmarking the column/diagonals 

⌛ Complexity Analysis

Time Complexity: O(N!) for DFS recursion
O(1) for checking validity of queen-placement per recursive call

Space Complexity: O(N)


**N-Queens is still an enumeration problem,** but with **a permutation-like constraint** that makes its complexity factorial instead of exponential.

💻 Implementation of Solution

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        vector<vector<string>> result;
        unordered_set<int> cols;
        unordered_set<int> mainDiags;
        unordered_set<int> antiDiags;
 
        dfs(n, 0, board, result, cols, mainDiags, antiDiags);
        return result;
    }
 
void dfs(int n, int row, 
         vector<string>& board, 
         vector<vector<string>>& result,
         unordered_set<int>& cols, 
         unordered_set<int>& mainDiags, 
         unordered_set<int>& antiDiags) {
 
    // Base case: A valid board configuration is found
    if (row == n) {
        result.push_back(board);
        return;
    }
 
    // Explore column positions for this row
    for (int col = 0; col < n; col++) { 
 
        // Check if this column or diagonals are occupied
        if (cols.count(col) || mainDiags.count(row - col) || antiDiags.count(row + col)) {
            continue; // Skip invalid placements
        }
 
        // Place the queen
        board[row][col] = 'Q';
        cols.insert(col);
        mainDiags.insert(row - col);
        antiDiags.insert(row + col);
 
        // Recurse to the next row
        dfs(n, row + 1, board, result, cols, mainDiags, antiDiags);
 
        // Backtrack (undo placement)
        board[row][col] = '.';
        cols.erase(col);
        mainDiags.erase(row - col);
        antiDiags.erase(row + col);
    }
}
 
 
};