The n-queens puzzle is the problem of placing n _queens on an _n×_n _chess board such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        List<Integer> line = new ArrayList<>(n);
        helper(line, n);
        return count;
    }

    public void helper(List<Integer> line, int n) {
        if(line.size() == n) {
            count++;
            return;
        }

        for(int i = 0; i < n; i++) {
            if(isValid(line, i)) {
                line.add(i);
                helper(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;
    }
}