We must count all valid touch-screen passwords on a \(4\times 4\) lattice of points. A password is an ordered sequence of distinct nodes with length at least \(2\). If the current node is \(a\) and the next node is \(b\), the move is allowed only when every lattice point strictly inside the segment from \(a\) to \(b\) has already appeared earlier in the password.
This makes the problem much subtler than counting paths in a fixed graph. Whether a long jump is legal depends on which points have already been visited, so the available moves change from state to state.
Let \(V\) be the set of grid points, with \(|V|=n=wh\). In the actual problem \(w=h=4\), so \(n=16\). We want to count every valid sequence exactly once.
Suppose the current password prefix is
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$$
Define the visited set
$$U=\{v_1,v_2,\dots,v_k\}.$$
The key observation is that the future does not depend on the full order of the prefix. It depends only on:
$$U,\qquad v_k.$$
That is enough because a future move only asks two questions: is the destination still unused, and are all required interior points already in \(U\)? Since nodes are never revisited, the visited set grows monotonically.
Take two distinct nodes
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
Set
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
A standard lattice-point fact says that the open segment from \(a\) to \(b\) contains exactly \(g-1\) lattice points. They are
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$$
So if \(g=1\), the direction is primitive and there are no interior lattice points at all. If \(g>1\), those \(g-1\) intermediate points are precisely the nodes that must already have been used before the jump can be taken.
For each ordered pair \((a,b)\) of distinct nodes, define \(R(a,b)\) as the set of interior lattice points on the open segment from \(a\) to \(b\).
Then a move from the current endpoint \(v\) to an unused node \(u\) is legal exactly when
$$u\notin U,\qquad R(v,u)\subseteq U.$$
This formulation separates geometry from search. All geometric information is contained in the precomputed sets \(R(a,b)\), and the dynamic part of the problem reduces to checking whether those required points are already present in the visited set.
Let \(F(U,v)\) be the number of valid ways to extend the current state whose visited set is \(U\) and whose last node is \(v\).
If \(u\) is a legal next node, then appending \(u\) creates:
$$1$$
new password that stops immediately after \(u\), and also
$$F(U\cup\{u\},u)$$
longer passwords that continue from the new state. Therefore
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
If no legal destination exists, the sum is empty and \(F(U,v)=0\). Because every password has a unique last state before its final move, this recurrence counts every valid continuation exactly once.
Consider the jump from \((0,3)\) to \((3,0)\). Here
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
So the interior lattice points are
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$$
This means that a password prefix ending at \((0,3)\) may jump to \((3,0)\) only if both \((1,2)\) and \((2,1)\) have already been used. If either point is still unused, the jump is forbidden.
By contrast, the jump from \((0,0)\) to \((3,2)\) has
$$g=\gcd(3,2)=1,$$
so
$$R\bigl((0,0),(3,2)\bigr)=\varnothing.$$
That jump is immediately legal as soon as the destination itself is unused. This is exactly the distinction the recurrence exploits: some moves are always available, while others become available only after the right intermediate points have entered the visited set.
Each password has a unique starting node \(s\in V\). Once that first node is fixed, the remaining count is \(F(\{s\},s)\). Hence the total number of passwords is
$$T=\sum_{s\in V} F(\{s\},s).$$
Single-node prefixes are not counted as completed passwords here; every counted object arises from appending at least one further node, which matches the behavior of the implementations.
The C++, Python, and Java implementations all follow the same plan. First they enumerate the \(16\) grid points by their Cartesian coordinates. Then, for every ordered pair of distinct nodes, they compute the gcd of the horizontal and vertical displacements, walk along the segment in primitive steps, and store the resulting set \(R(a,b)\) of required interior points.
Because the board has only \(16\) points, a visited set fits naturally into a bit mask. The same representation is used for each precomputed requirement set. This turns the legality test \(R(v,u)\subseteq U\) into a constant-time bit operation. The compiled implementations store memoized results in a flat table indexed by the visited mask and current endpoint, while the Python implementation stores the same state in a memo dictionary.
The search starts from every possible first node. At each state, the implementation scans all unused destinations, keeps only those whose required interior points are already present in the visited mask, and adds one for the password that ends immediately after the move plus the recursively computed number of longer continuations. Since each state is solved once, the algorithm avoids enumerating the enormous family of passwords explicitly.
Let \(n=wh\) and let \(d=\max(w,h)\). Precomputing all segment requirements costs \(O(n^2 d)\), because for each ordered pair we may walk through up to \(g-1\le d-1\) intermediate lattice points. On the actual \(4\times 4\) board this cost is tiny.
The memoized search has at most \(n2^{n-1}\) reachable state descriptions \((U,v)\): for each endpoint \(v\), the visited set can be any subset containing \(v\). Each state tries up to \(n\) candidate next nodes, so the overall running time is \(O(n^2 2^n)\). The memory usage is \(O(n2^n+n^2)\), dominated by the memo table. For \(n=16\), this means at most \(16\cdot 2^{16}=1{,}048{,}576\) memo entries, which is easily manageable.
Gesucht ist die Anzahl aller gültigen Touchscreen-Passwörter auf einem \(4\times 4\)-Gitter. Ein Passwort ist eine geordnete Folge verschiedener Knoten mit Länge mindestens \(2\). Ein Zug vom aktuellen Knoten \(a\) zu \(b\) ist nur dann erlaubt, wenn alle Gitterpunkte im Inneren der Verbindungsstrecke bereits früher in der Folge benutzt wurden.
Damit ist das Problem kein gewöhnliches Pfadzählen in einem festen Graphen. Ob ein weiter Sprung erlaubt ist, hängt vom bereits besuchten Zustand ab; die Menge der zulässigen Züge ändert sich also dynamisch.
Sei \(V\) die Menge aller Gitterpunkte, mit \(|V|=n=wh\). In der eigentlichen Aufgabe gilt \(w=h=4\), also \(n=16\). Wir wollen jede zulässige Folge genau einmal zählen.
Sei das aktuelle Präfix
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$$
Definiere die besuchte Menge
$$U=\{v_1,v_2,\dots,v_k\}.$$
Die entscheidende Beobachtung ist: Für die Zukunft genügt es, \(U\) und den letzten Knoten \(v_k\) zu kennen. Die genaue Reihenfolge der früheren Knoten spielt keine Rolle mehr, denn ein späterer Zug fragt nur:
ist das Ziel noch unbenutzt und liegen alle erforderlichen Zwischenpunkte bereits in \(U\)?
Da kein Knoten wiederholt werden darf, wächst \(U\) während des Aufbaus monoton.
Betrachte zwei verschiedene Knoten
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
Setze
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
Ein Standardfakt über Gitterpunkte besagt: Das offene Segment von \(a\) nach \(b\) enthält genau \(g-1\) Gitterpunkte. Diese sind
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$$
Bei \(g=1\) gibt es also keine inneren Gitterpunkte. Bei \(g>1\) sind genau diese Zwischenpunkte die Punkte, die schon besucht worden sein müssen, bevor der Sprung erlaubt ist.
Für jedes geordnete Paar \((a,b)\) verschiedener Knoten sei \(R(a,b)\) die Menge der inneren Gitterpunkte auf dem offenen Segment von \(a\) nach \(b\).
Dann ist ein Zug vom aktuellen Endpunkt \(v\) zu einem unbenutzten Knoten \(u\) genau dann erlaubt, wenn
$$u\notin U,\qquad R(v,u)\subseteq U.$$
Damit wird die Geometrie vollständig von der Suche getrennt. Alle geometrischen Informationen stecken in den vorab berechneten Mengen \(R(a,b)\), und der dynamische Teil besteht nur noch darin zu prüfen, ob diese benötigten Punkte bereits in der besuchten Menge liegen.
Sei \(F(U,v)\) die Anzahl gültiger Fortsetzungen eines Zustands mit besuchter Menge \(U\) und aktuellem Endpunkt \(v\).
Ist \(u\) ein legaler nächster Knoten, dann erzeugt das Anhängen von \(u\)
$$1$$
neues Passwort, das sofort bei \(u\) endet, sowie
$$F(U\cup\{u\},u)$$
weitere längere Passwörter aus dem neuen Zustand. Daher gilt
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
Gibt es kein legales Ziel, so ist die Summe leer und \(F(U,v)=0\). Da jedes Passwort genau einen letzten Zustand vor seinem letzten Zug besitzt, wird jede gültige Fortsetzung genau einmal erfasst.
Betrachte den Sprung von \((0,3)\) nach \((3,0)\). Dann ist
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
Also sind die inneren Gitterpunkte
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$$
Ein Präfix, das bei \((0,3)\) endet, darf also nur dann direkt nach \((3,0)\) springen, wenn sowohl \((1,2)\) als auch \((2,1)\) bereits besucht wurden. Fehlt einer dieser beiden Punkte, ist der Sprung verboten.
Zum Vergleich: Der Sprung von \((0,0)\) nach \((3,2)\) hat
$$g=\gcd(3,2)=1,$$
also
$$R\bigl((0,0),(3,2)\bigr)=\varnothing.$$
Dieser Zug ist sofort erlaubt, sobald das Ziel noch frei ist. Genau diese Unterscheidung zwischen primitiven und nichtprimitiven Richtungen nutzt die Rekursion aus.
Jedes Passwort besitzt einen eindeutigen Startknoten \(s\in V\). Ist dieser fest, dann ist die verbleibende Anzahl gleich \(F(\{s\},s)\). Insgesamt also
$$T=\sum_{s\in V} F(\{s\},s).$$
Einzelne Startknoten zählen hier noch nicht als vollständige Passwörter; gezählt wird immer erst, wenn mindestens ein weiterer Knoten angehängt wurde. Genau so arbeiten die Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst werden die \(16\) Gitterpunkte mit ihren kartesischen Koordinaten aufgelistet. Danach wird für jedes geordnete Paar verschiedener Knoten der ggT der horizontalen und vertikalen Differenz berechnet, das Segment in primitiven Schritten abgelaufen und die entstehende Menge \(R(a,b)\) der benötigten Zwischenpunkte gespeichert.
Da das Brett nur \(16\) Punkte besitzt, passt eine besuchte Menge bequem in eine Bitmaske. Dieselbe Darstellung wird auch für jede vorab berechnete Anforderungsmenge verwendet. Dadurch wird der Test \(R(v,u)\subseteq U\) zu einer konstanten Bitoperation. Die kompilierten Implementierungen verwenden eine flache Memo-Tabelle, die durch besuchte Maske und aktuellen Endpunkt indiziert wird; die Python-Implementierung speichert denselben Zustand in einem Memo-Dictionary.
Die Suche startet bei jedem möglichen Anfangsknoten. In jedem Zustand werden alle noch freien Ziele geprüft; nur diejenigen bleiben übrig, deren notwendige Zwischenpunkte bereits in der besuchten Maske enthalten sind. Für jeden solchen Zug addiert die Implementierung eins für das Passwort, das sofort endet, plus die rekursiv bestimmte Anzahl längerer Fortsetzungen. Weil jeder Zustand nur einmal ausgewertet wird, muss die riesige Menge aller Passwörter nicht explizit erzeugt werden.
Seien \(n=wh\) und \(d=\max(w,h)\). Die Vorberechnung aller Segmentanforderungen kostet \(O(n^2 d)\), denn für jedes geordnete Paar können bis zu \(g-1\le d-1\) Zwischenpunkte durchlaufen werden. Auf dem tatsächlichen \(4\times 4\)-Brett ist dieser Aufwand sehr klein.
Die memoisiere Suche hat höchstens \(n2^{n-1}\) erreichbare Zustandsbeschreibungen \((U,v)\): Für jeden Endpunkt \(v\) kann die besuchte Menge jede Teilmenge sein, die \(v\) enthält. Pro Zustand werden bis zu \(n\) Kandidaten getestet, also ergibt sich insgesamt \(O(n^2 2^n)\) Laufzeit. Der Speicherbedarf ist \(O(n2^n+n^2)\) und wird von der Memo-Tabelle dominiert. Für \(n=16\) sind das höchstens \(16\cdot 2^{16}=1{,}048{,}576\) Memo-Einträge.
Burada sayılan nesneler, \(4\times 4\) nokta ızgarası üzerindeki geçerli dokunmatik ekran şifreleridir. Bir şifre, uzunluğu en az \(2\) olan ve aynı düğümü tekrar etmeyen sıralı bir düğüm dizisidir. Geçerli bir hamlede, mevcut düğüm \(a\)'dan yeni düğüm \(b\)'ye geçebilmek için \(a\) ile \(b\) arasındaki doğru parçasının iç kısmında kalan bütün ızgara noktalarının daha önce ziyaret edilmiş olması gerekir.
Bu yüzden problem, sabit bir graf üzerinde yol saymaktan daha zordur. Uzak bir sıçramanın izinli olup olmaması, hangi noktaların daha önce kullanıldığına bağlıdır; yani geçerli hamleler durumdan duruma değişir.
\(V\) tüm ızgara noktalarının kümesi olsun ve \(|V|=n=wh\) olsun. Bu problemde \(w=h=4\) olduğundan \(n=16\)'dır. Amaç, her geçerli şifreyi tam bir kez saymaktır.
Mevcut şifre öneki
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j)$$
olsun. Ziyaret edilen küme
$$U=\{v_1,v_2,\dots,v_k\}$$
şeklinde tanımlansın. Asıl kritik gözlem şudur: Gelecekte hangi hamlelerin mümkün olduğu, tüm geçmiş sıraya değil sadece
$$U,\qquad v_k$$
bilgisine bağlıdır. Çünkü yeni bir hamlede sorulan tek şey, hedef düğümün henüz kullanılmamış olması ve gerekli ara noktaların zaten \(U\) içinde bulunmasıdır. Düğümler tekrar edilmediği için \(U\) her adımda yalnızca büyür.
İki farklı düğüm alalım:
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
Şunları tanımlayalım:
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
Izgara geometrisinin standart bir sonucu şunu söyler: \(a\) ile \(b\) arasındaki açık doğru parçası üzerinde tam olarak \(g-1\) adet ızgara noktası vardır. Bunlar
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1$$
şeklindedir. Eğer \(g=1\) ise iç noktalar yoktur. Eğer \(g>1\) ise, sıçramadan önce zaten kullanılmış olması gereken noktalar tam olarak bunlardır.
Her farklı \((a,b)\) sıralı düğüm çifti için, açık doğru parçası üzerindeki iç noktaların kümesini \(R(a,b)\) ile gösterelim.
O zaman mevcut son düğüm \(v\)'den kullanılmamış bir \(u\) düğümüne geçiş tam ve ancak tam şu durumda yasaldır:
$$u\notin U,\qquad R(v,u)\subseteq U.$$
Böylece geometri kısmı aramadan ayrılmış olur. Tüm geometrik bilgi önceden hesaplanan \(R(a,b)\) kümelerinde tutulur; dinamik kısım ise yalnızca bu zorunlu ara noktaların ziyaret kümesinde bulunup bulunmadığını kontrol etmektir.
\(F(U,v)\), ziyaret kümesi \(U\) ve son düğümü \(v\) olan bir durumdan başlanınca yapılabilecek geçerli devamların sayısı olsun.
Eğer \(u\) geçerli bir sonraki düğümse, \(u\)'yu eklemek
$$1$$
adet yeni şifre üretir; bu şifre \(u\)'da hemen biter. Ayrıca
$$F(U\cup\{u\},u)$$
adet daha uzun devam üretir. Dolayısıyla
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
Hiç geçerli hedef yoksa toplam boştur ve \(F(U,v)=0\) olur. Her şifrenin son hamlesinden hemen önce tek bir benzersiz durum bulunduğu için bu formül her geçerli devamı tam bir kez sayar.
\((0,3)\) noktasından \((3,0)\) noktasına sıçramayı düşünelim. Burada
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
Bu yüzden ara noktalar
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}$$
olur. Yani sonu \((0,3)\)'te biten bir önek, ancak \((1,2)\) ve \((2,1)\) daha önce kullanıldıysa doğrudan \((3,0)\)'a gidebilir. Bu iki noktadan biri bile eksikse hamle yasaktır.
Buna karşılık \((0,0)\)'dan \((3,2)\)'ye geçişte
$$g=\gcd(3,2)=1$$
olduğundan
$$R\bigl((0,0),(3,2)\bigr)=\varnothing$$
çıkar. Yani hedef düğüm boş olduğu sürece bu sıçrama hemen geçerlidir. Özyinelemenin kullandığı temel ayrım tam olarak budur: bazı yönler her zaman açıktır, bazıları ise ancak doğru ara noktalar ziyaret edildikten sonra açılır.
Her şifrenin benzersiz bir başlangıç düğümü \(s\in V\) vardır. Bu düğüm sabitlenince kalan sayı \(F(\{s\},s)\) olur. O halde toplam cevap
$$T=\sum_{s\in V} F(\{s\},s)$$
şeklindedir. Tek düğümlü başlangıç durumları burada tamamlanmış şifre sayılmaz; ancak en az bir yeni düğüm eklendiğinde sayım yapılır. Uygulamalar da tam olarak bunu yapar.
C++, Python ve Java uygulamalarının hepsi aynı planı izler. Önce \(16\) ızgara noktası Kartezyen koordinatlarıyla numaralanır. Sonra her farklı sıralı düğüm çifti için yatay ve düşey farkların EBOB'u alınır, doğru parçası ilkel adımlarla yürünür ve elde edilen zorunlu ara nokta kümesi \(R(a,b)\) olarak saklanır.
Tahtada yalnızca \(16\) nokta olduğu için ziyaret kümesi bit maskesi olarak çok doğal biçimde tutulur. Aynı temsil her önceden hesaplanmış gereksinim kümesi için de kullanılır. Böylece \(R(v,u)\subseteq U\) testi sabit zamanlı bit işlemlerine dönüşür. Derlenmiş uygulamalar, ziyaret maskesi ve son düğümle indekslenen düz bir bellekleme tablosu kullanır; Python uygulaması ise aynı durumu bir sözlükte önbelleğe alır.
Arama her olası başlangıç düğümünden başlar. Her durumda tüm boş hedefler denenir; yalnızca zorunlu ara noktaları zaten ziyaret maskesinde bulunan hedefler kabul edilir. Böyle bir hamle için hemen biten şifre adına bir eklenir ve daha uzun devamlar için yeni duruma özyinelemeli olarak gidilir. Her durum yalnızca bir kez çözüldüğü için, gerçek şifre sayısı çok büyük olsa da bunların hepsini tek tek üretmeye gerek kalmaz.
\(n=wh\) ve \(d=\max(w,h)\) olsun. Tüm doğru parçası gereksinimlerini önceden hesaplamak \(O(n^2 d)\) zaman alır; çünkü her sıralı çift için en fazla \(g-1\le d-1\) ara nokta boyunca yürünür. Gerçek \(4\times 4\) tahta için bu maliyet çok küçüktür.
Belleklemeli aramada en fazla \(n2^{n-1}\) adet erişilebilir \((U,v)\) durumu vardır: her son düğüm \(v\) için, \(v\)'yi içeren herhangi bir ziyaret kümesi mümkün olabilir. Her durumda en çok \(n\) aday hedef denenir; dolayısıyla toplam süre \(O(n^2 2^n)\) olur. Bellek kullanımı \(O(n2^n+n^2)\) düzeyindedir ve baskın terim bellekleme tablosudur. \(n=16\) için bu, en fazla \(16\cdot 2^{16}=1{,}048{,}576\) bellek girişi demektir.
Hay que contar todos los patrones válidos de una pantalla táctil sobre una retícula \(4\times 4\). Un patrón es una secuencia ordenada de nodos distintos con longitud al menos \(2\). Si el nodo actual es \(a\) y el siguiente es \(b\), el salto solo es válido cuando todos los puntos de la retícula que quedan estrictamente dentro del segmento entre \(a\) y \(b\) ya aparecieron antes en la secuencia.
Por eso no basta con pensar en un grafo fijo. La legalidad de un salto largo depende de qué puntos han sido visitados, así que el conjunto de movimientos disponibles cambia con el estado.
Sea \(V\) el conjunto de puntos de la cuadrícula, con \(|V|=n=wh\). En el problema real \(w=h=4\), por lo que \(n=16\). Queremos contar cada patrón válido exactamente una vez.
Supongamos que el prefijo actual es
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$$
Definimos el conjunto de nodos ya usados como
$$U=\{v_1,v_2,\dots,v_k\}.$$
La observación fundamental es que el futuro no depende del orden completo del prefijo, sino solo de
$$U,\qquad v_k.$$
Eso basta porque una transición futura solo pregunta dos cosas: si el destino sigue libre y si todos los puntos intermedios exigidos ya pertenecen a \(U\). Como ningún nodo puede repetirse, el conjunto visitado crece de forma monótona.
Tomemos dos nodos distintos
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
Definimos
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
Un hecho estándar de geometría en retículas dice que el segmento abierto entre \(a\) y \(b\) contiene exactamente \(g-1\) puntos de la retícula. Esos puntos son
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$$
Así, si \(g=1\), la dirección es primitiva y no hay puntos interiores. Si \(g>1\), esos \(g-1\) puntos son precisamente los que deben haber sido visitados antes para que el salto sea legal.
Para cada par ordenado \((a,b)\) de nodos distintos, definimos \(R(a,b)\) como el conjunto de puntos interiores del segmento abierto de \(a\) a \(b\).
Entonces un salto desde el nodo final actual \(v\) hacia un nodo no usado \(u\) es legal exactamente cuando
$$u\notin U,\qquad R(v,u)\subseteq U.$$
Esto separa la geometría del conteo. Toda la información geométrica queda encapsulada en los conjuntos precomputados \(R(a,b)\), y la parte dinámica se reduce a comprobar si esos puntos obligatorios ya están contenidos en el conjunto visitado.
Sea \(F(U,v)\) el número de extensiones válidas de un estado cuyo conjunto visitado es \(U\) y cuyo último nodo es \(v\).
Si \(u\) es un siguiente nodo legal, entonces añadir \(u\) produce
$$1$$
nuevo patrón que termina inmediatamente en \(u\), y también
$$F(U\cup\{u\},u)$$
patrones más largos que continúan desde el nuevo estado. Por tanto,
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
Si no existe ningún destino legal, la suma es vacía y \(F(U,v)=0\). Como cada patrón tiene un único estado justo antes de su último movimiento, la recurrencia cuenta cada continuación válida exactamente una vez.
Consideremos el salto desde \((0,3)\) hasta \((3,0)\). Aquí
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
Por tanto, los puntos interiores son
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$$
Esto significa que un prefijo que termina en \((0,3)\) solo puede saltar a \((3,0)\) si tanto \((1,2)\) como \((2,1)\) ya han sido usados. Si falta uno de ellos, el movimiento está prohibido.
En cambio, el salto desde \((0,0)\) hasta \((3,2)\) satisface
$$g=\gcd(3,2)=1,$$
y por eso
$$R\bigl((0,0),(3,2)\bigr)=\varnothing.$$
Ese movimiento es legal de inmediato, siempre que el destino todavía no se haya usado. Esta es la diferencia central que explota la recurrencia: algunos saltos siempre están disponibles y otros solo se desbloquean cuando ciertos puntos intermedios ya forman parte del conjunto visitado.
Cada patrón tiene un nodo inicial único \(s\in V\). Fijado ese comienzo, el número restante es \(F(\{s\},s)\). En consecuencia, el total buscado es
$$T=\sum_{s\in V} F(\{s\},s).$$
Los patrones de un solo nodo no se cuentan como contraseñas completas; solo se cuenta cuando se añade al menos un nodo más. Ese es exactamente el comportamiento de las implementaciones.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero enumeran los \(16\) puntos de la cuadrícula por sus coordenadas cartesianas. Después, para cada par ordenado de nodos distintos, calculan el mcd de los desplazamientos horizontal y vertical, recorren el segmento en pasos primitivos y guardan el conjunto \(R(a,b)\) de puntos interiores exigidos.
Como el tablero solo tiene \(16\) posiciones, un conjunto visitado cabe naturalmente en una máscara de bits. La misma representación se usa para cada conjunto de requisitos precomputado. Así, la prueba \(R(v,u)\subseteq U\) se convierte en una operación de bits de tiempo constante. Las versiones compiladas guardan la memorización en una tabla plana indexada por la máscara visitada y el último nodo, mientras que la versión en Python memoriza el mismo estado en un diccionario.
La búsqueda se inicia desde cada posible nodo de arranque. En cada estado, la implementación prueba todos los destinos no usados, conserva solo aquellos cuyos puntos interiores requeridos ya están dentro de la máscara visitada y suma uno por la contraseña que termina inmediatamente después del movimiento más el número recursivo de continuaciones más largas. Como cada estado se resuelve una sola vez, el algoritmo evita enumerar explícitamente la enorme cantidad total de patrones.
Sea \(n=wh\) y \(d=\max(w,h)\). Precomputar todos los requisitos geométricos cuesta \(O(n^2 d)\), porque para cada par ordenado podemos recorrer hasta \(g-1\le d-1\) puntos interiores. En la cuadrícula real \(4\times 4\), ese costo es muy pequeño.
La búsqueda con memorización tiene a lo sumo \(n2^{n-1}\) estados alcanzables \((U,v)\): para cada último nodo \(v\), el conjunto visitado puede ser cualquier subconjunto que contenga a \(v\). Cada estado prueba hasta \(n\) destinos candidatos, así que el tiempo total es \(O(n^2 2^n)\). La memoria usada es \(O(n2^n+n^2)\), dominada por la tabla de memorización. Para \(n=16\), esto significa como máximo \(16\cdot 2^{16}=1{,}048{,}576\) entradas memorizadas.
本题要求统计 \(4\times 4\) 点阵上的所有合法触屏密码。一个密码是一个长度至少为 \(2\) 的有序节点序列，并且每个节点只能出现一次。若当前节点为 \(a\)，下一步想跳到 \(b\)，那么只有当线段 \(ab\) 内部的所有格点都已经在更早的位置被使用过时，这一步才合法。
因此，这不是一个“固定图上数路径”的简单问题。某个远距离跳跃是否允许，取决于此前已经访问过哪些点，所以可选边集会随着状态变化而变化。
记全部格点的集合为 \(V\)，其中 \(|V|=n=wh\)。在本题里 \(w=h=4\)，所以 \(n=16\)。目标是把每一个合法密码恰好计算一次。
设当前密码前缀为
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$$
把已经出现过的节点记为集合
$$U=\{v_1,v_2,\dots,v_k\}.$$
关键观察是：后续还能怎么走，并不依赖前缀的完整顺序，而只依赖
$$U,\qquad v_k.$$
原因很简单。下一步是否可走，只需要判断两件事：目标点是否尚未使用，以及该跳跃要求的中间格点是否都已经落在 \(U\) 中。由于节点不能重复，\(U\) 在搜索过程中只会不断增大。
取两个不同节点
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
定义
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
整数格点几何中的一个基本事实是：从 \(a\) 到 \(b\) 的开线段内部恰好包含 \(g-1\) 个格点，它们正是
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$$
因此，当 \(g=1\) 时，这个方向是原始方向，线段内部没有任何格点；当 \(g>1\) 时，这 \(g-1\) 个点就是本次跳跃之前必须已经访问过的全部中间点。
对每一对不同的有序节点 \((a,b)\)，记 \(R(a,b)\) 为从 \(a\) 到 \(b\) 的开线段内部所有格点组成的集合。
那么，从当前终点 \(v\) 跳到一个尚未访问的节点 \(u\) 是合法的，当且仅当
$$u\notin U,\qquad R(v,u)\subseteq U.$$
这一步把几何与搜索彻底分开了。所有几何信息都被压缩进预处理得到的集合 \(R(a,b)\) 中，动态部分只剩下判断这些必需中间点是否已经包含在访问集合里。
设 \(F(U,v)\) 表示：当前访问集合为 \(U\)、当前终点为 \(v\) 时，还能扩展出多少个合法密码。
如果 \(u\) 是一个合法的下一节点，那么把 \(u\) 接到后面会产生
$$1$$
个新密码，它在 \(u\) 处立刻结束；同时还会产生
$$F(U\cup\{u\},u)$$
个更长的延伸密码。因此有递推式
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
若当前没有任何合法去向，则这个求和为空，故 \(F(U,v)=0\)。由于每个密码在最后一步之前都有唯一的前一状态，上式会把每个合法延伸恰好统计一次。
考虑从 \((0,3)\) 跳到 \((3,0)\)。此时
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
所以中间格点集合为
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$$
这意味着，一个当前停在 \((0,3)\) 的前缀，只有在 \((1,2)\) 和 \((2,1)\) 都已被访问过的情况下，才能直接跳到 \((3,0)\)。如果这两个点里有任何一个尚未使用，那么该跳跃就是非法的。
对比之下，从 \((0,0)\) 跳到 \((3,2)\) 时有
$$g=\gcd(3,2)=1,$$
因此
$$R\bigl((0,0),(3,2)\bigr)=\varnothing.$$
只要目标点还没被用过，这一步就可以立刻执行。递推真正利用的，正是这种区别：有些方向天然可走，有些方向则必须等待正确的中间点先进入访问集合之后才会解锁。
每个密码都有唯一的起点 \(s\in V\)。一旦起点固定，剩余的合法延伸数量就是 \(F(\{s\},s)\)。因此总答案为
$$T=\sum_{s\in V} F(\{s\},s).$$
这里不会把单个起点本身算作完整密码；只有当再追加至少一个节点时才开始计数，这与三个实现的行为完全一致。
C++、Python 和 Java 三个实现遵循同一套思路。首先，它们按笛卡尔坐标枚举出 \(16\) 个格点。然后，对每一对不同的有序节点，计算水平位移与垂直位移的最大公约数，按原始步长沿线段前进，并把得到的必需中间点集合 \(R(a,b)\) 预先存起来。
由于棋盘只有 \(16\) 个点，访问集合非常适合用位掩码表示。每个预处理出来的需求集合也采用同样的位表示。这样，判断 \(R(v,u)\subseteq U\) 就能化为常数时间的按位运算。两个编译型实现把记忆化结果放在由访问掩码和当前终点索引的一维表里；Python 版本则用字典缓存同样的状态。
搜索从每一个可能的起始点出发。到达某个状态后，实现会检查所有尚未访问的目标点，只保留那些“所需中间点已经全部包含在访问掩码内”的候选。对每个合法目标，加一表示“此处立刻结束的新密码”，再递归加入更长延伸的数量。因为每个状态只会被求解一次，算法无需显式枚举规模极其庞大的全部密码。
设 \(n=wh\)，\(d=\max(w,h)\)。预处理全部线段需求的代价为 \(O(n^2 d)\)，因为对每一对有序节点，最多需要走过 \(g-1\le d-1\) 个中间格点。对于实际的 \(4\times 4\) 棋盘，这一部分开销很小。
记忆化搜索至多拥有 \(n2^{n-1}\) 个可达状态 \((U,v)\)：对每个终点 \(v\)，访问集合可以是任何一个包含 \(v\) 的子集。每个状态最多尝试 \(n\) 个下一节点，因此总时间复杂度是 \(O(n^2 2^n)\)。空间复杂度为 \(O(n2^n+n^2)\)，主要由记忆化表主导。代入 \(n=16\) 可得最多 \(16\cdot 2^{16}=1{,}048{,}576\) 个记忆化表项，规模完全可控。
Нужно посчитать все допустимые графические пароли на решетке \(4\times 4\). Пароль представляет собой упорядоченную последовательность различных узлов длины не меньше \(2\). Если текущий узел равен \(a\), а следующий равен \(b\), то переход разрешен только тогда, когда все узлы решетки, лежащие строго внутри отрезка \(ab\), уже встречались раньше в последовательности.
Поэтому это не обычный подсчет путей в фиксированном графе. Возможность дальнего перехода зависит от того, какие точки уже были посещены, так что множество допустимых ходов меняется вместе с состоянием.
Обозначим через \(V\) множество всех точек решетки, причем \(|V|=n=wh\). В данной задаче \(w=h=4\), следовательно \(n=16\). Требуется посчитать каждый допустимый пароль ровно один раз.
Пусть текущий префикс имеет вид
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$$
Введем множество уже использованных вершин
$$U=\{v_1,v_2,\dots,v_k\}.$$
Главное наблюдение состоит в том, что дальнейшее развитие зависит не от полного порядка в префиксе, а только от
$$U,\qquad v_k.$$
Действительно, любой следующий ход проверяет лишь два условия: свободна ли вершина назначения и содержатся ли все обязательные промежуточные точки в \(U\). Так как повторять вершины нельзя, множество \(U\) увеличивается монотонно.
Возьмем две различные вершины
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
Положим
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
Стандартный факт о решетке говорит, что открытый отрезок от \(a\) до \(b\) содержит ровно \(g-1\) решетчатых точек. Они имеют вид
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$$
Если \(g=1\), то направление примитивно и внутренних точек нет. Если \(g>1\), то именно эти \(g-1\) точки должны быть посещены заранее, чтобы прыжок стал допустимым.
Для каждой упорядоченной пары различных вершин \((a,b)\) обозначим через \(R(a,b)\) множество внутренних точек открытого отрезка от \(a\) к \(b\).
Тогда переход из текущего конца \(v\) в еще не использованную вершину \(u\) разрешен тогда и только тогда, когда
$$u\notin U,\qquad R(v,u)\subseteq U.$$
Это полностью отделяет геометрию от поиска. Вся геометрическая информация вынесена в заранее вычисленные множества \(R(a,b)\), а динамическая часть сводится к проверке, лежат ли требуемые промежуточные точки в множестве уже посещенных вершин.
Пусть \(F(U,v)\) обозначает число допустимых продолжений состояния с множеством посещенных вершин \(U\) и текущим концом \(v\).
Если \(u\) является допустимой следующей вершиной, то добавление \(u\) создает
$$1$$
новый пароль, который заканчивается сразу в \(u\), а также
$$F(U\cup\{u\},u)$$
более длинных продолжений из нового состояния. Следовательно,
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
Если допустимых переходов нет, сумма пуста и \(F(U,v)=0\). Поскольку у каждого пароля есть единственное состояние непосредственно перед последним ходом, эта формула учитывает каждое допустимое продолжение ровно один раз.
Рассмотрим прыжок из \((0,3)\) в \((3,0)\). Здесь
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
Значит, промежуточные точки таковы:
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$$
Следовательно, префикс, заканчивающийся в \((0,3)\), может перепрыгнуть прямо в \((3,0)\) только тогда, когда точки \((1,2)\) и \((2,1)\) уже были посещены раньше. Если хотя бы одна из них отсутствует, переход запрещен.
Для сравнения рассмотрим переход из \((0,0)\) в \((3,2)\). В этом случае
$$g=\gcd(3,2)=1,$$
поэтому
$$R\bigl((0,0),(3,2)\bigr)=\varnothing.$$
Такой ход разрешен сразу, как только вершина назначения еще не использована. Именно это различие между примитивными и непримитивными направлениями и использует рекурсия.
У каждого пароля есть единственная стартовая вершина \(s\in V\). После фиксации старта оставшееся число продолжений равно \(F(\{s\},s)\). Поэтому общее количество паролей равно
$$T=\sum_{s\in V} F(\{s\},s).$$
Одиночная стартовая вершина сама по себе не считается завершенным паролем; подсчет начинается только после добавления хотя бы одной новой вершины. Именно так ведут себя реализации.
Реализации на C++, Python и Java устроены одинаково. Сначала они перечисляют \(16\) точек решетки по их декартовым координатам. Затем для каждой упорядоченной пары различных вершин вычисляют НОД горизонтального и вертикального смещения, проходят отрезок примитивными шагами и сохраняют множество \(R(a,b)\) всех обязательных промежуточных точек.
Поскольку на доске всего \(16\) позиций, множество посещенных вершин естественно кодируется битовой маской. Та же схема используется и для каждого заранее вычисленного множества требований. Благодаря этому проверка \(R(v,u)\subseteq U\) превращается в константную побитовую операцию. Компилируемые версии используют плоскую таблицу мемоизации, индексируемую посещенной маской и текущей конечной вершиной, а версия на Python хранит то же состояние в словаре.
Поиск запускается из каждой возможной стартовой вершины. В каждом состоянии перебираются все еще свободные назначения; остаются только те, для которых все нужные промежуточные точки уже содержатся в посещенной маске. Для каждого такого перехода добавляется единица за пароль, завершающийся немедленно после хода, а также рекурсивно учитывается число более длинных продолжений. Поскольку каждое состояние вычисляется только один раз, алгоритм не обязан явно перечислять гигантское число всех возможных паролей.
Пусть \(n=wh\), а \(d=\max(w,h)\). Предварительное вычисление всех геометрических требований занимает \(O(n^2 d)\) времени, потому что для каждой упорядоченной пары может понадобиться пройти до \(g-1\le d-1\) промежуточных точек. На реальной доске \(4\times 4\) эта стоимость мала.
Мемоизированный поиск имеет не более \(n2^{n-1}\) достижимых состояний \((U,v)\): для каждой конечной вершины \(v\) множество посещенных вершин может быть любым подмножеством, содержащим \(v\). В каждом состоянии проверяется до \(n\) кандидатных переходов, так что итоговая асимптотика по времени равна \(O(n^2 2^n)\). Память составляет \(O(n2^n+n^2)\) и в основном расходуется на таблицу мемоизации. При \(n=16\) это означает не более \(16\cdot 2^{16}=1{,}048{,}576\) мемоизированных записей.
المطلوب هو عدّ جميع كلمات المرور اللمسية الصحيحة على شبكة نقاط \(4\times 4\). كلمة المرور هي تسلسل مرتب من عقد مختلفة طولُه لا يقل عن \(2\). وإذا كانت العقدة الحالية هي \(a\) والعقدة التالية هي \(b\)، فإن الانتقال لا يكون مسموحًا إلا إذا كانت جميع نقاط الشبكة الواقعة داخل القطعة المستقيمة بين \(a\) و\(b\) قد استُخدمت سابقًا في التسلسل.
لهذا السبب فالمسألة ليست مجرد عدّ مسارات في رسم ثابت. صلاحية القفزات الطويلة تعتمد على النقاط التي زارتها السلسلة من قبل، ولذلك فإن مجموعة الحركات المسموح بها تتغير مع الحالة.
لنرمز إلى مجموعة جميع نقاط الشبكة بـ \(V\)، وليكن \(|V|=n=wh\). في المسألة الفعلية لدينا \(w=h=4\)، ومن ثم \(n=16\). والهدف هو عدّ كل كلمة مرور صحيحة مرة واحدة فقط.
لنفترض أن المقطع الحالي من كلمة المرور هو
$$P=(v_1,v_2,\dots,v_k),\qquad v_i\in V,\qquad v_i\ne v_j\quad(i\ne j).$$
ونعرّف مجموعة النقاط التي زِيرت بالفعل على أنها
$$U=\{v_1,v_2,\dots,v_k\}.$$
الملاحظة الحاسمة هي أن مستقبل البحث لا يعتمد على الترتيب الكامل للمقطع، بل يعتمد فقط على
$$U,\qquad v_k.$$
وهذا يكفي لأن أي حركة لاحقة لا تسأل إلا عن أمرين: هل الوجهة ما زالت غير مستخدمة، وهل جميع النقاط الداخلية المطلوبة موجودة بالفعل داخل \(U\)؟ وبما أن العقد لا تتكرر، فإن المجموعة \(U\) تكبر على نحو أحادي أثناء البناء.
خذ عقدتين مختلفتين
$$a=(x_a,y_a),\qquad b=(x_b,y_b).$$
ولنضع
$$\Delta x=x_b-x_a,\qquad \Delta y=y_b-y_a,\qquad g=\gcd(|\Delta x|,|\Delta y|).$$
هناك حقيقة قياسية في هندسة الشبكات تقول إن القطعة المفتوحة من \(a\) إلى \(b\) تحتوي بالضبط على \(g-1\) من نقاط الشبكة، وهذه النقاط هي
$$\left(x_a+t\frac{\Delta x}{g},\ y_a+t\frac{\Delta y}{g}\right),\qquad t=1,2,\dots,g-1.$$
فإذا كان \(g=1\) فلا توجد أي نقاط داخلية أصلًا. أما إذا كان \(g>1\)، فإن هذه النقاط \(g-1\) هي تحديدًا النقاط التي يجب أن تكون قد زِيرت سابقًا قبل السماح بهذه القفزة.
لكل زوج مرتب \((a,b)\) من العقد المختلفة، لنعرّف \(R(a,b)\) على أنها مجموعة نقاط الشبكة الداخلية الواقعة على القطعة المفتوحة بين \(a\) و\(b\).
عندئذٍ يكون الانتقال من العقدة الأخيرة الحالية \(v\) إلى عقدة غير مستخدمة \(u\) قانونيًا إذا وفقط إذا تحقق الشرطان
$$u\notin U,\qquad R(v,u)\subseteq U.$$
بهذا الشكل تنفصل الهندسة تمامًا عن البحث. فكل المعلومات الهندسية تختزنها المجموعات المحسوبة مسبقًا \(R(a,b)\)، أما الجزء الديناميكي فلا يزيد على اختبار ما إذا كانت نقاط العبور المطلوبة موجودة بالفعل داخل مجموعة الزيارة.
لنعرّف \(F(U,v)\) بأنه عدد الامتدادات الصحيحة الممكنة انطلاقًا من حالة تكون فيها مجموعة النقاط المزارة هي \(U\) والنقطة الأخيرة هي \(v\).
إذا كانت \(u\) عقدة تالية صالحة، فإن إضافتها تولّد
$$1$$
كلمة مرور جديدة تنتهي مباشرة عند \(u\)، كما تولّد أيضًا
$$F(U\cup\{u\},u)$$
من الامتدادات الأطول انطلاقًا من الحالة الجديدة. لذا نحصل على
$$F(U,v)=\sum_{\substack{u\in V\setminus U\\ R(v,u)\subseteq U}}\left(1+F(U\cup\{u\},u)\right).$$
إذا لم توجد أي وجهة قانونية، فإن هذا المجموع يكون فارغًا، ومن ثم \(F(U,v)=0\). وبما أن كل كلمة مرور تملك حالة وحيدة مباشرة قبل حركتها الأخيرة، فإن هذه العلاقة تعدّ كل امتداد صحيح مرة واحدة بالضبط.
لننظر إلى القفزة من \((0,3)\) إلى \((3,0)\). هنا
$$\Delta x=3,\qquad \Delta y=-3,\qquad g=\gcd(3,3)=3.$$
إذًا تكون نقاط العبور الداخلية
$$R\bigl((0,3),(3,0)\bigr)=\{(1,2),(2,1)\}.$$
وهذا يعني أن مقطعًا ينتهي عند \((0,3)\) لا يمكنه القفز مباشرة إلى \((3,0)\) إلا إذا كانت النقطتان \((1,2)\) و\((2,1)\) قد زِيرتا من قبل. وإذا كانت إحدى هاتين النقطتين غير مستخدمة بعد، فإن الحركة تكون ممنوعة.
أما القفزة من \((0,0)\) إلى \((3,2)\)، فإنها تحقق
$$g=\gcd(3,2)=1,$$
ولذلك
$$R\bigl((0,0),(3,2)\bigr)=\varnothing.$$
فتكون هذه الحركة مسموحة فورًا ما دامت الوجهة نفسها غير مستخدمة. وهذا هو الفارق الجوهري الذي تستغله العودية: بعض الاتجاهات متاحة دائمًا، وبعضها لا ينفتح إلا بعد أن تدخل نقاط داخلية معينة إلى مجموعة الزيارة.
لكل كلمة مرور نقطة بداية وحيدة \(s\in V\). وبعد تثبيت هذه البداية يصبح عدد الامتدادات المتبقية مساويًا لـ \(F(\{s\},s)\). ومن ثم فإن العدد الكلي هو
$$T=\sum_{s\in V} F(\{s\},s).$$
الحالات المكوّنة من نقطة واحدة فقط لا تُحسب هنا باعتبارها كلمات مرور مكتملة؛ يبدأ العد فقط بعد إضافة عقدة واحدة أخرى على الأقل، وهذا يطابق سلوك جميع التنفيذات.
تتبع تنفيذات C++ وPython وJava الخطة نفسها. فهي تبدأ أولًا بترقيم نقاط الشبكة الست عشرة وفق إحداثياتها الديكارتية. ثم تحسب لكل زوج مرتب من العقد المختلفة القاسم المشترك الأكبر للإزاحتين الأفقية والعمودية، وتسير على القطعة بخطوات أولية، وتحفظ مجموعة النقاط الداخلية المطلوبة \(R(a,b)\).
وبما أن اللوحة تحتوي على \(16\) نقطة فقط، فمن الطبيعي تمثيل مجموعة النقاط المزارة بقناع بتات. والتمثيل نفسه يُستخدم لكل مجموعة متطلبات محسوبة مسبقًا. وبهذا يتحول الشرط \(R(v,u)\subseteq U\) إلى عملية بتية ثابتة الزمن. التنفيذان المترجمان إلى كود آلي يستخدمان جدول حفظ خطيًا مفهرسًا بقناع الزيارة والنقطة الأخيرة، بينما يخزن تنفيذ Python الحالة نفسها في قاموس حفظ.
يبدأ البحث من كل نقطة بداية ممكنة. وفي كل حالة، يُفحص كل هدف غير مستخدم، ولا يُحتفظ إلا بالأهداف التي صارت جميع نقاطها الداخلية المطلوبة ضمن قناع الزيارة. ولكل حركة صالحة يُضاف واحد يمثل كلمة المرور التي تنتهي مباشرة بعد هذه الحركة، ثم يُضاف عدد الامتدادات الأطول المحسوب عوديًا من الحالة الجديدة. وبما أن كل حالة تُحل مرة واحدة فقط، فلا حاجة إلى تعداد جميع كلمات المرور الممكنة صراحةً، وهي كثيرة جدًا.
إذا رمزنا إلى \(n=wh\) وإلى \(d=\max(w,h)\)، فإن حساب جميع متطلبات القطع المستقيمة مسبقًا يكلف \(O(n^2 d)\) من الزمن، لأن كل زوج مرتب قد يحتاج إلى المرور على ما يصل إلى \(g-1\le d-1\) من النقاط الداخلية. وعلى لوحة \(4\times 4\) الفعلية، تبقى هذه الكلفة صغيرة جدًا.
أما البحث المعتمد على الحفظ فله في أقصى الأحوال \(n2^{n-1}\) حالة قابلة للوصول من الشكل \((U,v)\): فلكل نقطة أخيرة \(v\)، يمكن أن تكون مجموعة الزيارة أي مجموعة فرعية تحتوي \(v\). ويجرب كل وضع حتى \(n\) أهداف تالية، لذلك يكون زمن التنفيذ الكلي \(O(n^2 2^n)\). واستهلاك الذاكرة هو \(O(n2^n+n^2)\)، ويهيمن عليه جدول الحفظ. وعندما \(n=16\)، فهذا يعني وجود ما لا يزيد على \(16\cdot 2^{16}=1{,}048{,}576\) مدخلة محفوظة.