def isCrossing(tup1, lst):
    for val, idx in enumerate(lst):
        if ((tup1[0] + tup1[1]) == (idx + val)): # If queens are on the diagonal
            return True
        if ((tup1[0] - tup1[1]) == (idx - val)): # If queens are on the diagonal
            return True
        if (tup1[0] == idx): # If queens are on the same row
            return True
    return False

def queens(n):
    lst = []
    return queens_rec(n, lst)

def queens_rec(n, lst):
    if len(lst) == n:
        return 1
    cnt = 0
    for row in range(n):
        if not isCrossing((row, len(lst)), lst):
            # print(lst + [row])
            cnt += queens_rec(n, lst + [row])
    return cnt