How many combinations (Math Stackexchange)

original = {1:[2,4,5,6,8],
            2:[1,3,4,5,6,7,9],
            3:[2,4,5,6,8],
            4:[1,2,3,5,7,8,9],
            5:[1,2,3,4,6,7,8,9],
            6:[1,2,3,5,7,8,9],
            7:[2,4,5,6,8],
            8:[1,3,4,5,6,7,9],
            9:[2,4,5,6,8]
            }

def legals(current):
    curr = current[-1]
    if (not curr%2) and 5 in current:
        extras = [10-curr]
    else:
        tocheck = [2*x-curr for x in [2,4,5,6,8] if x in current]
        extras = [x for x in tocheck if x in range(1,10)]

    return list(set([x for x in (original[current[-1]]+extras) if x not in current]))

possibles = [[x] for x in range(1,10)]
for j in range(3-1):
    newposs = [i+[x] for i in possibles for x in legals(i)]
    possibles = newposs
for j in range(6):
    newposs = [i+[x] for i in possibles for x in legals(i)]
    possibles = newposs
    print(len(possibles))