n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。

给定一个整数n，返回所有不同的n皇后问题的解决方案。

每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

（第三次写的感悟）抛开drawChessboard和isValid这两个辅助方法，这题就是一个简单的和permutaiton，subset类似的dfs题，只是在这个dfs里面需要用isValid来判断下数字能不能放到clist里面去，用drawChessboard来把integer的clist转成string的clist存到res里面去。
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if(n <= 0) return res;

        search(res, new ArrayList<Integer>(), n);
        return res;
    }

    private void search(List<List<String>> res, List<Integer> cols, int n) {
        //cols代表从0行到第n-1行queen所放处列的index
        if(cols.size() == n) {
            res.add(drawChessboard(cols));
            return;
        }

        for(int colIndex = 0; colIndex < n; colIndex++) {
            if(!isValid(cols, colIndex)) continue;
            cols.add(colIndex);
            search(res, cols, n);
            cols.remove(cols.size() - 1);
        }
    }

    private List<String> drawChessboard(List<Integer> cols) {
        List<String> chessboard = new ArrayList<>();
        for(int i = 0; i < cols.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < cols.size(); j++) {
                if(j == cols.get(i)) {
                    sb.append('Q');
                }else {
                    sb.append('.');
                }
            }
            chessboard.add(sb.toString());
        }
        return chessboard;
    }

    private boolean isValid(List<Integer> cols, int column) {
        int row = cols.size();
        for(int rowIndex = 0; rowIndex < cols.size(); rowIndex++) {
            if(cols.get(rowIndex) == column) return false;
            if(rowIndex + cols.get(rowIndex) == row + column) return false;
            if(rowIndex - cols.get(rowIndex) == row - column) return false;
        }
        return true;
    }
}


第二次做
好理解 但是不如上面的好，可以优化为上面的版本
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<Integer>> intRes = queens(n);
        return convert(intRes);
    }

    private List<List<Integer>> queens(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> clist = new ArrayList<>();
        helper(res, clist, n);
        return res;
    }

    private void helper(List<List<Integer>> res, List<Integer> clist, int n) {
        if(clist.size() == n) {
            res.add(new ArrayList<>(clist));
            return;
        }

        for(int i = 0; i < n; i++) { //循环第一行每个位置
            if(isValid(clist, i)) {
                clist.add(i);
                helper(res, clist, n); //深入下去每一行
                clist.remove(clist.size()-1);
            }
        }
    }

    private boolean isValid(List<Integer> clist, int i) {
        int row = clist.size();
        for(int j = 0; j < row; j++) {
            if(clist.get(j) == i) return false;
            if(j + clist.get(j) == row + i) return false;
            if(j - clist.get(j) == row - i) return false;
        }
        return true;
    }

    private List<List<String>> convert(List<List<Integer>> intList) {
        List<List<String>> res = new ArrayList<>();
        for(int i = 0; i < intList.size(); i++) {
            List<String> clist = new ArrayList<>();
            for(int j = 0; j < intList.get(i).size(); j++) {
                StringBuilder sb = new StringBuilder();
                for(int m = 0; m < intList.get(i).size(); m++) {
                    if(m == intList.get(i).get(j)) sb.append("Q");
                    else sb.append(".");
                }
                clist.add(sb.toString());
            }
            res.add(clist);
        }
        return res;
    }
}

第三次做
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<Integer> clist = new ArrayList<>();
        helper(n, res, clist);
        return res;
    }

    private void helper(int n, List<List<String>> res, List<Integer> clist) {
        if(clist.size() == n) {
            res.add(draw(clist));
        }

        for(int i = 0; i < n; i++) {
            if(isValid(i, clist)) {
                clist.add(i);
                helper(n, res, clist);
                clist.remove(clist.size()-1);
            }
        }
    }

    private boolean isValid(int i, List<Integer> clist) {
        if(clist.size() == 0) return true;
        for(int j = 0; j < clist.size(); j++) {
            if(i == clist.get(j)) return false;
            if(j + clist.get(j) == i + clist.size()) return false;
            if(j - clist.get(j) == clist.size() - i) return false;
        }
        return true;
    }

    private List<String> draw(List<Integer> clist) {
        List<String> res = new ArrayList<>();
        for(int i = 0; i < clist.size(); i++) {
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < clist.size(); j++) {
                if(j != clist.get(i)) sb.append(".");
                else sb.append("Q");
            }
            res.add(new String(sb));
        }
        return res;
    }
}