class Solution {
    
    int count = 0;
    int arr[];
    
    boolean place(int k,int i)
    {
        for(int j=0;j<=k-1;j++)
        {
            if(arr[j] == i || ( Math.abs(k-j) == Math.abs(i-arr[j]) ) )
                return false;
        }
        return true;
    }
    
    public void nQueens(int k,int n)
    {
        for(int i=0;i<n;i++)
        {
            if(place(k,i))
            {
                arr[k] = i;
                if(k == n-1)
                    count++;
                else
                    nQueens(k+1,n);
            }
        }
    }
    
    public int totalNQueens(int n) {
        
        arr = new int[n];
        nQueens(0,n);
        return count;
    }
}