N-Queens

def solve_n_queens(n):
    res=[]; cols=set(); d1=set(); d2=set()
    board=[['.']*n for _ in range(n)]
    def bt(r):
        if r==n: res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or r-c in d1 or r+c in d2: continue
            cols.add(c); d1.add(r-c); d2.add(r+c); board[r][c]='Q'
            bt(r+1)
            cols.remove(c); d1.remove(r-c); d2.remove(r+c); board[r][c]='.'
    bt(0)
    return res

public List<List<String>> solveNQueens(int n){
    List<List<String>> res=new ArrayList<>();
    char[][] board=new char[n][n];
    for(char[] row:board) Arrays.fill(row,'.');
    Set<Integer> cols=new HashSet<>(),d1=new HashSet<>(),d2=new HashSet<>();
    backtrack(res,board,cols,d1,d2,0,n);
    return res;
}
void backtrack(List<List<String>> res,char[][] board,Set<Integer> cols,Set<Integer> d1,Set<Integer> d2,int r,int n){
    if(r==n){List<String> sol=new ArrayList<>();for(char[] row:board) sol.add(new String(row));res.add(sol);return;}
    for(int c=0;c<n;c++){
        if(cols.contains(c)||d1.contains(r-c)||d2.contains(r+c)) continue;
        cols.add(c);d1.add(r-c);d2.add(r+c);board[r][c]='Q';
        backtrack(res,board,cols,d1,d2,r+1,n);
        cols.remove(c);d1.remove(r-c);d2.remove(r+c);board[r][c]='.';
    }
}