class Solution:
    def totalNQueens(self, n: int) -> int:
        # using global array to store the position of queens
        self.queen = []
        return self.helper(n, 0, 0)
        
    def helper(self,n, row, count):
        for col in range(n):
            
            if self.is_not_under_attack(row, col):
                # add queen's position to global array
                self.queen.append([row, col])
                if row + 1 == n:
                    #traversed to the bottom; found a solution; add to count variable
                    count +=1
                    
                else:
                    # move on to the next row
                    count = self.helper(n, row+1, count)
                self.queen.remove([row,col])
        return count
                
                
    
    def is_not_under_attack(self, row, col):
        #all the positions in the diagonal will be equal to row-col or row+col
        right_diag=row-col
        left_diag=row+col
        # looping over all the previous queens to find the available position
        for each in self.queen:
            # if lies in row or col of previous queen, return
            if each[0]==row or each[1]==col:
                return False
            # if lies in left or right diagonal of previous queen, return
            if each[0]-each[1]==right_diag or each[0]+each[1]==left_diag:
                return False
        return True