luke-17.py

MOVES = [[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]]
KEYPAD = [[1, 2, 3],[4, 5, 6],[7, 8, 9],[None, 0, None]]

VALID = {(x, y) : key 
         for x,row in enumerate(KEYPAD) 
         for y,key in enumerate(row) 
         if not key == None}

GRAPH = {key : [VALID[(x+x2, y+y2)] for x2, y2 in MOVES if (x+x2, y+y2) in VALID]
         for x, row in enumerate(KEYPAD) 
         for y, key in enumerate(row) 
         if not key == None}

def walk(graph, node, d=1, m=10):
    return 1 if d == m else sum([walk(graph, n, d+1, m) for n in graph[node]])

print walk(GRAPH, 1)