Android-Sperrbildschirm

Intro

Sie sitzen in einem Sitzungssaal am Ende eines langen Tisches. Sie sehen sich um und sehen Tim Cook, das Apple Board of Directors, den Geist von Steve Jobs und Jack Donaghy. Apple hat dieses Treffen anberaumt, weil es erkannt hat, wie viel cooler der Android-Sperrbildschirm ist, und sie möchten sie 1-UP. Jeder im Raum starrt dich an, als Ghost Steve schreit: "Hilf mir, CodeGolf Man! Du bist meine einzige Hoffnung!"

Das Problem

Der Android-Sperrbildschirm ist ein 3 x 3-Raster von Punkten, die durch Wischen eines Fingers von einem Punkt zum nächsten verbunden werden können, um einen Pfad zu erstellen. Ein Kennwort wird als ein möglicher Pfad angesehen, der eine beliebige Anzahl von Punkten enthält und eine beliebige Anzahl von Punkten ausschließt. (Auf einem tatsächlichen Telefon muss der Pfad mindestens 4 Punkte lang sein. Ignorieren Sie diese Einschränkung für diese Herausforderung.) Apple plant, das 3 x 3-Raster durch ein M x N-Raster (M * N) / 9 zu ersetzen mal besser!

Regeln:

Beispiel: In einem 3x3-Raster mit Punkten von 1 bis 9:

1 2 3
4 5 6
7 8 9

Einige gültige Pfade sind:

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

Und einige ungültige Pfade sind:

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

Ihre Eingabe wird drei Zahlen sein:

(M,N,d)

Wobei das Gitter M x N ist und d die Länge des Pfades ist

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

Ihr Programm oder Ihre Funktion erhält die Eingabe als durch Kommas getrennte Zeichenfolge und muss die Anzahl der möglichen Kennwörter dieser Länge zurückgeben. Beispielsweise:

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

Es gelten die Standard-Code-Golfregeln, der kürzeste Code gewinnt!

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

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

Mir ist klar, dass die Klammern im Inneren sum([...])nicht unbedingt erforderlich sind, aber es gibt einen großen Leistungsnachteil, wenn sie nicht berücksichtigt werden.

Ausgabe für alle 3x3s:

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

Produziert:

1624
7152
26016
72912
140704
140704

Zu Test- / Bestätigungszwecken die ersten 6 Werte für eine 4x5-Karte:

20
262
3280
39644
459764
5101232

4 x 5 ist ein interessanter Fall, der überprüft werden muss, da es 2 x 2, 3 x 3 und 2 x 4 Peg Jumps gibt.

Kurze Erklärung

Im Allgemeinen handelt es sich um eine umfassende Suche mit kumulativem Beschneiden. Da p(3, 3, 4)es sich beispielsweise um 1624 handelt, p(3, 3, 5)werden nur 8120-Möglichkeiten geprüft, anstatt alle 15120-Möglichkeiten naiv zu prüfen. Der größte Teil der Logik ist in der folgenden Bedingung enthalten:

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

Im Klartext kann dies verstanden werden als:

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