The n-queens puzzle is the problem of placing n queens on ann×nchessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.

public class Solution {
    /*
     * @param n: The number of queens
     * @return: All distinct solutions
     */
    public List<List<String>> solveNQueens(int n) {
        // write your code here
        List<List<String>> ans = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        if (n == 0) {
            ans.add(new ArrayList<>());
            return ans;
        }
        dfs(n, cur, ans);
        return ans;
    }

    public void dfs(int n, List<Integer> cur, List<List<String>> ans) {
        //exit
        if (cur.size() == n) {
            ans.add(getChessBoard(cur));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!isValid(i, cur)) {
                continue;
            }
            cur.add(i);
            dfs(n, cur, ans);
            cur.remove(cur.size() - 1);
        }
    }

    public List<String> getChessBoard(List<Integer> cur) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < cur.size(); i++) {
            String current = "";
            for (int j = 0; j < cur.size(); j++) {
                if (j == cur.get(i)) {
                    current += "Q";
                } else {
                    current += ".";
                }
            }
            ans.add(new String(current));
        }

        return ans;
    }



    public boolean isValid(int j, List<Integer> cur) {


        for (int i = cur.size() - 1, off = 1; i >= 0; i--,off++) {
            //check vertical up
            if (cur.get(i) == j) {
                return false;
            }

            //check left up
            if (cur.get(i) == (j - off)) {
                return false;
            }

            //check right up
            if (cur.get(i) == (j + off)) {
                return false;
            }
        }

         return true;

    }


}