Ekran blokady Androida

Wprowadzenie

Siedzisz w sali konferencyjnej na końcu długiego stołu. Rozejrzyj się i zobaczysz Tima Cooka, zarząd Apple, ducha Steve'a Jobsa i Jacka Donaghy. Apple zwołał to spotkanie, ponieważ zdali sobie sprawę, jak fajniejszy jest ekran blokady Androida, i chcą je zwiększyć. Wszyscy w pokoju patrzą na ciebie, gdy Duch Steve krzyczy: „Pomóż mi, CodeGolf Man! Jesteś moją jedyną nadzieją!”

Problem

Ekran blokady Androida to siatka kropek 3 x 3, które można połączyć, przesuwając palcem od jednej kropki do drugiej, tworząc ścieżkę. Hasło jest uważane za każdą możliwą ścieżkę, która zawiera dowolną liczbę kropek i wyklucza dowolną liczbę kropek. (W prawdziwym telefonie ścieżka musi mieć co najmniej 4 kropki. W przypadku tego wyzwania zignoruj ​​to ograniczenie). Apple planuje zastąpić siatkę 3 x 3 siatką M x N, która wynosi (M * N) / 9 razy lepiej!

Zasady:

Na przykład na siatce 3x3 z kropkami ponumerowanymi od 1 do 9:

1 2 3
4 5 6
7 8 9

Niektóre prawidłowe ścieżki to:

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

A niektóre nieprawidłowe ścieżki to:

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

Twój wkład będzie składał się z trzech liczb:

(M,N,d)

Gdzie siatka to M x N, a d to długość ścieżki

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

Twój program lub funkcja otrzyma dane wejściowe jako ciąg rozdzielany przecinkami i musi zwrócić liczbę możliwych haseł o tej długości. Na przykład:

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

Obowiązują standardowe zasady gry w golfa, wygrywa najkrótszy kod!

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

Python - 170 bajtów

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

Zdaję sobie sprawę, że nawiasy w środku sum([...])nie są absolutnie konieczne, ale istnieje duża kara wydajnościowa za ich nieuwzględnienie.

Wyjście dla wszystkich 3x3:

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

Produkuje:

1624
7152
26016
72912
140704
140704

Do celów testowania / potwierdzania pierwszych 6 wartości dla płyty 4x5:

20
262
3280
39644
459764
5101232

4x5 to ciekawy przypadek do weryfikacji, ponieważ ma skoki 2x2, 3x3 i 2x4.

Krótkie wyjaśnienie

Ogólnie rzecz biorąc, jest to wyczerpujące wyszukiwanie z łącznym przycinaniem. Na przykład, ponieważ p(3, 3, 4)jest to 1624, p(3, 3, 5)sprawdzi tylko 8120 możliwości, zamiast naiwnie sprawdzać wszystkie 15120. Większość logiki jest zawarta w warunku:

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

W prostym języku angielskim można to rozumieć jako:

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