class Solution {
    vector<vector<string>> ans;
    vector<string> path;
    vector<bool> a,b,c;
  
public:
    vector<vector<string>> solveNQueens(int n) {
        a = vector<bool>(n);
        b = c = vector<bool>(2*n);
        path = vector<string>(n,string(n,'.'));
        dfs(0,n);
        return ans;
    }
    void dfs(int x,int n){
        if(x == n){
            ans.push_back(path);
            return ;
        }
        for(int i=0;i<n;i++){
            if(a[i] || b[i-x+n] || c[i+x]) continue;
            a[i] = b[i-x+n] = c[i+x] = true;
            path[x][i] = 'Q';
            dfs(x+1 , n);
            path[x][i] = '.';
            a[i] = b[i-x+n] = c[i+x] = false;
        }
    }
};