Anzahl der Pfade auf einem Gitter von S bis M

Ein möglicher (aber komplizierter) Ansatz

Sie könnten Bewegungen durch komplexe Zahlen darstellen:

$1$bewegt sich nach rechts,$-1$bewegt sich nach links,$i$ist aufsteigen,$-i$bewegt sich nach unten.

Dann ist ein Pfad eine Sequenz wie z$1,-i, -1, ...$

Die Bedingungen für einen gültigen Pfad haben dann einfache arithmetische Äquivalenzen.

Um von B nach J zu wechseln Die Gesamtsumme der Zahlen muss sein$2-5i$.

Im Raster bleiben Für jede natürliche Zahl$n$, die Summe$S_n$des ersten$n$Zahlen müssen genügen$4\ge \Re (S_n)\ge -1, 0\ge \Im (S_n)\ge -5.$

Kein Feld zweimal besuchen Keine Summe aufeinanderfolgender Zahlen darf Summe haben$0$.

Dies scheint geeignet zu sein, programmiert zu werden, wenn dies von Interesse ist.

Beachten Sie in der Originalquelle, dass jeder Schritt im Pfad rechts oder unten war. Mit diesen Regeln erfordert jeder Weg von B nach J 2 Rechte und 5 Abstiege in beliebiger Reihenfolge. Es gibt$\binom{5+2}{2} = 21$solche Wege. Aber um beispielsweise von B nach G zu gelangen, bräuchten Sie Bewegungen nach links und nach unten. Wenn Sie sowohl Links als auch Rechts zulassen, ist die Anzahl der Pfade unendlich, da Sie sich nach rechts, links, rechts, links bewegen können ... so lange Sie möchten.

Bearbeiten: Mit der Einschränkung, eine Position nicht mehr als einmal zu besuchen, ist die Anzahl der Pfade mit jeder zulässigen Richtung endlich, aber groß (im Vergleich zur Brettgröße). Zum Beispiel die Anzahl der Pfade zwischen gegenüberliegenden Ecken von a$2 \times n$Gitter ist$2^{n-1}$, schon exponentiell.