from collections import defaultdict

def count_knight_paths(maxlevel):
    jump = {0: [6, 4], 1: [6, 8], 2: [9, 7],
            3: [4, 8], 4: [9, 3, 0], 6: [7, 1, 0],
            7: [6, 2], 8: [3, 1], 9: [4, 2]}
    c = { 1 : 1 }
    for level in range(maxlevel):
        cprim = defaultdict(int)
        for key in c:
            for jumped in jump[key]:
                cprim[jumped] += c[key]
        c = cprim
    return sum(c.values())

if __name__ == "__main__":
    for i in range(10):
        print(i + 1, count_knight_paths(i))

(1, 1)
(2, 2)
(3, 5)
(4, 10)
(5, 26)
(6, 52)
(7, 136)
(8, 272)
(9, 712)
(10, 1424)