class Solution {
    vector> result;
public:
    bool canPlace(int i, int j, vector &tmp, int n){
        if(i == 0) return true;
        for(int k = 0; k < i; k++){
            if(tmp[k][j] == 'Q') return false;
        }
        for(int p = 0; p < i; p++){
            for(int q = 0; q < n; q++){
                if((p-q == i-j || p+q == i+j) && tmp[p][q] == 'Q'){
                    return false;
                }
            }
        }
        return true;
    }

    vector possiblePlaces(int i, vector &tmp, int n){
        vector places;
        
        for(int j = 0; j < n; j++){
            if(canPlace(i,j,tmp, n)){
                places.push_back(j);
            }
        }
        return places;
    }
    
    void dfs(int level, vector &tmp, int n){
        if(level >= n){
            result.push_back(tmp);
            return;
        }
        
        vector places = possiblePlaces(level, tmp, n);
        int j;
        for(int k = 0; k < places.size(); k++){
            j = places[k];
            tmp[level][j] = 'Q';
            dfs(level + 1, tmp, n);
            tmp[level][j] = '.';
        }
        
    }

    vector > solveNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        result. clear();
        vector tmp(n, string(n, '.'));
        dfs(0, tmp, n);
        
        return result;
    }
};