from copy import deepcopy

#
# The 576 latin squares on four letters
#
stack = []
result = []

# I use sets instead of list to be able to use .discard
latin = [set([x for x in range(4)]) for y in range(16)]
stack.append(deepcopy(latin))

def applyConstraints(latin):
    for i in range(16):
        if len(latin[i]) == 1:
            x = list(latin[i])[0]
            for j in range(4):
                latin[4*(i//4)+j].discard(x)
                latin[(i%4)+j*4].discard(x)
            latin[i] = set([x])


while len(stack) != 0:

    # apply constraints
    latin = deepcopy(stack.pop())
    latincopy = deepcopy(latin)
    applyConstraints(latincopy)
    while latincopy != latin:
        latin = deepcopy(latincopy)
        applyConstraints(latincopy)

    # store results if done, otherwise branch

    sizes = [len(x) for x in latin]

    if min(sizes) == 1 and max(sizes) == 1:
        result.append(deepcopy(latin))


    elif min(sizes) != 0:
        # identify a set to branch
        index = -1
        for i in range(16):
            if sizes[i] != 1:
                index = i
                break

        # branch that set
        for x in latin[index]:
            latincopy[index] = set([x])
            stack.append(deepcopy(latincopy))

print(len(result))



#
# The 576 latin squares on 4 letters - using bitwise sets
#
from functools import reduce

stack = []
result = []

latin = [15 for y in range(16)]
singleton = lambda x : not (x & (x - 1))
stack.append(latin.copy())



def applyConstraints(latin):
    for i in range(16):
        if singleton(latin[i]):
            x = latin[i]
            for j in range(4):
                latin[4*(i//4)+j] = latin[4*(i//4)+j] & (~x)
                latin[(i%4)+j*4] = latin[(i%4)+j*4] & (~x)
            latin[i] = x


while len(stack) != 0:
    # pop the next unfinished latin square
    latin = stack.pop()

    # apply constraints
    latincopy = latin.copy()
    applyConstraints(latincopy)
    while latincopy != latin:
        latin = latincopy.copy()
        applyConstraints(latincopy)

    # identify singleton sets
    singletons = list(map(singleton, latin))

    # append finished square
    appendable = reduce(lambda x, y : x and y, singletons)
    if appendable: result.append(latin.copy())
    else:
        # check if contains empty sets
        invalid = map(lambda x : not x, latin)
        invalid = reduce(lambda x , y : x or y, invalid)

        if not invalid:
            # identify set with at least two elements
            index = singletons.index(False)

            # branch that set
            for x in range(4):
                if 2**x & latin[index]:
                    latincopy[index] = 2**x
                    stack.append(latincopy.copy())

print(len(result))