/**
knakul853
**/
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {

        vector<vector<string>>ans;
        vector<string>temp(n, string(n, '.'));

        dfs(n, 0, ans, temp );

        return ans;
    }

    void dfs(int n, int id, vector<vector<string>>&ans, vector<string>&temp)
    {
        if( id == n ){
            ans.push_back(temp);
            return;
        }

        for(int i=0;i<n;i++)
        {
            if(ok(temp, id, i, n)){
                temp[id][i] = 'Q';

                dfs(n, id+1, ans, temp);

                temp[id][i] = '.';
            }
        }
    }

    bool ok( vector<string>& dp, int row, int col, int n){

        for( int i=0;i<row;i++ ){
            if( dp[i][col] == 'Q' ) return false;
        }

        for(int i=row-1 , j = col-1; i>=0 && j>=0; i--,j--){
            if(dp[i][j] == 'Q') return false;
        }

        for(int i=row-1, j = col+1;i >=0 && j<n ; i--, j++)
        {
            if( dp[i][j] == 'Q') return false;
        }

        return true;

    }
};