Problem Statement

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Problem Link

N-Queens - LeetCode

Reference Link

https://www.youtube.com/watch?v=i05Ju7AftcM&ab_channel=takeUforward

Code

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        
        vector<vector<string>> ans;
        vector<string> board(n);
        
        string s(n,'.');
        
        for(int i=0;i<n;i++)
            board[i] = s;
        
        solve(ans,board,n,0);
        
        return ans;
        
    }
    void solve(vector<vector<string>> &ans,vector<string> &board,int n,int col)
    {
        if(col==n)
        {
            ans.push_back(board);
            return;
        }
        
        **// Do not make nested for loops**
				for(int row=0;row<n;row++)
        {
            if(isSafe(board,n,row,col))
            {
                board[row][col] = 'Q';
                solve(ans,board,n,col+1);
                board[row][col] = '.';
            }
        }
    }
    bool isSafe(vector<string> &board,int n,int row,int col)
    {
        int duprow = row;
        int dupcol = col;
        
        while(row>=0 and col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            
            row--;col--;
        }
        row = duprow;
        col = dupcol;
        
        while(col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            
            col--;
        }
        row = duprow;
        col = dupcol;
        
        while(row<=n-1 and col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            
            row++;col--;
        }
        
        return true;
    }
};

Time Optimized Solution

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        
        vector<vector<string>> ans;
        vector<string> board(n);
        
        string s(n,'.');
        
        for(int i=0;i<n;i++)
            board[i] = s;
        
        vector<int> leftrow(n,0),upperDiag(2*n-1,0),lowerDiag(2*n-1,0);
        solve(ans,board,n,0,leftrow,upperDiag,lowerDiag);
        
        return ans;
        
    }
    void solve(vector<vector<string>> &ans,vector<string> &board,int n,int col,vector<int> &leftrow,vector<int> &upperDiag,vector<int> &lowerDiag)
    {
        if(col==n)
        {
            ans.push_back(board);
            return;
        }
        
        for(int row=0;row<n;row++)
        {
            if(!leftrow[row] and !upperDiag[n-1+(col-row)] and !lowerDiag[row+col])
            {
                board[row][col] = 'Q';
                upperDiag[n-1+(col-row)] = 1;
                lowerDiag[row+col] = 1;
                leftrow[row] = 1;
                solve(ans,board,n,col+1,leftrow,upperDiag,lowerDiag);
                board[row][col] = '.';
                upperDiag[n-1+(col-row)] = 0;
                lowerDiag[row+col] = 0;
                leftrow[row] = 0;
            }
        }
    }
   
};