Problem: N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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

class Solution {
    public List<List<String>> solveNQueens(int n) {
        return fun(new ArrayList<String>(), n, 0);
    }
    private static List<List<String>> fun(ArrayList<String> s, int n, int r) {
        List<List<String>> l = new ArrayList<List<String>>();
        if(n==r){
            l.add(new ArrayList<>(s));
            return l;
        }
        for (int i = 0; i < n; i++) {
            String st = check(s,n,r,i);
            if(!st.equals("")){
                s.add(st);
                l.addAll(fun(s,n,r+1));
                s.remove(s.size()-1);
            }
        }
        return l;
    }
    static String check(ArrayList<String> s, int n, int r, int c){
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < r; i++) {
            if(s.get(i).charAt(c)=='Q')
                return st.toString();
        }
        int a = r-1, b = c-1;
        while(a>=0 && b>=0){
            if(s.get(a).charAt(b)=='Q')
                return st.toString();
            a--; b--;
        }
        a = r-1;
        b = c+1;
        while(a>=0 && b<n){
            if(s.get(a).charAt(b)=='Q')
                return st.toString();
            a--; b++;
        }
        for (int i = 0; i < n; i++) {
            if(i==c) st.append('Q');
            else st.append('.');
        }
        return st.toString();
    }
}