1 2 3
4 5 6
7 8 9

1
3
7,2,3
1,5,9,2
1,8,6,5,4
4,2,3,5,6,7,8,9
5,9,6,4

1,3
1,9,5
7,5,4,7
4,6

(M,N,d)

1 <= M <= 16
1 <= N <= 16
1 <= d <= M * N

Input:  2,2,1
Output: 4
Input:  2,2,2
Output: 12
Input:  7,4,1
Output: 28

//If I've made a mistake or the rules are unclear, please correct me!

from fractions import*
p=lambda m,n,d,l=0,s=set():d<1or sum([p(m,n,d-1,i,s|{i})for i in range(m*n)if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))])

for i in range(4, 10):
  print p(3, 3, i)

1624
7152
26016
72912
140704
140704

20
262
3280
39644
459764
5101232

if not(s and(s&{i}or set(range(l,i,abs(i-l)/gcd(i%n-l%n,i/n-l/n)))-s))

If no pegs have been used yet
     OR
   the target peg has not yet been used
     AND
   each of the pegs directly between the target peg and the
   current peg (a.k.a. "jumped over") have already been used