A hop moves from one heptagon to a neighboring heptagon, so the problem can be viewed on the infinite heptagon-adjacency graph, equivalently the dual graph of the order-3 heptagonal tiling. Fix a starting heptagon \(r\). For each \(t\), let \(F(t)\) denote the number of \(t\)-step walks that start at \(r\) and return to \(r\). The implementations evaluate this quantity at \(t=20\).
The recurrence for walk counting is simple; the subtle part is building exactly the finite region of the infinite graph that can influence a length-\(t\) return walk. The solutions do that by expanding concentric layers around \(r\), distinguishing two genuine geometric types of heptagons in each ring, and then running repeated adjacency propagation on the resulting finite ball.
Let \(L_d\) be the set of heptagons at graph distance \(d\) from the starting heptagon \(r\). The code does not attempt to represent the whole infinite tiling. Instead, it constructs the ball \(L_0\cup L_1\cup\cdots\cup L_R\) for a carefully chosen radius \(R\), and then counts walks inside that ball exactly.
The frontier is stored as a cyclic list of still-unused outward sides. A heptagon in the current outer ring appears in that list once for each outward side that has not yet been attached to the next ring. This is the key encoding invariant.
When two consecutive frontier entries are different, the next heptagon touches both corresponding parents, so a new corner heptagon is created. When a frontier entry survives without being paired across such a transition, it produces a side heptagon attached to just one parent. After the new ring is created, consecutive heptagons in that ring are connected cyclically, because the ring closes around the origin.
For \(d\ge 1\), write \(S_d\) for the number of side heptagons in layer \(L_d\), \(C_d\) for the number of corner heptagons, and \(N_d=S_d+C_d\) for the total size of the layer. The first ring contains only side heptagons:
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
Now examine how one layer creates the next. Every transition between two neighboring parents on the cyclic frontier creates exactly one corner heptagon, so
$$C_{d+1}=N_d.$$
A side heptagon in \(L_d\) contributes four outward frontier slots. Two are consumed by the corner creations at the ends of its block, leaving two side children. A corner heptagon contributes three outward slots, of which one remains after the two boundary transitions are used. Therefore
$$S_{d+1}=2S_d+C_d.$$
Combining the two relations gives a one-variable recurrence for the ring sizes:
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
with initial values \(N_1=7\) and \(N_2=21\). If
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2},$$
then
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$$
This closed form is not required by the code, but it explains the exponential growth of the layers and therefore the eventual cost of the computation.
The construction is designed so that every completed interior heptagon has exactly seven neighbors.
A side heptagon has one parent in the previous layer, two neighbors in its own cyclic ring, and four outward neighbors in the next layer, so its degree is
$$1+2+4=7.$$
A corner heptagon has two parents, two same-layer neighbors, and three outward neighbors, so its degree is
$$2+2+3=7.$$
The starting heptagon also has degree \(7\), because the first ring contains exactly seven adjacent heptagons. The validation logic in the implementations checks this invariant for every non-boundary heptagon that has already been fully expanded.
Suppose a closed walk of length \(t\) reaches some layer \(L_d\). It needs at least \(d\) hops to get from \(r\) to \(L_d\), and at least \(d\) more hops to return to \(r\). Hence
$$2d\le t,$$
so no such walk can ever visit a layer deeper than \(\lfloor t/2\rfloor\). This makes the truncation exact rather than approximate: the finite ball of radius \(\lfloor t/2\rfloor\) already contains every heptagon that can appear in a length-\(t\) return walk.
Once the required ball has been built, the counting step is standard graph theory. Let \(w_t(v)\) be the number of length-\(t\) walks from \(r\) to a heptagon \(v\) inside the constructed ball. Then
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
with initial conditions
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
The required quantity is just
$$F(t)=w_t(r).$$
If \(A\) is the adjacency matrix of the finite ball and \(e_r\) is the basis vector at the root, then the same statement is
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r.$$
The implementations use sparse adjacency lists and repeated sweeps instead of explicit matrix powers, but mathematically the two views are identical.
Start with the root heptagon \(r\). The initial cyclic frontier consists of seven copies of \(r\), one for each outward side. Because adjacent frontier entries are still the same heptagon, no corner creation is possible yet. Therefore the first ring is simply
$$S_1=7,\qquad C_1=0.$$
Now each heptagon in that first ring contributes four frontier slots, so the next frontier is seven consecutive blocks of length \(4\). The seven block boundaries create exactly seven corner heptagons. Inside each block, two slots remain unpaired, so each block also creates two side heptagons. Hence
$$C_2=7,\qquad S_2=14,\qquad N_2=21.$$
This picture already explains the first checkpoints. There are \(7\) two-step returns, because one may hop to any of the seven neighbors and immediately hop back. There are \(14\) three-step returns, because after the first hop one may move to either of the two adjacent heptagons in the first ring and then return to the root. The implementations also verify the next value \(F(4)=119\) before proceeding to the target \(F(20)\).
The C++, Python, and Java implementations first build the rooted ball of radius \(\lfloor \max(t,4)/2\rfloor\), so the target step count and the short validation checkpoints are all covered. They maintain the cyclic frontier of open sides, create corner heptagons at transitions between different parents, create side heptagons on the remaining frontier slots, and then connect the newly created ring into a cycle.
After a ring has been closed, the next frontier is formed by repeating each new heptagon according to its remaining outward degree: \(4\) copies for a side heptagon and \(3\) copies for a corner heptagon. That compact representation carries exactly the information needed to create the following ring without ever storing geometric coordinates.
Once the graph has been constructed, the implementation keeps two count vectors: the current distribution of walk endpoints and the next one. One sweep over the adjacency lists applies the recurrence \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\). Repeating that sweep up to the desired step count yields the closed-walk total at the root entry.
The same loop also checks the known values \(F(2)=7\), \(F(3)=14\), and \(F(4)=119\). The C++ and Java versions parallelize the per-vertex sweep; the Python version performs the same arithmetic serially.
Let \(T\) be the requested number of hops and let \(R=\lfloor T/2\rfloor\). Because \(N_d\) grows like \(\alpha^d\) with \(\alpha=(3+\sqrt5)/2\), the number of heptagons in the radius-\(R\) ball satisfies
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$$
The graph is 7-regular away from the outer boundary, so the number of edges is of the same order as the number of vertices. Building the ball therefore costs \(\Theta(\alpha^R)\), and one adjacency-propagation step also costs \(\Theta(\alpha^R)\). The full computation takes
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$$
time and \(\Theta(\alpha^R)\) memory for the graph plus two walk-count vectors. For the concrete target \(T=20\), this direct dynamic-programming approach is easily small enough to run exactly with ordinary integer arithmetic.
Ein Sprung wechselt von einem Heptagon zu einem benachbarten Heptagon. Damit arbeitet das Problem auf dem unendlichen Nachbarschaftsgraphen der Heptagone, also äquivalent auf dem Dualgraphen der regulären heptagonalen Pflasterung \(\{7,3\}\). Sei \(r\) das Startheptagon. Für jedes \(t\) bezeichne \(F(t)\) die Anzahl der Wege der Länge \(t\), die in \(r\) beginnen und wieder in \(r\) enden. Die Implementierungen berechnen diesen Wert für \(t=20\).
Die Rekursion für Wegzahlen ist an sich einfach. Der eigentliche Punkt besteht darin, aus dem unendlichen Graphen genau den endlichen Ausschnitt zu konstruieren, der eine Rückkehr in \(t\) Schritten überhaupt beeinflussen kann. Genau dazu bauen die Lösungen konzentrische Schichten um \(r\), unterscheiden zwei echte Geometrietypen in jedem Ring und führen anschließend eine Adjazenz-Propagation auf diesem endlichen Ball aus.
Bezeichne mit \(L_d\) die Menge aller Heptagone im Graphabstand \(d\) vom Startheptagon \(r\). Der Code repräsentiert nicht die gesamte unendliche Pflasterung, sondern nur den Ball \(L_0\cup L_1\cup\cdots\cup L_R\) für einen passend gewählten Radius \(R\). Auf diesem Ball wird die Zahl der Wege exakt berechnet.
Die aktuelle Außengrenze wird als zyklische Liste noch freier Außenseiten gespeichert. Ein Heptagon im äußeren Ring erscheint in dieser Liste genau so oft, wie es noch nicht belegte Seiten in Richtung des nächsten Rings besitzt. Das ist die zentrale Invariante der Konstruktion.
Wenn zwei aufeinanderfolgende Einträge der Grenzliste verschieden sind, berührt das nächste Heptagon beide zugehörigen Elternheptagone; es entsteht also ein Eckheptagon. Bleibt ein Grenzeintrag ohne eine solche Paarung übrig, so erzeugt er ein Seitenheptagon mit genau einem Elternheptagon. Nach dem Erzeugen eines Rings werden benachbarte neue Heptagone zyklisch verbunden, denn der Ring schließt sich vollständig um den Ursprung.
Für \(d\ge 1\) sei \(S_d\) die Anzahl der Seitenheptagone in \(L_d\), \(C_d\) die Anzahl der Eckheptagone und \(N_d=S_d+C_d\) die Gesamtgröße des Rings. Der erste Ring enthält nur Seitenheptagone:
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
Nun betrachtet man, wie ein Ring den nächsten erzeugt. Jeder Übergang zwischen zwei benachbarten Elternheptagonen auf der zyklischen Grenze erzeugt genau ein Eckheptagon. Also gilt
$$C_{d+1}=N_d.$$
Ein Seitenheptagon in \(L_d\) liefert vier Außenslots. Zwei davon werden an den Blockenden von Eckheptagonen verbraucht, also bleiben zwei Slots für Seitenkinder übrig. Ein Eckheptagon liefert drei Außenslots; nach den beiden Randübergängen bleibt genau ein Slot übrig. Deshalb
$$S_{d+1}=2S_d+C_d.$$
Daraus folgt für die Ringgrößen die eindimensionale Rekurrenz
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
mit \(N_1=7\) und \(N_2=21\). Für
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2}$$
ergibt sich sogar die geschlossene Form
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$$
Die Implementierungen benötigen diese Formel nicht direkt, aber sie erklärt das exponentielle Wachstum der Ringe und damit die Größenordnung der Laufzeit.
Die Konstruktion ist so angelegt, dass jedes vollständig ausgebaute innere Heptagon genau sieben Nachbarn besitzt.
Ein Seitenheptagon hat ein Elternheptagon im vorigen Ring, zwei Nachbarn im eigenen Ring und vier Nachbarn im nächsten Ring. Sein Grad ist also
$$1+2+4=7.$$
Ein Eckheptagon hat zwei Eltern, zwei Nachbarn im selben Ring und drei äußere Nachbarn. Damit ist sein Grad
$$2+2+3=7.$$
Auch das Startheptagon hat Grad \(7\), weil der erste Ring genau sieben angrenzende Heptagone enthält. Die Validierung in den Implementierungen prüft diese Invariante für jedes bereits vollständig expandierte, also nicht mehr am Rand liegende Heptagon.
Nimmt man einen geschlossenen Weg der Länge \(t\), der irgendeinen Ring \(L_d\) erreicht, dann braucht der Weg mindestens \(d\) Sprünge von \(r\) nach \(L_d\) und mindestens \(d\) weitere Sprünge zurück. Also muss gelten
$$2d\le t.$$
Daher kann kein Rückkehrweg der Länge \(t\) jemals tiefer als bis \(L_{\lfloor t/2\rfloor}\) reichen. Die Trunkierung ist also exakt und keine Näherung: Der Ball vom Radius \(\lfloor t/2\rfloor\) enthält bereits alle Heptagone, die in einer solchen Rückkehr auftreten können.
Ist der benötigte Ball einmal aufgebaut, dann ist der Zählteil reine Graphentheorie. Sei \(w_t(v)\) die Zahl der Wege der Länge \(t\) vom Startheptagon \(r\) zu einem Heptagon \(v\) innerhalb des konstruierten Balls. Dann gilt
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
mit Anfangswerten
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
Gesucht ist also einfach
$$F(t)=w_t(r).$$
Ist \(A\) die Adjazenzmatrix des endlichen Balls und \(e_r\) der Basisvektor an der Wurzel, so lässt sich dasselbe auch als
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r$$
schreiben. Die Implementierungen verwenden dafür keine Matrixpotenzen, sondern sparsame Adjazenzlisten und wiederholte Durchläufe über die Nachbarn; mathematisch ist es derselbe Operator.
Man beginnt mit dem Wurzelheptagon \(r\). Die anfängliche zyklische Grenze besteht aus sieben Kopien von \(r\), je eine für jede Außenseite. Weil benachbarte Grenzeneinträge noch dasselbe Heptagon sind, kann zunächst kein Eckheptagon entstehen. Also ist der erste Ring einfach
$$S_1=7,\qquad C_1=0.$$
Danach liefert jedes Heptagon im ersten Ring vier Grenzslots, also besteht die nächste Grenze aus sieben Blöcken der Länge \(4\). Die sieben Blockgrenzen erzeugen genau sieben Eckheptagone. Innerhalb jedes Blocks bleiben zwei ungepaarte Slots übrig, also entstehen zusätzlich je zwei Seitenheptagone. Somit
$$C_2=7,\qquad S_2=14,\qquad N_2=21.$$
Dieses Bild erklärt bereits die ersten Kontrollwerte. Es gibt \(7\) Rückkehrwege der Länge \(2\), weil man eines der sieben Nachbarheptagone wählen und sofort zurückspringen kann. Es gibt \(14\) Rückkehrwege der Länge \(3\), weil man nach dem ersten Sprung zu einem der beiden benachbarten Heptagone im ersten Ring weitergehen und dann zur Wurzel zurückkehren kann. Die Implementierungen prüfen außerdem noch \(F(4)=119\), bevor sie den Zielwert \(F(20)\) ausgeben.
Die C++-, Python- und Java-Implementierungen bauen zuerst den Ball vom Radius \(\lfloor \max(t,4)/2\rfloor\) auf, sodass sowohl die Zielschrittzahl als auch die kurzen Validierungspunkte enthalten sind. Dazu führen sie die zyklische Grenzliste offener Seiten, erzeugen an Übergängen zwischen verschiedenen Eltern Eckheptagone, auf den übrigen Grenzslots Seitenheptagone und verbinden den neu erzeugten Ring anschließend zyklisch.
Nach dem Schließen eines Rings wird die nächste Grenze gebildet, indem jedes neue Heptagon entsprechend seinem verbleibenden Außengrad wiederholt wird: \(4\)-mal für ein Seitenheptagon und \(3\)-mal für ein Eckheptagon. Dadurch reichen rein kombinatorische Daten aus; geometrische Koordinaten werden nirgends benötigt.
Nach dem Graphaufbau hält die Implementierung zwei Zählvektoren: die aktuelle Verteilung der Endpunkte und die nächste. Ein Durchlauf über die Adjazenzlisten setzt die Rekurrenz \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\) um. Nach \(t\) solchen Durchläufen steht die gesuchte Anzahl geschlossener Wege im Wurzeleintrag.
Dieselbe Schleife überprüft auch die bekannten Werte \(F(2)=7\), \(F(3)=14\) und \(F(4)=119\). Die C++- und Java-Versionen parallelisieren den Vertex-Durchlauf; die Python-Version führt dieselbe Rechnung seriell aus.
Sei \(T\) die gewünschte Schrittzahl und \(R=\lfloor T/2\rfloor\). Da \(N_d\) wie \(\alpha^d\) mit \(\alpha=(3+\sqrt5)/2\) wächst, erfüllt die Anzahl der Heptagone im Ball vom Radius \(R\)
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$$
Abgesehen vom äußeren Rand ist der Graph 7-regulär, deshalb ist die Kantenzahl von derselben Größenordnung wie die Knotenzahl. Der Aufbau des Balls kostet also \(\Theta(\alpha^R)\), und ein einzelner Adjazenz-Durchlauf kostet ebenfalls \(\Theta(\alpha^R)\). Insgesamt ergibt sich
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$$
Zeit sowie \(\Theta(\alpha^R)\) Speicher für den Graphen plus zwei Zählvektoren. Für das konkrete Ziel \(T=20\) ist dieser direkte dynamische Ansatz problemlos klein genug, um exakt mit gewöhnlicher Ganzzahlarithmetik zu laufen.
Bir sıçrama, bir heptagondan komşu bir heptagona geçiştir. Dolayısıyla problem, sonsuz heptagon-komşuluk grafiği üzerinde düşünülebilir; eşdeğer olarak bu, \(\{7,3\}\) düzenli heptagonal döşemenin dual grafiğidir. Başlangıç heptagonu \(r\) olsun. Her \(t\) için \(F(t)\), \(r\)'de başlayıp yine \(r\)'de biten \(t\) adımlık yürüyüşlerin sayısıdır. Uygulamalar bu değeri \(t=20\) için hesaplar.
Yürüyüş sayımı için temel yineleme basittir. Asıl zorluk, sonsuz grafın içinden uzunluğu \(t\) olan bir geri dönüş yürüyüşünü etkileyebilecek tam sonlu bölgeyi kurmaktır. Çözümler bunu \(r\) etrafında eşmerkezli katmanlar oluşturarak, her halkadaki iki gerçek geometrik heptagon tipini ayırt ederek ve daha sonra elde edilen sonlu top üzerinde komşuluk yayılımı yaparak başarır.
\(L_d\), başlangıç heptagonu \(r\)'ye graf uzaklığı \(d\) olan heptagonlar kümesi olsun. Kod, sonsuz döşemenin tamamını temsil etmez; bunun yerine uygun bir \(R\) yarıçapı için \(L_0\cup L_1\cup\cdots\cup L_R\) topunu kurar ve yürüyüş sayılarını bu top üzerinde tam olarak hesaplar.
Dış sınır, henüz kullanılmamış dış kenarların çevrimsel bir listesi olarak tutulur. Mevcut en dış halkadaki bir heptagon, bir sonraki halkaya bağlanmamış dış kenarı sayısı kadar bu listede görünür. Kuruluşun ana değişmezi budur.
Bu sınır listesindeki ardışık iki giriş farklıysa, sıradaki heptagon her iki ebeveyn heptagona da dokunur; böylece bir köşe heptagonu oluşur. Bir giriş böyle bir geçişte eşlenmeden kalırsa, yalnızca tek ebeveyne bağlı bir yan heptagon üretir. Yeni halka oluşturulduktan sonra, o halkadaki ardışık heptagonlar çevrimsel olarak bağlanır; çünkü halka başlangıç noktasının etrafında kapanır.
\(d\ge 1\) için \(S_d\), \(L_d\) katmanındaki yan heptagonların; \(C_d\) köşe heptagonların; \(N_d=S_d+C_d\) ise toplam halka büyüklüğünün sayısı olsun. İlk halka yalnızca yan heptagonlardan oluşur:
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
Şimdi bir halkanın sonrakini nasıl ürettiğine bakalım. Çevrimsel sınır üzerindeki komşu iki ebeveyn arasındaki her geçiş tam bir köşe heptagonu oluşturur. Bu yüzden
$$C_{d+1}=N_d.$$
\(L_d\) içindeki bir yan heptagon dört dış sınır yuvası verir. Bunların ikisi blok uçlarındaki köşe oluşumlarında kullanılır; geriye iki yan çocuk kalır. Bir köşe heptagon üç dış yuva verir; iki sınır geçişi kullanıldıktan sonra bir yuva kalır. Dolayısıyla
$$S_{d+1}=2S_d+C_d.$$
Bu iki bağıntı birleştirilirse toplam halka boyutları için tek değişkenli yineleme elde edilir:
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
başlangıç değerleri de \(N_1=7\) ve \(N_2=21\)'dir. Eğer
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2}$$
alınırsa kapalı form
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right)$$
olur. Kod bu formülü doğrudan kullanmaz; ancak halkaların üstel büyüdüğünü ve dolayısıyla maliyetin nasıl ölçeklendiğini açıklar.
Kurgu, her tamamlanmış iç heptagonun tam olarak yedi komşuya sahip olacağı şekilde tasarlanmıştır.
Bir yan heptagonun bir önceki katmanda bir ebeveyni, kendi halkasında iki komşusu ve bir sonraki katmanda dört dış komşusu vardır. Bu yüzden derecesi
$$1+2+4=7$$
olur. Bir köşe heptagonun iki ebeveyni, aynı halkada iki komşusu ve dışarıda üç komşusu vardır; dolayısıyla derecesi
$$2+2+3=7$$
olur. Başlangıç heptagonunun derecesi de \(7\)'dir; çünkü ilk halka tam yedi komşu heptagon içerir. Uygulamalardaki doğrulama, tamamen genişletilmiş ve artık sınırda olmayan her heptagon için bu değişmezi denetler.
Uzunluğu \(t\) olan kapalı bir yürüyüşün \(L_d\) katmanına kadar ulaştığını varsayalım. Bu yürüyüşün \(r\)'den \(L_d\)'ye gitmesi için en az \(d\) adım, oradan geri dönmesi için de en az \(d\) adım gerekir. O halde
$$2d\le t$$
olmalıdır. Demek ki uzunluğu \(t\) olan hiçbir geri dönüş yürüyüşü \(\lfloor t/2\rfloor\) katmanından daha derine inemez. Bu nedenle kesme işlemi yaklaşık değil, tamdır: \(\lfloor t/2\rfloor\) yarıçaplı top, böyle bir yürüyüşte görünebilecek tüm heptagonları zaten içerir.
Gerekli top kurulduktan sonra sayım kısmı standart graf teorisidir. \(w_t(v)\), kurulan top içinde \(r\)'den \(v\)'ye giden uzunluğu \(t\) olan yürüyüşlerin sayısı olsun. O zaman
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
başlangıç koşullarıyla birlikte
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
İstenen nicelik doğrudan
$$F(t)=w_t(r)$$
olur. Eğer \(A\), sonlu topun komşuluk matrisi ve \(e_r\) de kökteki baz vektör ise aynı ifade
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r$$
biçiminde de yazılır. Uygulamalar açık matris üsleri kullanmak yerine seyrek komşuluk listeleri üzerinde tekrar tekrar tarama yapar; ama matematiksel olarak bu tamamen aynı işlemdir.
Kök heptagon \(r\) ile başlayalım. Başlangıçtaki çevrimsel sınır, dışarı bakan her kenar için bir tane olmak üzere yedi adet \(r\) kopyasından oluşur. Komşu sınır girişleri hâlâ aynı heptagon olduğu için bu aşamada köşe üretimi olmaz. Dolayısıyla ilk halka
$$S_1=7,\qquad C_1=0$$
şeklindedir. Sonra bu ilk halkadaki her heptagon dört sınır yuvası verdiğinden, bir sonraki sınır uzunluğu \(4\) olan yedi bloktan oluşur. Bu blokların sınırları tam yedi köşe heptagonu üretir. Her blok içinde iki eşlenmemiş yuva kaldığı için ayrıca ikişer yan heptagon oluşur. Böylece
$$C_2=7,\qquad S_2=14,\qquad N_2=21$$
elde edilir. Bu resim ilk kontrol değerlerini de açıklar. Uzunluğu \(2\) olan geri dönüş sayısı \(7\)'dir; çünkü yedi komşudan herhangi birine gidip hemen geri dönülebilir. Uzunluğu \(3\) olan geri dönüş sayısı \(14\)'tür; çünkü ilk adımdan sonra ilk halkadaki iki komşu heptagondan birine geçip sonra köke dönülebilir. Uygulamalar hedef \(F(20)\)'ye geçmeden önce \(F(4)=119\) değerini de ayrıca doğrular.
C++, Python ve Java uygulamaları önce \(\lfloor \max(t,4)/2\rfloor\) yarıçaplı köklü topu kurar; böylece hem hedef adım sayısı hem de kısa doğrulama kontrolleri kapsanır. Bunun için açık kenarların çevrimsel sınırını tutar, farklı ebeveynler arasındaki geçişlerde köşe heptagonları üretir, kalan yuvalarda yan heptagonları oluşturur ve yeni halkayı çevrim olarak kapatır.
Bir halka kapandıktan sonra sıradaki sınır, her yeni heptagonu kalan dış derece sayısı kadar tekrar ederek oluşturulur: yan heptagon için \(4\), köşe heptagon için \(3\). Böylece geometrik koordinatlar tutmadan, yalnızca kombinatoryal bilgiyle bir sonraki halka üretilebilir.
Graf kurulduktan sonra uygulama iki sayım vektörü tutar: mevcut yürüyüş sonları ve bir sonraki adımın sonları. Komşuluk listeleri üzerinde tek tarama, \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\) yinelemesini uygular. Bu tarama \(t\) kez tekrarlandığında kök girişindeki değer istenen kapalı yürüyüş sayısıdır.
Aynı döngü \(F(2)=7\), \(F(3)=14\) ve \(F(4)=119\) değerlerini de kontrol eder. C++ ve Java sürümleri düğümler üzerindeki bu taramayı paralelleştirir; Python sürümü aynı aritmetiği seri uygular.
\(T\) hedef adım sayısı ve \(R=\lfloor T/2\rfloor\) olsun. \(N_d\) değeri \(\alpha=(3+\sqrt5)/2\) tabanıyla \(\alpha^d\) mertebesinde büyüdüğü için, \(R\) yarıçaplı top içindeki heptagon sayısı
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R)$$
olur. Grafik dış sınır dışında 7-düzenli olduğu için kenar sayısı da düğüm sayısıyla aynı mertebededir. Bu nedenle topu kurma maliyeti \(\Theta(\alpha^R)\), tek bir komşuluk yayılımı adımı da yine \(\Theta(\alpha^R)\) olur. Toplam süre
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$$
ve bellek kullanımı graf ile iki sayım vektörü için \(\Theta(\alpha^R)\)'dir. Somut hedef \(T=20\) olduğunda bu doğrudan dinamik programlama yaklaşımı sıradan tamsayı aritmetiğiyle rahatça çalışacak kadar küçüktür.
Un salto pasa de un heptágono a otro heptágono adyacente. Por eso el problema puede verse sobre el grafo infinito de adyacencia entre heptágonos, o de forma equivalente sobre el grafo dual del mosaico heptagonal regular \(\{7,3\}\). Fijemos un heptágono inicial \(r\). Para cada \(t\), \(F(t)\) es el número de caminatas de longitud \(t\) que empiezan en \(r\) y regresan a \(r\). Las implementaciones evalúan esta cantidad en \(t=20\).
La recurrencia de conteo de caminatas es sencilla. La dificultad real está en construir exactamente la región finita del grafo infinito que puede influir en una caminata de retorno de longitud \(t\). Las soluciones lo hacen expandiendo capas concéntricas alrededor de \(r\), distinguiendo dos tipos geométricos reales de heptágonos en cada anillo y después aplicando propagación por adyacencia dentro de la bola finita resultante.
Sea \(L_d\) el conjunto de heptágonos a distancia de grafo \(d\) del heptágono inicial \(r\). El código no intenta representar todo el mosaico infinito. En su lugar, construye la bola \(L_0\cup L_1\cup\cdots\cup L_R\) para un radio \(R\) elegido con cuidado, y dentro de esa bola cuenta exactamente las caminatas.
La frontera exterior se guarda como una lista cíclica de lados salientes todavía libres. Un heptágono del anillo exterior actual aparece en esa lista tantas veces como lados exteriores sin usar le queden hacia el siguiente anillo. Ese es el invariante central de la construcción.
Si dos entradas consecutivas de la frontera son distintas, el siguiente heptágono toca a los dos padres correspondientes y se crea un heptágono de esquina. Si una entrada queda sin emparejar en una transición de ese tipo, produce un heptágono lateral unido a un solo padre. Cuando el nuevo anillo ya existe, sus heptágonos consecutivos se conectan cíclicamente, porque el anillo se cierra alrededor del origen.
Para \(d\ge 1\), sea \(S_d\) el número de heptágonos laterales en \(L_d\), \(C_d\) el número de heptágonos de esquina y \(N_d=S_d+C_d\) el tamaño total de la capa. El primer anillo contiene solo heptágonos laterales:
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
Ahora estudiemos cómo un anillo crea el siguiente. Cada transición entre dos padres vecinos en la frontera cíclica genera exactamente un heptágono de esquina, así que
$$C_{d+1}=N_d.$$
Un heptágono lateral en \(L_d\) aporta cuatro ranuras exteriores. Dos se consumen en las esquinas de los extremos del bloque, de modo que quedan dos hijos laterales. Un heptágono de esquina aporta tres ranuras exteriores; después de usar las dos transiciones de borde queda una. Por tanto
$$S_{d+1}=2S_d+C_d.$$
Al combinar ambas relaciones se obtiene una recurrencia escalar para los tamaños de capa:
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
con valores iniciales \(N_1=7\) y \(N_2=21\). Si definimos
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2},$$
entonces
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$$
El código no necesita esta forma cerrada de manera explícita, pero sí explica por qué las capas crecen exponencialmente y, con ello, por qué escala así el coste total.
La construcción está diseñada para que cada heptágono interior ya completado tenga exactamente siete vecinos.
Un heptágono lateral tiene un padre en la capa anterior, dos vecinos en su propio anillo y cuatro vecinos hacia fuera en la siguiente capa. Su grado es
$$1+2+4=7.$$
Un heptágono de esquina tiene dos padres, dos vecinos en la misma capa y tres vecinos exteriores. Su grado es
$$2+2+3=7.$$
El heptágono inicial también tiene grado \(7\), porque el primer anillo contiene exactamente siete vecinos. La validación de las implementaciones comprueba este invariante para cada heptágono no fronterizo que ya quedó totalmente expandido.
Supongamos que una caminata cerrada de longitud \(t\) alcanza alguna capa \(L_d\). Necesita por lo menos \(d\) saltos para ir desde \(r\) hasta \(L_d\) y al menos \(d\) más para volver a \(r\). Por lo tanto
$$2d\le t.$$
Así, ninguna caminata de retorno de longitud \(t\) puede visitar capas más profundas que \(L_{\lfloor t/2\rfloor}\). La truncación no es aproximada sino exacta: la bola de radio \(\lfloor t/2\rfloor\) ya contiene todos los heptágonos que pueden aparecer en una caminata cerrada de longitud \(t\).
Una vez construida la bola necesaria, la parte de conteo es teoría de grafos estándar. Sea \(w_t(v)\) el número de caminatas de longitud \(t\) desde \(r\) hasta un heptágono \(v\) dentro de la bola construida. Entonces
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
con condiciones iniciales
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
La cantidad pedida es simplemente
$$F(t)=w_t(r).$$
Si \(A\) es la matriz de adyacencia de la bola finita y \(e_r\) el vector base del origen, la misma afirmación puede escribirse como
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r.$$
Las implementaciones usan listas de adyacencia dispersas y barridos repetidos en lugar de potencias explícitas de matrices, pero matemáticamente el operador es el mismo.
Empezamos con el heptágono raíz \(r\). La frontera cíclica inicial está formada por siete copias de \(r\), una por cada lado saliente. Como entradas consecutivas de la frontera siguen siendo el mismo heptágono, todavía no puede aparecer ningún heptágono de esquina. Por lo tanto, el primer anillo es
$$S_1=7,\qquad C_1=0.$$
Después, cada heptágono del primer anillo aporta cuatro ranuras de frontera, así que la siguiente frontera consta de siete bloques consecutivos de longitud \(4\). Las siete separaciones entre bloques crean exactamente siete heptágonos de esquina. Dentro de cada bloque quedan dos ranuras sin emparejar, de modo que también nacen dos heptágonos laterales por bloque. Así,
$$C_2=7,\qquad S_2=14,\qquad N_2=21.$$
Esta imagen ya explica los primeros valores de control. Hay \(7\) retornos de longitud \(2\), porque puede elegirse cualquiera de los siete vecinos y volver de inmediato. Hay \(14\) retornos de longitud \(3\), porque tras el primer salto se puede avanzar a uno de los dos heptágonos adyacentes del primer anillo y luego regresar a la raíz. Las implementaciones también verifican \(F(4)=119\) antes de continuar hacia el objetivo \(F(20)\).
Las implementaciones en C++, Python y Java construyen primero la bola enraizada de radio \(\lfloor \max(t,4)/2\rfloor\), de modo que tanto el número de pasos objetivo como los puntos breves de validación queden cubiertos. Mantienen la frontera cíclica de lados libres, crean heptágonos de esquina en las transiciones entre padres distintos, crean heptágonos laterales en las ranuras restantes y luego cierran el nuevo anillo como un ciclo.
Una vez cerrado un anillo, la frontera siguiente se forma repitiendo cada nuevo heptágono según su grado exterior restante: \(4\) copias si es lateral y \(3\) si es de esquina. Esa representación compacta conserva exactamente la información necesaria para producir el siguiente anillo sin recurrir a coordenadas geométricas.
Cuando el grafo ya está construido, la implementación mantiene dos vectores de conteo: la distribución actual de extremos de caminata y la siguiente. Un barrido sobre las listas de adyacencia aplica la recurrencia \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\). Al repetir ese barrido hasta el paso deseado, la entrada correspondiente a la raíz contiene el número de caminatas cerradas buscado.
Ese mismo bucle comprueba además los valores conocidos \(F(2)=7\), \(F(3)=14\) y \(F(4)=119\). Las versiones de C++ y Java paralelizan el barrido por vértices; la versión de Python realiza la misma aritmética en serie.
Sea \(T\) el número de saltos pedido y \(R=\lfloor T/2\rfloor\). Como \(N_d\) crece como \(\alpha^d\) con \(\alpha=(3+\sqrt5)/2\), el número de heptágonos en la bola de radio \(R\) satisface
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$$
Salvo en la frontera externa, el grafo es 7-regular, así que el número de aristas es del mismo orden que el número de vértices. Construir la bola cuesta \(\Theta(\alpha^R)\), y un solo paso de propagación por adyacencia también cuesta \(\Theta(\alpha^R)\). En consecuencia, el cálculo completo requiere
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$$
tiempo y \(\Theta(\alpha^R)\) memoria para el grafo más dos vectores de conteo. Para el objetivo concreto \(T=20\), este enfoque directo de programación dinámica es lo bastante pequeño como para ejecutarse exactamente con aritmética entera ordinaria.
一次跳跃就是从一个七边形跳到与它共享边的相邻七边形。因此，这道题可以看成是在无限的七边形邻接图上计数；等价地说，就是在正则 \(\{7,3\}\) 七边形镶嵌的对偶图上计数。固定起点七边形 \(r\)。对每个 \(t\)，记 \(F(t)\) 为长度恰好为 \(t\)、从 \(r\) 出发并回到 \(r\) 的游走数。实现最终要计算的是 \(t=20\) 时的这个数量。
真正困难的地方不是“如何从邻居累加到下一步”这一条递推，而是如何只构造出无限图中真正会影响长度 \(t\) 回返游走的那一部分。三份实现都采用同一思路：围绕起点按距离一层层展开，识别每一圈里两种不同的七边形类型，然后只在这个有限球内做精确的邻接传播。
记 \(L_d\) 为与起点七边形 \(r\) 的图距离等于 \(d\) 的所有七边形集合。代码并不会表示整张无限镶嵌图，而是只构造某个半径 \(R\) 的有限球 \(L_0\cup L_1\cup\cdots\cup L_R\)，随后在这个有限球上精确统计回返游走。
外层边界被编码成一个循环表，表中的每个位置代表一个“尚未向外连接”的边。当前最外圈中的某个七边形，会在这张表里出现若干次，出现次数正好等于它还剩下多少条外向边没有接到下一圈。这是整个构造过程最关键的不变量。
如果边界表中相邻的两个条目来自不同的父七边形，那么下一层里就会生成一个同时接触这两个父七边形的“角点七边形”。如果某个条目没有在这样的交界处被配对，它就生成一个只连接到单个父七边形的“侧边七边形”。新的一圈生成之后，这一圈中的七边形还要按顺序连成一个环，因为它们围绕起点闭合成一整圈。
对 \(d\ge 1\)，设 \(S_d\) 为第 \(d\) 层中侧边七边形的数量，\(C_d\) 为角点七边形的数量，\(N_d=S_d+C_d\) 为这一层总大小。第一圈只有侧边七边形：
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
接下来分析一圈如何生成下一圈。循环边界上每一次“父节点发生切换”的位置都会生成恰好一个角点七边形，因此
$$C_{d+1}=N_d.$$
第 \(d\) 层中的一个侧边七边形会贡献 \(4\) 个外向槽位。其中两端各有一个槽位会在与相邻块的交界处被角点消耗掉，所以还剩 \(2\) 个槽位生成新的侧边七边形。一个角点七边形会贡献 \(3\) 个外向槽位，扣掉两端交界后只剩 \(1\) 个槽位。因此
$$S_{d+1}=2S_d+C_d.$$
把这两个关系合起来，就得到总层大小的一维递推：
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
初值为 \(N_1=7\)、\(N_2=21\)。如果记
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2},$$
那么还有闭式
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$$
实现本身并不需要显式使用这个闭式，但它很好地解释了为什么层大小是指数增长的，也就解释了后续时间和空间代价的增长速度。
这套构造的核心目标之一，就是保证所有已经完整展开的内部七边形都恰好有 \(7\) 个邻居。
一个侧边七边形有 \(1\) 个来自上一层的父邻居、同层环上的 \(2\) 个邻居，以及下一层中的 \(4\) 个外向邻居，所以它的度数是
$$1+2+4=7.$$
一个角点七边形有 \(2\) 个父邻居、同层的 \(2\) 个邻居，以及 \(3\) 个外向邻居，因此它的度数是
$$2+2+3=7.$$
起点七边形本身的度数也是 \(7\)，因为第一圈正好包含 \(7\) 个与它相邻的七边形。实现中的校验步骤正是在检查：凡是已经不在最外边界、也就是说已经完成扩展的七边形，它们的度数都必须等于 \(7\)。
设一条长度为 \(t\) 的闭合游走曾经到达第 \(d\) 层 \(L_d\)。那么它至少要走 \(d\) 步才能从 \(r\) 到达这一层，之后至少还要再走 \(d\) 步才能回到 \(r\)。所以必有
$$2d\le t.$$
这说明，长度为 \(t\) 的回返游走不可能访问比 \(\lfloor t/2\rfloor\) 更深的层。于是这里的截断并不是近似，而是严格正确的：半径 \(\lfloor t/2\rfloor\) 的有限球已经包含了一条长度 \(t\) 回返游走可能经过的全部七边形。
有限球构造完成后，计数部分就是标准的图论递推。令 \(w_t(v)\) 表示在已构造出的有限球中，从 \(r\) 出发、长度为 \(t\)、终点在七边形 \(v\) 的游走数，那么
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
初始条件为
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
题目需要的量就是
$$F(t)=w_t(r).$$
如果把这个有限球的邻接矩阵记为 \(A\)，把根对应的基向量记为 \(e_r\)，那么同样的关系也可以写成
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r.$$
三份实现都没有真的去做矩阵乘方，而是采用稀疏邻接表逐轮扫描；但从数学上看，这两种写法描述的是完全同一个线性算子。
从根七边形 \(r\) 开始。初始的循环边界是 \(7\) 个 \(r\) 的拷贝，每个拷贝对应一条尚未向外连接的边。由于相邻边界条目仍然来自同一个七边形，所以这时还不会形成角点七边形。因此第一圈就是
$$S_1=7,\qquad C_1=0.$$
接下来，第一圈中的每个七边形都会提供 \(4\) 个外向槽位，于是下一次的边界变成 \(7\) 个长度为 \(4\) 的连续块。块与块之间的 \(7\) 个交界恰好产生 \(7\) 个角点七边形。每个长度为 \(4\) 的块内部还剩下 \(2\) 个没有被交界消耗掉的槽位，因此每个块再生成 \(2\) 个侧边七边形。于是
$$C_2=7,\qquad S_2=14,\qquad N_2=21.$$
这个局部图形已经能解释前几个检验值。长度为 \(2\) 的回返共有 \(7\) 条，因为可以先走到任意一个邻居，再立刻走回根。长度为 \(3\) 的回返共有 \(14\) 条，因为第一步走到第一圈后，第二步可以走向该圈中与之相邻的两个七边形之一，第三步再回到根。实现还会继续检查 \(F(4)=119\)，然后才输出目标值 \(F(20)\)。
C++、Python 和 Java 三个实现都会先构造半径 \(\lfloor \max(t,4)/2\rfloor\) 的根球，这样既覆盖目标步数，也覆盖内置的短步数校验。它们维护循环边界中的开放边槽位，在不同父节点交界处生成角点七边形，在剩余槽位上生成侧边七边形，然后把新的一圈按顺序闭合成一个环。
一圈构造完成后，下一轮边界通过重复新生成的七边形来得到：侧边七边形重复 \(4\) 次，角点七边形重复 \(3\) 次，因为这正是它们留给更外层的开放边数。这样就能完全依靠组合结构推进构造，而不需要显式保存任何几何坐标。
图构造好以后，实现维护两个计数向量：当前步数下的终点分布，以及下一步的终点分布。对全部邻接表做一次扫描，就完成一次
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u)$$
的更新。重复扫描直到目标步数后，根节点对应的条目就是所求的闭合游走数。
同一个循环还会顺便检查 \(F(2)=7\)、\(F(3)=14\)、\(F(4)=119\)。其中 C++ 和 Java 版本把按顶点扫描的步骤并行化；Python 版本执行完全相同的算术，只是不并行。
设目标步数为 \(T\)，所需半径为 \(R=\lfloor T/2\rfloor\)。由于 \(N_d\) 按 \(\alpha=(3+\sqrt5)/2\) 的速度增长，因此半径 \(R\) 球中的七边形总数满足
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$$
除最外边界外，这张图基本上是 7 正则的，所以边数与点数同阶。构造有限球需要 \(\Theta(\alpha^R)\) 时间，一次邻接传播也需要 \(\Theta(\alpha^R)\) 时间。因此总时间复杂度为
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right),$$
空间复杂度为 \(\Theta(\alpha^R)\)，对应图结构加上两个游走计数向量。对本题实际目标 \(T=20\) 来说，这样的直接动态规划规模完全足够小，可以用普通整数精确完成。
Один прыжок переводит нас из одного семиугольника в соседний семиугольник. Поэтому задачу удобно рассматривать на бесконечном графе смежности семиугольников, то есть, эквивалентно, на двойственном графе регулярной мозаики \(\{7,3\}\). Зафиксируем стартовый семиугольник \(r\). Для каждого \(t\) обозначим через \(F(t)\) число маршрутов длины \(t\), которые начинаются в \(r\) и снова заканчиваются в \(r\). Реализации вычисляют эту величину для \(t=20\).
Сама рекурсия для подсчета маршрутов проста. Настоящая трудность в том, чтобы из бесконечного графа построить ровно ту конечную область, которая может повлиять на замкнутый маршрут длины \(t\). Решения делают это, расширяя слои вокруг \(r\), различая два естественных типа семиугольников в каждом кольце, а затем выполняя точную propagation по смежности внутри полученного конечного шара.
Пусть \(L_d\) - множество всех семиугольников на графовом расстоянии \(d\) от стартового семиугольника \(r\). Код не пытается хранить всю бесконечную мозаику. Вместо этого он строит шар \(L_0\cup L_1\cup\cdots\cup L_R\) для подходящего радиуса \(R\), а затем точно считает маршруты внутри этого шара.
Внешняя граница хранится как циклический список еще не использованных внешних сторон. Семиугольник текущего внешнего кольца появляется в этом списке столько раз, сколько у него остается незаполненных ребер, ведущих наружу. Это и есть главный инвариант построения.
Если два соседних элемента граничного списка различны, следующий семиугольник касается обоих соответствующих родителей, и возникает угловой семиугольник. Если элемент не участвует в таком переходе, он порождает боковой семиугольник, связанный только с одним родителем. После построения нового кольца соседние семиугольники этого кольца соединяются циклически, потому что кольцо замыкается вокруг центра.
Для \(d\ge 1\) обозначим через \(S_d\) число боковых семиугольников в слое \(L_d\), через \(C_d\) число угловых, а через \(N_d=S_d+C_d\) общий размер слоя. Первое кольцо содержит только боковые семиугольники:
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
Теперь посмотрим, как одно кольцо порождает следующее. Каждый переход между двумя соседними родителями на циклической границе создает ровно один угловой семиугольник, поэтому
$$C_{d+1}=N_d.$$
Боковой семиугольник в \(L_d\) дает четыре внешних слота. Два из них расходуются на угловые семиугольники по краям блока, так что остаются два боковых потомка. Угловой семиугольник дает три внешних слота; после двух граничных переходов остается один. Следовательно,
$$S_{d+1}=2S_d+C_d.$$
Объединяя эти формулы, получаем одномерную рекурсию для размеров слоев:
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
при начальных значениях \(N_1=7\) и \(N_2=21\). Если положить
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2},$$
то имеем замкнутую формулу
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$$
Код не пользуется этой формулой напрямую, но она ясно показывает экспоненциальный рост слоев и тем самым объясняет итоговый масштаб вычислений.
Построение специально устроено так, чтобы каждый уже завершенный внутренний семиугольник имел ровно семь соседей.
Боковой семиугольник имеет одного родителя в предыдущем слое, двух соседей в собственном кольце и четырех внешних соседей в следующем слое. Его степень равна
$$1+2+4=7.$$
Угловой семиугольник имеет двух родителей, двух соседей в том же кольце и трех внешних соседей. Его степень равна
$$2+2+3=7.$$
Стартовый семиугольник тоже имеет степень \(7\), потому что первое кольцо состоит ровно из семи соседних семиугольников. Проверки в реализациях контролируют этот инвариант для всех вершин, которые уже полностью расширены и не лежат на внешней границе.
Предположим, что замкнутый маршрут длины \(t\) достигает слоя \(L_d\). Чтобы попасть туда из \(r\), требуется как минимум \(d\) шагов, и как минимум еще \(d\) шагов нужно, чтобы вернуться обратно в \(r\). Значит, обязательно
$$2d\le t.$$
Следовательно, никакой маршрут возврата длины \(t\) не может заходить глубже, чем в слой \(L_{\lfloor t/2\rfloor}\). Здесь усечение является не приближением, а точным утверждением: шар радиуса \(\lfloor t/2\rfloor\) уже содержит все семиугольники, которые могут встретиться в замкнутом маршруте длины \(t\).
После построения нужного шара задача становится стандартной задачей теории графов. Пусть \(w_t(v)\) - число маршрутов длины \(t\) из \(r\) в семиугольник \(v\) внутри построенного шара. Тогда
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
с начальными условиями
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
Искомая величина есть просто
$$F(t)=w_t(r).$$
Если \(A\) - матрица смежности конечного шара, а \(e_r\) - базисный вектор в корне, то то же самое можно записать как
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r.$$
Реализации используют не явные степени матрицы, а разреженные списки смежности и повторяющиеся проходы по соседям; математически это один и тот же линейный оператор.
Начнем с корневого семиугольника \(r\). Начальная циклическая граница состоит из семи копий \(r\), по одной на каждую внешнюю сторону. Поскольку соседние элементы границы пока относятся к одному и тому же семиугольнику, угловой семиугольник здесь еще появиться не может. Значит, первое кольцо равно
$$S_1=7,\qquad C_1=0.$$
Далее каждый семиугольник первого кольца дает четыре граничных слота, так что следующая граница состоит из семи последовательных блоков длины \(4\). Семь границ между блоками создают ровно семь угловых семиугольников. Внутри каждого блока остаются два неиспользованных слота, поэтому каждый блок дополнительно создает два боковых семиугольника. Отсюда
$$C_2=7,\qquad S_2=14,\qquad N_2=21.$$
Эта картинка уже объясняет первые контрольные значения. Двухшаговых возвратов ровно \(7\): можно перейти в любого из семи соседей и сразу вернуться. Трехшаговых возвратов \(14\): после первого шага можно перейти к одному из двух соседних семиугольников в первом кольце, а затем вернуться в корень. Реализации дополнительно проверяют \(F(4)=119\), прежде чем переходить к целевому значению \(F(20)\).
Реализации на C++, Python и Java сначала строят корневой шар радиуса \(\lfloor \max(t,4)/2\rfloor\), чтобы охватить и целевое число шагов, и короткие встроенные проверки. Для этого они поддерживают циклическую границу свободных сторон, создают угловые семиугольники на переходах между разными родителями, создают боковые семиугольники на оставшихся слотах и затем замыкают новое кольцо в цикл.
После замыкания кольца следующая граница образуется повторением каждого нового семиугольника по числу оставшихся внешних ребер: \(4\) раза для бокового и \(3\) раза для углового. Благодаря этому достаточно чисто комбинаторной информации; никакие геометрические координаты не нужны.
Когда граф уже построен, реализация хранит два вектора: текущее распределение концов маршрутов и следующее. Один проход по спискам смежности реализует рекурсию \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\). После \(t\) таких проходов значение в корневой вершине и есть число искомых замкнутых маршрутов.
Тот же цикл одновременно проверяет известные значения \(F(2)=7\), \(F(3)=14\) и \(F(4)=119\). Версии на C++ и Java распараллеливают проход по вершинам; версия на Python выполняет ту же арифметику последовательно.
Пусть \(T\) - требуемое число шагов, а \(R=\lfloor T/2\rfloor\). Поскольку \(N_d\) растет как \(\alpha^d\), где \(\alpha=(3+\sqrt5)/2\), число семиугольников в шаре радиуса \(R\) удовлетворяет оценке
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$$
Вне внешней границы граф имеет степень \(7\), поэтому число ребер имеет тот же порядок, что и число вершин. Построение шара требует \(\Theta(\alpha^R)\) времени, и один шаг propagation по смежности стоит столько же. Полная вычислительная стоимость равна
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$$
по времени и \(\Theta(\alpha^R)\) по памяти для самого графа и двух счетчиков маршрутов. Для конкретной цели \(T=20\) этот прямой динамический подход достаточно мал, чтобы выполнять точный подсчет обычными целыми числами.
كل قفزة تنتقل من سباعي إلى سباعي مجاور له. لذلك يمكن فهم المسألة على أنها تعمل فوق الرسم البياني اللانهائي لمجاورات السباعيات، أو بصورة مكافئة فوق الرسم البياني المزدوج للتبليط المنتظم \(\{7,3\}\). نثبت سباعيًا ابتدائيًا \(r\). ولكل \(t\) نرمز بـ \(F(t)\) إلى عدد المسارات بطول \(t\) التي تبدأ من \(r\) وتعود إلى \(r\). التنفيذات تحسب هذه الكمية عند \(t=20\).
علاقة العد نفسها بسيطة، لكن الصعوبة الحقيقية هي بناء الجزء المنتهي من الرسم اللانهائي الذي يمكنه بالفعل التأثير في مسار عودة طوله \(t\). ولهذا تبني الحلول طبقات متراكزة حول \(r\)، وتفرّق بين نوعين هندسيين حقيقيين من السباعيات في كل حلقة، ثم تجري بعد ذلك نشرًا متكررًا عبر المجاورة داخل الكرة المنتهية الناتجة.
لتكن \(L_d\) مجموعة جميع السباعيات التي تبعد مسافة بيانية مقدارها \(d\) عن السباعي الابتدائي \(r\). لا يحاول الكود تمثيل التبليط اللانهائي كله. بدلًا من ذلك، يبني الكرة المنتهية \(L_0\cup L_1\cup\cdots\cup L_R\) لنصف قطر مختار بعناية \(R\)، ثم يحسب داخلها عدد المسارات على نحو دقيق.
يُمثَّل الحد الخارجي على شكل قائمة دورية من الأضلاع الخارجية التي لم تُستعمل بعد. والسباعي الموجود في الحلقة الخارجية الحالية يظهر في هذه القائمة بعدد يساوي عدد أضلاعه الخارجية التي لم تُوصَل بعد بالحلقة التالية. هذه هي اللازمة الأساسية التي يحملها البناء كله.
إذا كان عنصران متجاوران في قائمة الحد مختلفين، فإن السباعي التالي يلامس الأبويْن الموافقين معًا، وعندها يتولد سباعي زاوية. أما إذا بقي عنصر من دون مثل هذا الاقتران عبر انتقال حدّي، فإنه يولد سباعي جانب متصلًا بأب واحد فقط. وبعد إنشاء الحلقة الجديدة، تُوصَل السباعيات المتتالية فيها على نحو دوري لأن الحلقة تنغلق حول نقطة البدء.
لـ \(d\ge 1\)، لنرمز بـ \(S_d\) إلى عدد سباعيات الجانب في الطبقة \(L_d\)، وبـ \(C_d\) إلى عدد سباعيات الزاوية، وبـ \(N_d=S_d+C_d\) إلى الحجم الكلي للطبقة. الحلقة الأولى تحتوي على سباعيات جانب فقط:
$$S_1=7,\qquad C_1=0,\qquad N_1=7.$$
والآن نحلل كيف تنشئ حلقةٌ ما الحلقةَ التالية. كل انتقال بين أبوين متجاورين على الحد الدوري يولد بالضبط سباعي زاوية واحدًا، ومن ثم
$$C_{d+1}=N_d.$$
سباعي الجانب في \(L_d\) يساهم بأربع خانات حدية خارجية. تُستهلك خانتان منها عند زاويتي الكتلة، فيبقى خانتان تولدان ابنين جانبيين. أما سباعي الزاوية فيعطي ثلاث خانات خارجية، وبعد استخدام الانتقالين الطرفيين تبقى خانة واحدة. لذلك نحصل على
$$S_{d+1}=2S_d+C_d.$$
وبدمج العلاقتين نحصل على علاقة أحادية لأحجام الطبقات:
$$N_{d+1}=3N_d-N_{d-1}\qquad (d\ge 2),$$
مع القيم الابتدائية \(N_1=7\) و\(N_2=21\). وإذا وضعنا
$$\alpha=\frac{3+\sqrt5}{2},\qquad \beta=\frac{3-\sqrt5}{2},$$
فإن لدينا الصيغة المغلقة
$$N_d=\frac{7}{\sqrt5}\left(\alpha^d-\beta^d\right).$$
التنفيذ لا يحتاج إلى هذه الصيغة مباشرة، لكنها تفسر بوضوح لماذا تنمو الطبقات نموًا أسيًا، وبالتالي لماذا يتصرف زمن التنفيذ بهذه الصورة.
صُمم البناء بحيث يكون لكل سباعي داخلي اكتمل تمديده سبعة جيران تمامًا.
سباعي الجانب له أب واحد في الطبقة السابقة، وجاران في الحلقة نفسها، وأربعة جيران خارجيون في الطبقة التالية، ولذلك درجته
$$1+2+4=7.$$
أما سباعي الزاوية فله أبوان، وجاران في الحلقة نفسها، وثلاثة جيران خارجيون، وبالتالي درجته
$$2+2+3=7.$$
والسباعي الابتدائي نفسه درجته \(7\) لأن الحلقة الأولى تحتوي على سبعة سباعيات مجاورة له. وتتحقق خطوات التحقق في التنفيذ من هذه اللازمة لكل سباعي لم يعد على الحد الخارجي، أي لكل سباعي اكتمل توسيعه بالكامل.
إذا وصل مسار مغلق طوله \(t\) إلى الطبقة \(L_d\)، فهو يحتاج إلى ما لا يقل عن \(d\) قفزات للخروج من \(r\) إلى تلك الطبقة، وإلى ما لا يقل عن \(d\) قفزات أخرى للعودة من جديد إلى \(r\). لذلك لا بد أن
$$2d\le t.$$
وبالتالي لا يمكن لمسار عودة طوله \(t\) أن يزور طبقة أعمق من \(L_{\lfloor t/2\rfloor}\). هذا يعني أن القطع هنا دقيق تمامًا وليس تقريبًا: الكرة ذات نصف القطر \(\lfloor t/2\rfloor\) تحتوي سلفًا على كل سباعي يمكن أن يظهر في مسار عودة طوله \(t\).
بعد بناء الكرة اللازمة، يصبح جزء العد مسألة معيارية في نظرية الرسوم البيانية. ليكن \(w_t(v)\) عدد المسارات بطول \(t\) من \(r\) إلى سباعي \(v\) داخل الكرة المبنية. عندئذ
$$w_{t+1}(v)=\sum_{u\sim v} w_t(u),$$
مع الشروط الابتدائية
$$w_0(r)=1,\qquad w_0(v)=0\quad (v\ne r).$$
إذن الكمية المطلوبة هي ببساطة
$$F(t)=w_t(r).$$
وإذا كانت \(A\) مصفوفة المجاورة للكرة المنتهية و\(e_r\) متجه الأساس عند الجذر، فإن الكلام نفسه يكتب على الصورة
$$w_t=A^t e_r,\qquad F(t)=e_r^{\mathsf T}A^t e_r.$$
التنفيذات لا تحسب قوى المصفوفات صراحة، بل تستخدم قوائم مجاورة sparse وتمريرات متكررة فوقها، لكن التفسير الرياضي واحد تمامًا.
نبدأ بالسباعي الجذر \(r\). الحد الدوري الابتدائي يتكون من سبع نسخ من \(r\)، واحدة لكل ضلع خارجي. وبما أن العناصر المتجاورة في هذا الحد ما تزال تشير إلى السباعي نفسه، فلا يمكن أن يتكوّن سباعي زاوية بعد. لذلك تكون الحلقة الأولى ببساطة
$$S_1=7,\qquad C_1=0.$$
بعد ذلك يساهم كل سباعي في الحلقة الأولى بأربع خانات حدية، ومن ثم يصبح الحد التالي مؤلفًا من سبع كتل متتالية طول كل منها \(4\). الفواصل بين هذه الكتل السبع تُنتج بالضبط سبعة سباعيات زاوية. وداخل كل كتلة تبقى خانتان غير مقترنتين، فتولد كل كتلة أيضًا سباعيي جانب. لذلك
$$C_2=7,\qquad S_2=14,\qquad N_2=21.$$
هذه الصورة تفسر أول قيم التحقق مباشرة. فهناك \(7\) مسارات عودة بطول \(2\)، لأنك تستطيع الذهاب إلى أي جار من الجيران السبعة ثم الرجوع فورًا. وهناك \(14\) مسار عودة بطول \(3\)، لأنك بعد القفزة الأولى تستطيع الانتقال إلى أحد السباعيين المجاورين في الحلقة الأولى ثم العودة إلى الجذر. كما تتحقق التنفيذات أيضًا من القيمة \(F(4)=119\) قبل الانتقال إلى الهدف \(F(20)\).
تبدأ تنفيذات C++ وPython وJava ببناء الكرة الجذرية ذات نصف القطر \(\lfloor \max(t,4)/2\rfloor\)، وبذلك تغطي عدد الخطوات المطلوب كما تغطي نقاط التحقق القصيرة المدمجة. وهي تحافظ على الحد الدوري للأضلاع المفتوحة، وتولد سباعيات الزاوية عند الانتقالات بين آباء مختلفين، وتولد سباعيات الجانب على الخانات المتبقية، ثم تغلق الحلقة الجديدة على شكل دورة.
وبعد إغلاق الحلقة، يُنشأ الحد التالي بتكرار كل سباعي جديد بحسب درجته الخارجية المتبقية: \(4\) مرات لسباعي الجانب و\(3\) مرات لسباعي الزاوية. وهذا التمثيل المضغوط يحمل بالضبط المعلومات اللازمة لبناء الحلقة التالية من غير أي حاجة إلى إحداثيات هندسية.
بعد اكتمال بناء الرسم البياني، يحتفظ التنفيذ بمتجهين للعد: التوزيع الحالي لنهايات المسارات والتوزيع التالي. ويمثل تمرير واحد فوق قوائم المجاورة تطبيق العلاقة \(w_{t+1}(v)=\sum_{u\sim v} w_t(u)\). وبعد تكرار هذا التمرير حتى عدد الخطوات المطلوب، تكون قيمة الجذر هي عدد المسارات المغلقة المطلوبة.
وتتحقق الحلقة نفسها أيضًا من القيم المعروفة \(F(2)=7\) و\(F(3)=14\) و\(F(4)=119\). وتقوم نسختا C++ وJava بموازاة المسح على مستوى الرؤوس، بينما تنفذ نسخة Python الحساب نفسه على نحو تسلسلي.
لتكن \(T\) هي عدد القفزات المطلوب، ولتكن \(R=\lfloor T/2\rfloor\). بما أن \(N_d\) ينمو مثل \(\alpha^d\) حيث \(\alpha=(3+\sqrt5)/2\)، فإن عدد السباعيات داخل الكرة ذات نصف القطر \(R\) يحقق
$$|L_0\cup\cdots\cup L_R|=\Theta(\alpha^R).$$
وخارج الحد الأقصى يكون الرسم منتظم الدرجة \(7\) تقريبًا، لذا فإن عدد الأضلاع من نفس رتبة عدد الرؤوس. بناء الكرة يكلف \(\Theta(\alpha^R)\)، وخطوة نشر واحدة عبر المجاورة تكلف المقدار نفسه. وعليه فإن الكلفة الكلية هي
$$\Theta(T\alpha^R)=\Theta\!\left(T\alpha^{T/2}\right)$$
زمنًا، و\(\Theta(\alpha^R)\) ذاكرةً للرسم البياني إضافة إلى متجهي العد. وبالنسبة إلى الهدف الفعلي \(T=20\)، فإن هذا الأسلوب المباشر من البرمجة الديناميكية صغير بما يكفي ليعمل بدقة باستخدام الحساب الصحيح العادي.