51. Added N-Queen Solution in C++

[purrvax]

Problem Number

51

Problem Title

N-Queen

LeetCode Link

https://leetcode.com/problems/n-queens/

Contribution Checklist

• I have written the Approach section.
• I have written the Intuition section.
• I have included a working C++ solution.
• I will raise a PR and ensure the filename follows the convention [Number]. [Problem Title].cpp.

Approach

1. We place one queen per column, moving from left to right (col = 0 to n−1).
2. For each column, we try placing the queen in every possible row (row = 0 to n−1).
3. Before placing a queen at (row, col), we instantly check if it’s safe using three helper arrays:

leftrow[row] → checks if any queen is already in that row
lowerdiagonal[row + col]
upperdiagonal[n - 1 + col - row] checks diagonal

4. If the position is safe, we place the queen, mark those hashes as occupied, and move to next column using recursion.
5. If we reach col == n, it means all queens are successfully placed → we store the current board as one valid answer.
6. After exploring that path, we backtrack remove the queen and unmark the hash arrays, then try next row.

Continue this process until all possibilities are explored — storing all valid solutions.

Intuition

The N-Queens problem is solved using recursion and backtracking by placing exactly one queen in each column, ensuring that no two queens attack each other. Since every queen must be in a unique column, we only need to check whether the current row and both diagonals are safe before placing a queen. To make this safety check instant (O(1) time), we maintain three hash arrays: one to mark which rows are already occupied, and two more to track the lower-left and upper-left to diagonals. If the chosen (row, col) position is safe according to all three, we place the queen and recursively move to the next column. If we get stuck later, we backtrack removing the queen and trying another row.
This efficient hashing approach eliminates the need to scan the entire board for conflicts, and drastically reduces time complexity from O(N³ or N⁴) to roughly O(N!), allowing us to explore all valid arrangements quickly while naturally discarding invalid ones using backtracking.

Solution in C++

class Solution {
public:
    // Function to check if placing a queen at (row, col) is safe
    bool isSafe(int row, int col, vector<string> &temp, int n) {
        int duprow = row;
        int dupcol = col;
        // Check all columns to the left in the same row
        for (int j = 0; j < col; j++) {
            if (temp[row][j] == 'Q') return false;
        }

        // Check upper-left diagonal
        while(row >= 0 && col >= 0){
            if(temp[row][col] == 'Q') return false;
            row--;
            col--;
        }
        row = duprow;
        col = dupcol;
        // Check lower-left diagonal
        while(row < n && col >= 0){
            if(temp[row][col] == 'Q') return false;
            row++;
            col--;
        }

        return true;
    }

    // Backtracking function to place queens column by column
    void solve(int col, vector<string> temp, vector<vector<string>> &ans, int n) {
        // If all columns are filled, add current board to answer
        if (col == n) {
            ans.push_back(temp);
            return;
        }

        for (int row = 0; row < n; row++) {
            if (isSafe(row, col, temp, n)) {
                // Place queen
                temp[row][col] = 'Q';
                // Recurse for next column
                solve(col + 1, temp, ans, n); 
                // Backtrack and remove queen
                temp[row][col] = '.';        
            }
        }
    }

    // Main function to call backtracking
    vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ans;
    vector<string> temp;
    string s(n, '.');
    for(int i = 0 ; i < n ; i++) temp.push_back(s); // FIXED

    solve(0, temp, ans, n);
    return ans;
}

};

[github-actions]

Hope so You have raised a valid issue, wait untill the owner will review the issue