knights.py

adj = {1 : {6, 8}, 2 : {7, 9}, 3 : {4, 8}, 4 : {3, 9, 0}, 6 : {1, 7, 0},
       7 : {2, 6}, 8 : {1, 3}, 9 : {4, 2}, 0 : {4, 6}}
memo = {}
def allpaths2(at, n, tot):
    if (at, n) in memo:
        tot[0] += memo[at, n]
        return
    prev = tot[0]
    if n == 0:
        tot[0] += 1
        return
    neighs = adj[at]
    for neigh in neighs:
        allpaths2(neigh, n - 1, tot)
    next = tot[0]
    memo[at, n] = next - prev

def count_paths(at, n):
    tot = [0]
    allpaths2(at, n, tot)
    return tot[0]

assert(count_paths(1, 1) == 2)
assert(count_paths(1, 2) == 5)
assert(count_paths(1, 3) == 10)
assert(count_paths(1, 8) == 712)
assert(count_paths(1, 9) == 1424)
assert(count_paths(1, 15) == 204416)
print(count_paths(1, 30))