Let \(O_{a,b}\) be the equal-angled octagon whose side lengths, read cyclically, are \(a,b,a,b,a,b,a,b\). We must compute \(t(O_{4,2})\), where \(t(O_{a,b})\) counts tilings of this octagon by unit-edge rhombi and unit squares. The implementations do not use a closed formula; instead they count tilings recursively by describing every remaining subregion only through its boundary.
The key observation is that every tile edge lies in one of eight directions separated by \(45^\circ\). After scaling coordinates by \(2\), those directions become
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $$
Every coordinate can therefore be written as \(r+s\sqrt{2}\), which matches the algebraic representation used by the implementations.
The initial octagon is encoded by the cyclic word
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $$
More generally, any remaining subregion is represented by the cyclic sequence of its unit boundary steps. If \(w\) is such a word, let \(T(w)\) denote the number of tilings of the region enclosed by \(w\).
To avoid double counting, the recursion always selects the lowest boundary vertex, breaking ties by taking the leftmost one. Let that vertex be \(p\), and let the outgoing boundary edge from \(p\) have direction \(d\). In any valid tiling, exactly one tile uses that exposed boundary edge, so the recursion only needs to enumerate the possible tiles attached there.
Let \(u\) be the unit vector in direction \(d\). The second side of the tile must turn into the interior by \(45^\circ\), \(90^\circ\), or \(135^\circ\). Therefore the only candidates use the unit vector in direction \(d+\delta \pmod 8\) with \(\delta\in\{1,2,3\}\), and their corners are
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $$
The case \(\delta=2\) gives a square; the cases \(\delta=1\) and \(\delta=3\) give the two rhombus orientations. No other convex unit-edge square or rhombus can share the chosen boundary edge and still lie inside the region.
A candidate tile is accepted only when its two interior corners lie inside or on the current polygon and none of its four edges crosses an existing boundary edge, except for shared endpoints or the shared boundary edge itself. Cross products, segment tests, and vertex coordinates all stay inside the algebraic lattice generated by \(1\) and \(\sqrt{2}\), so the geometric tests follow the same exact combinatorial geometry as the tiles.
Write \(E(P)\) for the set of unit edges on the current boundary and \(E(Q)\) for the boundary of the chosen tile. When the tile is removed from the remaining region, shared edges disappear and newly exposed tile edges appear, so
$$ E(P\setminus Q)=E(P)\triangle E(Q), $$
where \(\triangle\) denotes symmetric difference. The resulting edge set is rebuilt into one or more counterclockwise boundary cycles by a deterministic walk: start from the lowest-leftmost unused edge and always take the smallest left turn. If the region splits into cycles \(w_1,\dots,w_r\), then the subproblems are independent and
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $$
with the empty boundary contributing \(1\).
For \(a=b=1\), the initial boundary word is
$$ w_{1,1}=(0,1,2,3,4,5,6,7). $$
The canonical starting vertex is the lowest-leftmost corner, and its outgoing boundary edge points east. The recursion therefore tests exactly three first tiles: one rhombus turning northeast, one square turning north, and one rhombus turning northwest. Summing all valid descendants gives
$$ t(O_{1,1})=8, $$
which matches one of the small checkpoint values used to validate the recurrence.
The C++, Python, and Java implementations all follow the same recurrence. They build the initial boundary word for \(O_{4,2}\), expand it into vertices, choose the canonical lowest-leftmost start, try up to three candidate tiles, reject candidates that fail point-in-polygon or segment-intersection tests, and update the boundary through symmetric difference of unit edges. Every reconstructed cycle is oriented counterclockwise before memo lookup so that equivalent subregions share the same cache entry. The count is stored in arbitrary-precision integers, and the C++ implementation also checks small benchmark values such as \(t(O_{1,1})=8\), \(t(O_{2,1})=76\), and \(t(O_{3,2})=456572\).
If a state has boundary length \(m\), then building its vertices, scanning for the canonical start, testing the three candidate tiles, checking segment intersections, and reconstructing the next boundary cycles each take linear time in \(m\). Thus one visited state costs \(O(m)\) time and \(O(m)\) temporary memory. The full search is still exponential in the worst case because the number of distinct boundary states can grow exponentially, but memoization, immediate geometric rejection, and decomposition into independent cycles reduce the practical search space sharply.
Sei \(O_{a,b}\) das gleichwinklige Achteck mit zyklischer Seitenfolge \(a,b,a,b,a,b,a,b\). Gesucht ist \(t(O_{4,2})\), wobei \(t(O_{a,b})\) die Anzahl der Pflasterungen dieses Achtecks durch Einheitsrauten und Einheitsquadrate bezeichnet. Die Implementierungen benutzen keine geschlossene Formel, sondern zählen rekursiv und beschreiben jede verbleibende Teilregion nur durch ihren Rand.
Die zentrale Beobachtung ist, dass jede Kante einer Kachel in einer von acht Richtungen liegt, die jeweils um \(45^\circ\) versetzt sind. Nach einer Skalierung der Koordinaten um den Faktor \(2\) lauten diese Richtungen
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $$
Jede Koordinate hat also die Form \(r+s\sqrt{2}\), genau wie in der algebraischen Darstellung der Implementierungen.
Das Anfangsachteck wird durch das zyklische Wort
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}) $$
kodiert. Allgemeiner wird jede verbleibende Teilregion durch die zyklische Folge ihrer Einheitsrandkanten beschrieben. Für ein solches Wort \(w\) bezeichne \(T(w)\) die Anzahl der Pflasterungen der von \(w\) eingeschlossenen Region.
Um Mehrfachzählungen zu vermeiden, wählt die Rekursion immer den geometrisch tiefsten Randpunkt und bei Gleichstand den linken davon. Dieser Punkt sei \(p\), und die ausgehende Randkante habe Richtung \(d\). In jeder gültigen Pflasterung benutzt genau eine Kachel diese freiliegende Randkante, daher genügt es, nur die dort möglichen Kacheln zu betrachten.
Sei \(u\) der Einheitsvektor in Richtung \(d\). Die zweite Seite der Kachel muss um \(45^\circ\), \(90^\circ\) oder \(135^\circ\) in das Innere drehen. Daher kommen nur Einheitsvektoren in Richtung \(d+\delta \pmod 8\) mit \(\delta\in\{1,2,3\}\) in Frage, und die vier Ecken lauten
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $$
Der Fall \(\delta=2\) liefert ein Quadrat, die Fälle \(\delta=1\) und \(\delta=3\) die beiden Rautenorientierungen. Keine andere konvexe Einheitsraute und kein anderes Einheitsquadrat kann dieselbe Randkante teilen und gleichzeitig im Inneren der Region bleiben.
Eine Kandidatenkachel wird nur akzeptiert, wenn ihre beiden inneren Ecken im aktuellen Polygon liegen oder auf dessen Rand liegen und keine ihrer vier Kanten eine vorhandene Randkante schneidet, außer an gemeinsamen Endpunkten oder entlang der geteilten Randkante selbst. Kreuzprodukte, Streckentests und Eckkoordinaten bleiben alle in der algebraischen Struktur \(r+s\sqrt{2}\), sodass die Geometrie exakt an das zugrunde liegende Acht-Richtungs-Gitter angepasst bleibt.
Bezeichne \(E(P)\) als Menge der Einheitskanten auf dem aktuellen Rand und \(E(Q)\) als Rand der gewählten Kachel. Entfernt man diese Kachel aus der verbleibenden Region, verschwinden gemeinsame Kanten und neu freigelegte Kanten der Kachel erscheinen, also
$$ E(P\setminus Q)=E(P)\triangle E(Q), $$
wobei \(\triangle\) die symmetrische Differenz bezeichnet. Aus der entstehenden Kantenmenge werden dann durch einen deterministischen Umlauf eine oder mehrere Randzyklen gegen den Uhrzeigersinn rekonstruiert: Man startet bei der tiefsten linken noch unbenutzten Kante und nimmt stets die kleinste Linksdrehung. Zerfällt die Region in Zyklen \(w_1,\dots,w_r\), so sind die Teilprobleme unabhängig und
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $$
wobei der leere Rand den Beitrag \(1\) liefert.
Für \(a=b=1\) ist das Anfangsrandwort
$$ w_{1,1}=(0,1,2,3,4,5,6,7). $$
Der kanonische Startpunkt ist die tiefste linke Ecke, und die ausgehende Randkante zeigt nach Osten. Die Rekursion prüft daher genau drei erste Kacheln: eine Raute mit Drehung nach Nordosten, ein Quadrat mit Drehung nach Norden und eine Raute mit Drehung nach Nordwesten. Die Summe aller gültigen Nachfolger ergibt
$$ t(O_{1,1})=8, $$
genau einen der kleinen Kontrollwerte der Rekursion.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Rekursion. Sie erzeugen zunächst das Anfangsrandwort für \(O_{4,2}\), wandeln es in Eckpunkte um, wählen den kanonischen tiefsten linken Start, testen bis zu drei Kandidatenkacheln, verwerfen Kandidaten mit fehlgeschlagenem Punkt-im-Polygon- oder Streckenschnitt-Test und aktualisieren den Rand über die symmetrische Differenz der Einheitskanten. Jeder rekonstruierte Zyklus wird vor dem Memo-Lookup gegen den Uhrzeigersinn orientiert, damit äquivalente Teilregionen denselben Cache-Schlüssel besitzen. Gezählt wird mit Ganzzahlen beliebiger Größe, und die C++-Implementierung prüft zusätzlich kleine Vergleichswerte wie \(t(O_{1,1})=8\), \(t(O_{2,1})=76\) und \(t(O_{3,2})=456572\).
Hat ein Zustand Randlänge \(m\), dann benötigen das Aufbauen der Eckpunkte, das Suchen des kanonischen Starts, das Testen der drei Kandidatenkacheln, die Schnittprüfungen und die Rekonstruktion der nächsten Randzyklen jeweils lineare Zeit in \(m\). Ein besuchter Zustand kostet also \(O(m)\) Zeit und \(O(m)\) temporären Speicher. Die Gesamtsuche bleibt im Worst Case exponentiell, weil die Zahl verschiedener Randzustände exponentiell wachsen kann; Memoisierung, sofortiges Verwerfen geometrisch ungültiger Kandidaten und die Zerlegung in unabhängige Zyklen verkleinern den praktischen Suchraum jedoch deutlich.
\(O_{a,b}\), kenar uzunlukları çevre boyunca \(a,b,a,b,a,b,a,b\) biçiminde sıralanan eş açılı sekizgendir. Hesaplanması istenen değer \(t(O_{4,2})\)'dir; burada \(t(O_{a,b})\), bu sekizgenin birim kenarlı eşkenar dörtgenler ve karelerle döşenme sayısını ifade eder. Uygulamalar kapalı bir formül kullanmaz; bunun yerine her kalan alt bölgeyi yalnızca sınırı üzerinden tanımlayan özyinelemeli bir sayım yapar.
Ana gözlem şudur: Her karo kenarı, birbirinden \(45^\circ\) ayrılan sekiz yönün birinde yer alır. Koordinatlar \(2\) ile ölçeklenince bu yönler
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}) $$
olur. Böylece her koordinat \(r+s\sqrt{2}\) biçiminde yazılabilir; bu da uygulamaların kullandığı cebirsel gösterimdir.
Başlangıç sekizgeni şu çevrimsel sözcükle kodlanır:
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $$
Daha genel olarak, kalan her alt bölge birim sınır adımlarının çevrimsel dizisiyle temsil edilir. Böyle bir sözcük \(w\) için \(T(w)\), \(w\)'nin çevrelediği bölgenin döşenme sayısı olsun.
Çifte sayımı önlemek için özyineleme her zaman geometrik olarak en aşağıdaki sınır köşesini, eşitlik varsa en soldakini seçer. Bu köşe \(p\), bu köşeden çıkan sınır kenarının yönü de \(d\) olsun. Geçerli her döşemede bu açık sınır kenarını kullanan tam bir karo vardır; dolayısıyla yalnızca burada yerleşebilecek olası karoları saymak yeterlidir.
\(u\), \(d\) yönündeki birim vektör olsun. Karonun ikinci kenarı içeri doğru \(45^\circ\), \(90^\circ\) ya da \(135^\circ\) dönmelidir. Bu yüzden yalnızca \(d+\delta \pmod 8\) yönündeki birim vektör kullanılabilir; burada \(\delta\in\{1,2,3\}\). Dört köşe de
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v $$
olur. \(\delta=2\) durumu bir kare verir; \(\delta=1\) ve \(\delta=3\) ise iki farklı eşkenar dörtgen yönelimidir. Seçilen sınır kenarını paylaşan ve yine de bölgenin içinde kalan başka bir dışbükey birim kenarlı kare ya da eşkenar dörtgen yoktur.
Bir aday karo ancak iki iç köşesi mevcut çokgenin içinde ya da sınırında ise ve dört kenarından hiçbiri, ortak uç noktalar veya zaten paylaşılan sınır kenarı dışında, mevcut bir sınır kenarıyla kesişmiyorsa kabul edilir. Çapraz çarpımlar, doğru parçası testleri ve köşe koordinatları hep \(r+s\sqrt{2}\) yapısında kaldığı için geometrik kontroller karoların yaşadığı sekiz yönlü kafesle tam uyumludur.
\(E(P)\) mevcut sınırdaki birim kenar kümesi, \(E(Q)\) ise seçilen karonun sınırı olsun. Karo kalan bölgeden çıkarılınca ortak kenarlar yok olur, yeni açığa çıkan karo kenarları ise sınıra eklenir; dolayısıyla
$$ E(P\setminus Q)=E(P)\triangle E(Q) $$
elde edilir; burada \(\triangle\) simetrik farktır. Oluşan kenar kümesi daha sonra belirlenimci bir yürüyüşle bir ya da daha fazla saat yönünün tersine sınır döngüsüne çevrilir: En aşağıdaki en soldaki kullanılmamış kenardan başlanır ve her adımda en küçük sol dönüş alınır. Bölge \(w_1,\dots,w_r\) döngülerine ayrışıyorsa alt problemler bağımsızdır ve
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i) $$
olur. Boş sınırın katkısı \(1\)'dir.
\(a=b=1\) için başlangıç sınır sözcüğü
$$ w_{1,1}=(0,1,2,3,4,5,6,7) $$
şeklindedir. Kanonik başlangıç noktası en aşağıdaki en soldaki köşedir ve çıkan sınır kenarı doğuya gider. Bu yüzden özyineleme tam üç ilk karo dener: kuzeydoğuya dönen bir eşkenar dörtgen, kuzeye dönen bir kare ve kuzeybatıya dönen bir eşkenar dörtgen. Geçerli bütün alt dalların toplamı
$$ t(O_{1,1})=8 $$
sonucunu verir; bu da özyinelemenin küçük doğrulama değerlerinden biridir.
C++, Python ve Java uygulamalarının üçü de aynı özyinelemeyi kullanır. Önce \(O_{4,2}\) için başlangıç sınır sözcüğü kurulur, bu sözcük köşelere açılır, kanonik en alt-sol başlangıç seçilir, en fazla üç aday karo denenir, nokta-çokgen içinde testi veya doğru parçası kesişim testi başarısız olan adaylar atılır ve sınır birim kenarların simetrik farkı ile güncellenir. Yeniden oluşturulan her döngü, eşdeğer alt bölgelerin aynı önbellek anahtarını paylaşması için saat yönünün tersine çevrilir. Sayım keyfi büyüklükte tamsayılarla tutulur; ayrıca C++ uygulaması \(t(O_{1,1})=8\), \(t(O_{2,1})=76\) ve \(t(O_{3,2})=456572\) gibi küçük karşılaştırma değerlerini de sınar.
Bir durumun sınır uzunluğu \(m\) ise köşeleri kurmak, kanonik başlangıcı bulmak, üç aday karoyu denemek, kesişim kontrollerini yapmak ve sonraki sınır döngülerini çıkarmak \(m\) doğrusal zaman alır. Dolayısıyla ziyaret edilen tek bir durum \(O(m)\) zaman ve \(O(m)\) geçici bellek gerektirir. Toplam arama en kötü durumda yine üstel kalır; çünkü farklı sınır durumlarının sayısı üstel büyüyebilir. Buna rağmen memoization, erken geometrik reddetme ve bağımsız döngülere ayrışma pratik arama uzayını ciddi biçimde küçültür.
Sea \(O_{a,b}\) el octógono equiangular cuyas longitudes de lado, recorridas cíclicamente, son \(a,b,a,b,a,b,a,b\). Debemos calcular \(t(O_{4,2})\), donde \(t(O_{a,b})\) cuenta las teselaciones de este octógono con rombos de arista unitaria y cuadrados de arista unitaria. Las implementaciones no usan una fórmula cerrada; cuentan las teselaciones de forma recursiva describiendo cada subregión restante solo por su frontera.
La observación clave es que toda arista de una pieza está en una de ocho direcciones separadas por \(45^\circ\). Si se escalan las coordenadas por \(2\), esas direcciones pasan a ser
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $$
Así, toda coordenada puede escribirse como \(r+s\sqrt{2}\), exactamente la estructura algebraica usada por las implementaciones.
El octógono inicial se codifica mediante la palabra cíclica
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $$
Más generalmente, cualquier subregión restante queda representada por la secuencia cíclica de sus pasos de frontera unitarios. Si \(w\) es una de esas palabras, sea \(T(w)\) el número de teselaciones de la región encerrada por \(w\).
Para evitar contar dos veces la misma teselación, la recursión siempre elige el vértice de frontera más bajo y, en caso de empate, el más a la izquierda. Sea ese punto \(p\), y sea \(d\) la dirección de la arista saliente desde \(p\). En toda teselación válida existe exactamente una pieza que usa esa arista expuesta, de modo que basta enumerar las piezas posibles apoyadas allí.
Sea \(u\) el vector unitario en dirección \(d\). El segundo lado de la pieza debe girar hacia el interior \(45^\circ\), \(90^\circ\) o \(135^\circ\). Por tanto, solo se puede usar el vector unitario en dirección \(d+\delta \pmod 8\) con \(\delta\in\{1,2,3\}\), y los cuatro vértices son
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $$
El caso \(\delta=2\) produce un cuadrado; los casos \(\delta=1\) y \(\delta=3\) producen las dos orientaciones del rombo. No existe otro cuadrado o rombo convexo de arista unitaria que comparta la arista elegida y permanezca dentro de la región.
Una pieza candidata se acepta solo si sus dos vértices interiores quedan dentro o sobre el polígono actual y ninguna de sus cuatro aristas cruza una arista ya presente en la frontera, salvo en extremos compartidos o a lo largo de la propia arista de frontera compartida. Productos vectoriales, pruebas de segmentos y coordenadas de vértices permanecen en la estructura algebraica \(r+s\sqrt{2}\), así que las comprobaciones geométricas siguen exactamente la misma rejilla de ocho direcciones que usan las piezas.
Sea \(E(P)\) el conjunto de aristas unitarias de la frontera actual y \(E(Q)\) la frontera de la pieza elegida. Al retirar esa pieza de la región restante, las aristas compartidas desaparecen y aparecen las aristas de la pieza que quedan expuestas, por lo que
$$ E(P\setminus Q)=E(P)\triangle E(Q), $$
donde \(\triangle\) denota diferencia simétrica. El conjunto resultante de aristas se reconstruye después en uno o varios ciclos de frontera en sentido antihorario mediante un recorrido determinista: se empieza por la arista no usada más baja e izquierda y siempre se toma el menor giro a la izquierda. Si la región se divide en ciclos \(w_1,\dots,w_r\), los subproblemas son independientes y
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $$
tomando la frontera vacía con contribución \(1\).
Cuando \(a=b=1\), la palabra de frontera inicial es
$$ w_{1,1}=(0,1,2,3,4,5,6,7). $$
El vértice inicial canónico es la esquina más baja y más a la izquierda, y su arista saliente apunta hacia el este. La recursión prueba entonces exactamente tres primeras piezas: un rombo que gira al noreste, un cuadrado que gira al norte y un rombo que gira al noroeste. Sumando todos los descendientes válidos se obtiene
$$ t(O_{1,1})=8, $$
que coincide con uno de los valores pequeños de comprobación usados para validar la recurrencia.
Las implementaciones en C++, Python y Java siguen la misma recurrencia. Construyen la palabra de frontera inicial para \(O_{4,2}\), la expanden a vértices, eligen el inicio canónico más bajo y más a la izquierda, prueban hasta tres piezas candidatas, rechazan las que fallan las pruebas de punto en polígono o de intersección de segmentos y actualizan la frontera mediante la diferencia simétrica de aristas unitarias. Cada ciclo reconstruido se orienta en sentido antihorario antes de consultar la memoización para que subregiones equivalentes compartan la misma entrada de caché. El conteo se mantiene en enteros de precisión arbitraria, y la implementación en C++ además verifica valores pequeños como \(t(O_{1,1})=8\), \(t(O_{2,1})=76\) y \(t(O_{3,2})=456572\).
Si un estado tiene longitud de frontera \(m\), entonces construir sus vértices, buscar el inicio canónico, probar las tres piezas candidatas, comprobar intersecciones y reconstruir los siguientes ciclos de frontera cuesta tiempo lineal en \(m\). Por tanto, un estado visitado requiere \(O(m)\) tiempo y \(O(m)\) memoria temporal. La búsqueda completa sigue siendo exponencial en el peor caso porque el número de estados de frontera distintos puede crecer exponencialmente, aunque la memoización, el descarte geométrico temprano y la descomposición en ciclos independientes reducen mucho el espacio de búsqueda en la práctica.
设 \(O_{a,b}\) 为一个等角八边形，其边长沿边界按 \(a,b,a,b,a,b,a,b\) 交替出现。题目要求计算 \(t(O_{4,2})\)，其中 \(t(O_{a,b})\) 表示用单位边长的菱形和单位边长的正方形铺满该八边形的方案数。这里的实现并不是先推出一个闭式公式，而是把每个剩余区域都压缩成“边界状态”，然后用递归和记忆化来计数。
最重要的几何事实是：所有铺砖边都落在相隔 \(45^\circ\) 的八个方向上。把坐标整体放大 \(2\) 倍之后，这八个方向可以写成
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $$
因此每个坐标都能写成 \(r+s\sqrt{2}\) 的形式，这正是实现中使用的代数表示方式。这样做的好处是，边界顶点、向量差和叉积都始终停留在同一套代数结构里，不需要把几何对象近似成普通浮点坐标后再反复累积误差。
初始八边形被编码成下面这个循环词：
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $$
这里的数字只表示方向，不表示长度；每出现一次就代表一条单位边。更一般地，递归过程中得到的任何剩余子区域，也都只用它的单位边界步序列来表示。如果某个状态的边界词是 \(w\)，就记 \(T(w)\) 为它所围成区域的铺法数。
为了保证同一份铺法不会从不同入口被重复统计，递归总是先找边界上“最低”的顶点；如果有多个，再取其中最靠左的那个。记这个顶点为 \(p\)，记从 \(p\) 出发的边界边方向为 \(d\)。在任何一组合法铺法中，都会有且仅有一块砖覆盖这条已经暴露在边界上的单位边，所以只要枚举“贴着这条边放置”的砖即可，不需要在整块区域里盲目尝试。
设 \(u\) 是方向 \(d\) 上的单位向量。因为砖块必须沿着八方向网格摆放，而且共享的那条边已经固定，所以第二条边只能向区域内部转 \(45^\circ\)、\(90^\circ\) 或 \(135^\circ\)。也就是说，只需要考虑方向 \(d+\delta \pmod 8\) 上的单位向量 \(v\)，其中 \(\delta\in\{1,2,3\}\)。对应的四个顶点就是
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $$
当 \(\delta=2\) 时得到的是正方形；当 \(\delta=1\) 或 \(\delta=3\) 时得到的是两种不同朝向的菱形。除了这三种情形，不存在其他仍然是凸的、边长为 \(1\) 且能共享这条边界边的正方形或菱形。
候选砖块并不是构造出来就一定可用。实现会检查两个关键条件。第一，砖块的另外两个顶点必须位于当前多边形内部或者恰好落在边界上，否则这块砖已经伸到区域外面去了。第二，砖块的四条边不能与现有边界发生非法相交；允许的接触只有公共端点，以及那条本来就与当前边界重合的共享边。因为顶点坐标和叉积都保持在 \(r+s\sqrt{2}\) 这类数里，所以线段相交、共线和点在线段上的判断都和八方向网格完全兼容。
记 \(E(P)\) 为当前区域边界上的单位边集合，记 \(E(Q)\) 为选中砖块的边界集合。把这块砖从剩余区域里“切掉”之后，原先重合的边会消失，而砖块另外暴露出来的边会成为新的边界，因此新边界满足
$$ E(P\setminus Q)=E(P)\triangle E(Q), $$
其中 \(\triangle\) 表示集合的对称差。接下来，程序从这组无向单位边重新恢复出一个或多个逆时针边界环。恢复方式也是确定性的：从尚未使用的“最低且最左”的边开始，每一步都选择最小的左转角。这样得到的边界词具有稳定的规范形式，适合直接作为记忆化键值。如果新的区域分裂成 \(w_1,\dots,w_r\) 这些互不影响的边界环，那么铺法数满足
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $$
而空边界对应的贡献是 \(1\)，因为它表示区域已经被完全铺满。
当 \(a=b=1\) 时，初始边界词非常简单：
$$ w_{1,1}=(0,1,2,3,4,5,6,7). $$
此时规范起点就是最左下角，出边方向向东。因此递归的第一步只会尝试三种首块：一个向东北转的菱形、一个向北转的正方形、以及一个向西北转的菱形。每一种合法首块都会留下一个更小的边界状态，或者直接完成铺满。把这些分支全部累加后得到
$$ t(O_{1,1})=8, $$
这正是实现里用于检验递归是否正确的一个小型检查值。
C++、Python 和 Java 三个实现都遵循同一条递归关系。它们先构造 \(O_{4,2}\) 的初始边界词，再把边界词展开成顶点序列，选出规范化的最低最左起点，然后最多尝试三块候选砖。若某块砖没有通过点在多边形内测试或线段相交测试，就立即丢弃；若通过，则用单位边集合的对称差生成新的边界，再把重建出的每个边界环统一整理成逆时针方向后送入记忆化搜索。计数本身使用任意精度整数保存，因此不会溢出。C++ 版本还额外对 \(t(O_{1,1})=8\)、\(t(O_{2,1})=76\) 和 \(t(O_{3,2})=456572\) 这几个较小案例做对照检查，但三种语言的核心递归完全一致。
若某个状态的边界长度为 \(m\)，那么构造顶点、寻找规范起点、测试三种候选砖、执行线段相交判断以及重建下一轮边界环，都只需要关于 \(m\) 的线性时间。因此单个被访问状态的代价是 \(O(m)\) 时间和 \(O(m)\) 临时空间。真正的难点在于不同边界状态的数量可能随问题规模呈指数增长，所以整体最坏复杂度仍然是指数级。不过，记忆化会合并大量重复子状态，非法几何分支往往会被很早剪掉，而边界分裂成多个互相独立的环时又能把大问题拆成若干小问题，这些因素都会显著改善实际运行表现。
Пусть \(O_{a,b}\) обозначает равноугольный восьмиугольник, у которого длины сторон по кругу идут как \(a,b,a,b,a,b,a,b\). Требуется вычислить \(t(O_{4,2})\), где \(t(O_{a,b})\) означает число замощений этого восьмиугольника ромбами единичного ребра и квадратами единичного ребра. Реализации не выводят закрытую формулу; они считают ответ рекурсивно, кодируя каждую оставшуюся область только ее границей.
Главное геометрическое наблюдение состоит в том, что каждое ребро плитки лежит в одном из восьми направлений, отстоящих друг от друга на \(45^\circ\). Если умножить координаты на \(2\), эти направления записываются как
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $$
Значит, любая координата имеет вид \(r+s\sqrt{2}\), что в точности совпадает с алгебраическим представлением, используемым в реализациях.
Начальный восьмиугольник кодируется циклическим словом
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $$
Вообще любая оставшаяся подобласть задается циклической последовательностью ее единичных граничных шагов. Если такое слово равно \(w\), то \(T(w)\) обозначает число замощений области, ограниченной этим словом.
Чтобы не пересчитывать одно и то же замощение разными способами, рекурсия всегда выбирает самую нижнюю граничную вершину, а при равенстве еще и самую левую. Пусть это вершина \(p\), а направление исходящего из нее граничного ребра равно \(d\). В любом корректном замощении существует ровно одна плитка, использующая это открытое граничное ребро, поэтому достаточно перебрать только те плитки, которые могут быть поставлены именно там.
Пусть \(u\) — единичный вектор направления \(d\). Вторая сторона плитки должна повернуть внутрь области на \(45^\circ\), \(90^\circ\) или \(135^\circ\). Поэтому нужно рассматривать только единичный вектор \(v\) направления \(d+\delta \pmod 8\), где \(\delta\in\{1,2,3\}\), а вершины кандидата имеют вид
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $$
При \(\delta=2\) получается квадрат, а при \(\delta=1\) и \(\delta=3\) — две ориентации ромба. Никакой другой выпуклый квадрат или ромб единичного ребра не может одновременно разделять выбранное граничное ребро и оставаться внутри области.
Кандидат принимается только в том случае, если две его внутренние вершины лежат внутри текущего многоугольника или на его границе, а ни одно из четырех ребер не пересекает существующее граничное ребро, кроме общих концов или самого общего граничного ребра. Векторные произведения, проверки отрезков и координаты вершин все время остаются в алгебраической форме \(r+s\sqrt{2}\), поэтому геометрические тесты точно согласованы с исходной восьминаправленной решеткой.
Обозначим через \(E(P)\) множество единичных ребер текущей границы, а через \(E(Q)\) — границу выбранной плитки. После удаления этой плитки из оставшейся области общие ребра исчезают, а открытые ребра плитки становятся новой границей, поэтому
$$ E(P\setminus Q)=E(P)\triangle E(Q), $$
где \(\triangle\) означает симметрическую разность. Из полученного множества ребер затем детерминированно восстанавливаются один или несколько граничных циклов против часовой стрелки: старт берется с самого нижнего левого неиспользованного ребра, а дальше на каждом шаге выбирается минимальный левый поворот. Если область распадается на циклы \(w_1,\dots,w_r\), то подзадачи независимы и
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $$
причем пустая граница дает вклад \(1\).
При \(a=b=1\) начальное слово границы равно
$$ w_{1,1}=(0,1,2,3,4,5,6,7). $$
Канонической стартовой вершиной оказывается самая нижняя левая вершина, а исходящее ребро направлено на восток. Поэтому рекурсия проверяет ровно три первых плитки: ромб с поворотом к северо-востоку, квадрат с поворотом к северу и ромб с поворотом к северо-западу. Сумма по всем допустимым продолжениям дает
$$ t(O_{1,1})=8, $$
и это совпадает с одним из контрольных значений, используемых для проверки рекуррентной схемы.
Реализации на C++, Python и Java используют одну и ту же рекуррентную конструкцию. Сначала они строят начальное граничное слово для \(O_{4,2}\), разворачивают его в список вершин, выбирают канонический старт в самой нижней левой точке, пробуют до трех кандидатных плиток, отбрасывают те, которые не проходят проверку «точка в многоугольнике» или проверку пересечения отрезков, и обновляют границу через симметрическую разность единичных ребер. Каждый восстановленный цикл перед обращением к мемоизации ориентируется против часовой стрелки, чтобы эквивалентные подобласти получали один и тот же ключ кэша. Подсчет ведется в целых числах произвольной длины, а реализация на C++ дополнительно сверяется с малыми значениями \(t(O_{1,1})=8\), \(t(O_{2,1})=76\) и \(t(O_{3,2})=456572\).
Если длина границы состояния равна \(m\), то построение вершин, поиск канонического старта, проверка трех кандидатных плиток, тесты пересечений и восстановление новых граничных циклов требуют линейного времени по \(m\). Следовательно, один посещенный узел поиска стоит \(O(m)\) времени и \(O(m)\) временной памяти. В худшем случае общий перебор остается экспоненциальным, потому что число различных граничных состояний может расти экспоненциально. Однако мемоизация, раннее отсечение геометрически невозможных ветвей и распад области на независимые циклы существенно уменьшают практический объем поиска.
ليكن \(O_{a,b}\) مثمنًا متساوي الزوايا، وتكون أطوال أضلاعه على الترتيب الدوري \(a,b,a,b,a,b,a,b\). المطلوب هو حساب \(t(O_{4,2})\)، حيث تعبّر \(t(O_{a,b})\) عن عدد تبليطات هذا المثمن بمعيّنات طول ضلعها \(1\) ومربعات طول ضلعها \(1\). لا تعتمد التطبيقات على صيغة مغلقة مباشرة، بل تعدّ التبليطات بطريقة تكرارية عبر تمثيل كل منطقة متبقية بحدّها فقط.
الفكرة الهندسية الأساسية هي أن كل ضلع في أي بلاطة يقع في واحد من ثمانية اتجاهات تفصل بينها زاوية \(45^\circ\). بعد تكبير الإحداثيات بعامل \(2\)، تصبح هذه الاتجاهات
$$ (2,0),\ (\sqrt{2},\sqrt{2}),\ (0,2),\ (-\sqrt{2},\sqrt{2}),\ (-2,0),\ (-\sqrt{2},-\sqrt{2}),\ (0,-2),\ (\sqrt{2},-\sqrt{2}). $$
وبالتالي يمكن كتابة كل إحداثي على الصورة \(r+s\sqrt{2}\)، وهي بالضبط البنية الجبرية التي تعتمدها التطبيقات عند تمثيل النقاط والمتجهات.
يُمثَّل المثمن الابتدائي بالكلمة الدورية
$$ w_{a,b}=(\underbrace{0,\dots,0}_{a},\underbrace{1,\dots,1}_{b},\underbrace{2,\dots,2}_{a},\underbrace{3,\dots,3}_{b},\underbrace{4,\dots,4}_{a},\underbrace{5,\dots,5}_{b},\underbrace{6,\dots,6}_{a},\underbrace{7,\dots,7}_{b}). $$
كل رقم هنا يصف اتجاه خطوة حدّية واحدة بطول وحدة. وبصورة أعم، فإن أي منطقة فرعية متبقية أثناء البحث تُمثَّل أيضًا بالتتابع الدوري لخطوات حدّها. وإذا كانت هذه الكلمة هي \(w\)، فإن \(T(w)\) يرمز إلى عدد تبليطات المنطقة التي تحيط بها.
حتى لا تُعدّ التبليطة نفسها أكثر من مرة، تختار الاستدعاءات التكرارية دائمًا أدنى رأس على الحد، وعند التعادل يُختار الأيسر. لنسمِّ هذا الرأس \(p\)، ولتكن جهة الضلع الخارج منه هي \(d\). في أي تبليط صالح توجد بلاطة واحدة بالضبط تستعمل هذا الضلع المكشوف من الحد، ولذلك يكفي أن نحصي البلاطات الممكنة الملتصقة به بدل التجريب العشوائي داخل المنطقة كلها.
لتكن \(u\) هي متجهة الوحدة في الاتجاه \(d\). بما أن البلاطة يجب أن تشارك هذا الضلع وأن تبقى داخل المنطقة، فإن ضلعها الثاني لا بد أن ينعطف إلى الداخل بمقدار \(45^\circ\) أو \(90^\circ\) أو \(135^\circ\). لهذا لا نحتاج إلا إلى متجهة الوحدة \(v\) في الاتجاه \(d+\delta \pmod 8\) حيث \(\delta\in\{1,2,3\}\)، وعندها تكون رؤوس البلاطة المرشحة هي
$$ p,\qquad p+u,\qquad p+u+v,\qquad p+v. $$
الحالة \(\delta=2\) تعطي مربعًا، والحالتان \(\delta=1\) و\(\delta=3\) تعطيان اتجاهي المعيّن الممكنين. ولا يوجد مربع أو معيّن محدب آخر بطول ضلع \(1\) يمكنه مشاركة الضلع المختار والبقاء داخل المنطقة.
لا تُقبل البلاطة المرشحة إلا إذا كان رأساها الداخليان داخل المضلع الحالي أو على حدّه، وإذا كانت أضلاعها الأربعة لا تقطع أي ضلع حدّي موجود قطعًا غير مسموح به. المسموح فقط هو مشاركة نقطة نهاية، أو مشاركة الضلع الحدّي نفسه الذي بُنيت عليه البلاطة. وبما أن الإحداثيات والجداءات الاتجاهية تبقى كلها من الشكل \(r+s\sqrt{2}\)، فإن اختبارات التقاطع والانتماء إلى القطعة المستقيمة تنسجم تمامًا مع الشبكة ذات الاتجاهات الثمانية.
لنرمز بـ \(E(P)\) إلى مجموعة الأضلاع الوحدية على حدّ المنطقة الحالية، وبـ \(E(Q)\) إلى حدّ البلاطة المختارة. بعد إزالة هذه البلاطة من المنطقة المتبقية تختفي الأضلاع المشتركة، بينما تظهر أضلاع البلاطة التي أصبحت مكشوفة، ولذلك نحصل على
$$ E(P\setminus Q)=E(P)\triangle E(Q), $$
حيث تمثل \(\triangle\) الفرق المتماثل بين المجموعتين. بعد ذلك يُعاد بناء الحد الجديد في صورة دورة واحدة أو عدة دورات عكس اتجاه عقارب الساعة، وذلك بسير حتمي يبدأ من أدنى ضلع غير مستخدم ثم الأيسر، ويختار في كل خطوة أصغر انعطاف يساري. وإذا انقسمت المنطقة إلى دورات \(w_1,\dots,w_r\)، فإن المسائل الفرعية تصبح مستقلة ويكون
$$ T(w)=\sum_{Q} \prod_{i=1}^{r} T(w_i), $$
مع اعتبار الحد الفارغ مساهمة تساوي \(1\)، لأنه يعني أن المنطقة امتلأت بالكامل.
عندما \(a=b=1\)، تكون كلمة الحد الابتدائية هي
$$ w_{1,1}=(0,1,2,3,4,5,6,7). $$
الرأس المعياري هنا هو الزاوية الأدنى فالأيسر، ويشير ضلع الخروج منها إلى الشرق. لذلك تختبر آلية العد التكرارية ثلاث بلاطات أولى فقط: معيّنًا ينعطف إلى الشمال الشرقي، ومربعًا ينعطف إلى الشمال، ومعيّنًا ينعطف إلى الشمال الغربي. وبجمع جميع الفروع الصالحة نحصل على
$$ t(O_{1,1})=8, $$
وهو أحد القيم الصغيرة المستخدمة للتحقق من صحة العلاقة التكرارية.
تتبع تطبيقات C++ وPython وJava جميعًا العلاقة نفسها. فهي تبني أولًا كلمة الحد الابتدائية لـ \(O_{4,2}\)، ثم توسعها إلى قائمة رؤوس، وتختار البداية المعيارية الأدنى ثم الأيسر، وتجرب حتى ثلاث بلاطات مرشحة، وترفض ما يفشل في اختبار النقطة داخل المضلع أو في اختبار تقاطع القطع المستقيمة، ثم تحدّث الحد عبر الفرق المتماثل لأضلاع الوحدة. كل دورة حدية يعاد بناؤها تُوجَّه عكس اتجاه عقارب الساعة قبل العودة إلى الذاكرة التخزينية حتى تشترك المناطق الفرعية المكافئة في المفتاح نفسه. ويُحفَظ العد في أعداد صحيحة ذات دقة غير محدودة، كما تتحقق نسخة C++ أيضًا من قيم صغيرة مثل \(t(O_{1,1})=8\) و\(t(O_{2,1})=76\) و\(t(O_{3,2})=456572\).
إذا كان طول حد حالة ما هو \(m\)، فإن بناء الرؤوس، والعثور على البداية المعيارية، وتجربة البلاطات الثلاث المرشحة، وفحص التقاطعات، وإعادة بناء دورات الحد التالية، كلها عمليات خطية في \(m\). لذا فتكلفة الحالة الواحدة هي \(O(m)\) زمنًا و\(O(m)\) ذاكرة مؤقتة. ومع ذلك يبقى البحث الكلي أسيًا في أسوأ الأحوال لأن عدد الحالات الحدّية المختلفة قد ينمو أسيًا. عمليًا، تقلل الذاكرة التخزينية للفروع المتكررة، والرفض الهندسي المبكر، وانقسام المنطقة إلى دورات مستقلة، هذا الحيز بصورة واضحة.