// 1- take a temporary vector of string and initialise it with '.' as mensioned in the problem.
// 2- make a dfs call for any row-index (let say 0).
// 3- while traversing make sure if u are getting a valid position in the vector string assign it 'Q' and check if u have traversed every row once, If u have then this vector string will be one of the valid answer. Traverse until u got all possible answer.
// 4- while checking for valid position make sure u are checking for every diagonal position from current assumed valid position and also the corresponding row and column.
class Solution {
public:
    
    bool isValid(int i,int j,int n,vector<string>&vec)
    {
        int a=i,b=j;
        for(int k=0;k<n;k++)
        {
            if(vec[i][k]=='Q') return false;
            if(vec[k][j]=='Q') return false;
        }
        while(a>=0 && b>=0)
        {
            if(vec[a][b]=='Q') return false;
            a--,b--;
        }
        a=i,b=j;
        while(a<n && b>=0)
        {
            if(vec[a][b]=='Q') return false;
            a++,b--;
        }
        a=i,b=j;
        while(a>=0 && b<n)
        {
            if(vec[a][b]=='Q') return false;
            a--,b++;
        }
        a=i,b=j;
        while(a<n && b<n)
        {
            if(vec[a][b]=='Q') return false;
            a++,b++;
        }
        return true;
    }
    void dfs(vector<string>&vec,int idx,int n,vector<vector<string>>&ans)
    {
        if(idx==n)
        {
            ans.push_back(vec);
            return ;
        }
        for(int i=0;i<n;i++)
        {
            if(isValid(idx,i,n,vec))
            {
                vec[idx][i]='Q';
                dfs(vec,idx+1,n,ans);
                vec[idx][i]='.';
            }
        } 
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>>ans;
        vector<string>vec(n,string(n,'.'));
        dfs(vec,0,n,ans);
        return ans;
    }
};