Android Lock Screen

Question

Intro

You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this meeting because they have realized how much cooler the Android lock screen is, and they want to 1-UP them. Everyone in the room stares at you as Ghost Steve cries, "Help me, CodeGolf Man! You're my only hope!"

The Problem

The Android lock screen is a 3 x 3 grid of dots that can be connected by swiping a finger from one dot to the next, creating a path. A password is considered any possible path that includes any number of dots, and excludes any number of dots. (On an actual phone, the path must be at least 4 dots long. For this challenge, ignore that restriction.) Apple plans to replace the 3 x 3 grid with an M x N grid, which is (M*N)/9 times better!

Rules:

A zero dot path is not a password, but a 1 dot path is

A path can cross itself

A path cannot cross directly over a dot without including that dot

A dot can only be used once

Paths that are identical by rotation are not the same password

Paths that are identical but ordered in reverse are not the same password

For example, on a 3x3 grid with dots numbered from 1 to 9:

1 2 3
4 5 6
7 8 9

Some valid paths are:

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

And some invalid paths are:

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

Your input will be three numbers:

(M,N,d)

Where the grid is M x N, and d is the length of the path

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

Your program or function will be given the input as a comma separated string, and it must return the number of possible passwords of that length. For example:

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

Standard code golf rules apply, shortest code wins!

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

Answer 1

Python - 170 bytes

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))])

I realize that the brackets inside sum([...]) are not strictly necessary, but there's a large performance penalty for not including them.

Output for all 3x3s:

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

Produces:

1624
7152
26016
72912
140704
140704

For testing/confirmation purposes, the first 6 values for a 4x5 board:

20
262
3280
39644
459764
5101232

4x5 is an interesting case to verify, because it has 2x2, 3x3, and 2x4 peg jumps.

---

Brief Explanation

In general, this is an exhaustive search, with cumulative pruning. For example, because p(3, 3, 4) is 1624, p(3, 3, 5) will only check 8120 posibilities, rather than naïvely checking all 15120. Most of the logic is contained in the condition:

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

In plain english, this can be understood as:

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