Then-queens puzzle is the problem of placingn_queens on an_n×_n_chessboard such that no two queens attack each other.

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

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

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resStr = new ArrayList<>();
        if(n < 1)
            return resStr;

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> line = new ArrayList<>(n);
        helper(res, line, n);

        for(List<Integer> r: res) {
            List<String> solution = new ArrayList<>();
            for(Integer position: r) {
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < n; i++) {
                    if(i != position)
                        sb.append('.');
                    else
                        sb.append('Q');
                }
                solution.add(sb.toString());
            }
            resStr.add(solution);
        }

        return resStr;
    }

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

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

    public boolean isValid(List<Integer> line, int num) {
        int next = line.size();
        for(int i = 0; i < line.size(); i++) {
            if(line.get(i) == num)
                return false;

            if(Math.abs(num - line.get(i)) == next - i)
                return false;
        }

        return true;
    }
}