51

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> state;
    bool visd[30], visad[30], vis[30];
    vector<vector<string>> fans;

    vector<vector<string>> solveNQueens(int n) {
        backtrack(0, n);
        convertToString(n);
        return fans;
    }

    void backtrack(int col, int n){
        if(col == n){
            ans.push_back(state);
            return;
        }
        for(int row=0; row<n; row++){
            if(!vis[row] && !visd[row-col+n-1]  && !visad[row+col]){
                vis[row] = visd[row-col+n-1] = visad[row+col] = true;
                state.push_back(row);
                backtrack(col+1, n);
                state.pop_back();
                vis[row] = visd[row-col+n-1] = visad[row+col] = false;
            }
        }
    }

    void convertToString(int n){
        for(int k=0; k<ans.size(); k++){
            vector<string> pat;
            for(int i=0; i<n; i++){
                string s;
                for(int j=0; j<n; j++)
                    s += ".";
                s[ans[k][i]] = 'Q';
                pat.push_back(s);
            }
            fans.push_back(pat);
        }
    }

};