class Solution {

    public List<List<String>> solveNQueens(int n) {

        List<String> ans = new ArrayList<String>();

        //initialize ans

        for(int i = 0; i < n; i++){

            StringBuilder s = new StringBuilder();

            for(int j = 0; j < n; j++){

                s.append(".");

            }

            ans.add(s.toString());

        }

        dfs(n,0,ans);

        return ret;

    }

    public void dfs(int n, int depth, List<String> ans){

        if(depth == n) {

            List<String> new_ans = new ArrayList<String>(ans);

            ret.add(new_ans);

            return;

        }

        StringBuilder strBuilder = new StringBuilder(ans.get(depth));

        for(int i = 0; i < n; i++){

            if(check(n, ans, depth, i)) continue; //already have Q in this column

            strBuilder.setCharAt(i, 'Q');

            ans.set(depth, strBuilder.toString());

            dfs(n, depth+1, ans);

            strBuilder.setCharAt(i, '.'); //recover

            ans.set(depth, strBuilder.toString());

        }

    }

    public Boolean check(int n, List<String> ans, int i, int j){

        for(int k = 0; k < i; k++){ //iterate n line

            //i-k = j-x => x = j+k-i; i-k = x-j => x = i+j-k

            if( ans.get(k).charAt(j) == 'Q'

               ||(j+k-i >= 0 && ans.get(k).charAt(j+k-i) == 'Q')

               || (i+j-k < n && ans.get(k).charAt(i+j-k) == 'Q'))

                return true;

        }

        return false;

    }

    private List<List<String>> ret = new ArrayList<>();

}