The task is to count the number of tilings of a \(9\times12\) rectangle by triominoes. The implementations allow all six orientations: the two straight trominoes and the four \(L\)-shaped trominoes.
Because each piece covers exactly three cells, the obvious necessary condition is \(3 \mid 9\cdot12\), so the challenge is not existence but exact enumeration. A direct search is still hopeless, since a local choice can affect cells one or two rows later.
Process the board from top to bottom. At any stage, the dynamic program remembers which cells are already occupied in two consecutive frontier rows. A bit value of 1 means that the cell is already covered by pieces chosen earlier, and a bit value of 0 means that the cell must still be completed by pieces extending farther downward.
The stored state therefore needs only \(2W\) bits for width \(W\). During one transition, a fresh third row is attached underneath those two rows, so the local search works on a temporary \(3W\)-bit mask. When that search finishes, the oldest row is dropped and the remaining two rows become the next stored profile.
This is the key compression: the global tiling is huge, but all future decisions depend only on the occupancy pattern of the next two rows.
The recursive search scans the newly attached bottom row from right to left. For the current column \(c\), every new piece is charged to the cell \((r+2,c)\), the lowest cell of that placement inside the three-row window. Relative to rows \(r,r+1,r+2\), the six admissible shapes are
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
These are exactly the two straight triominoes and the four rotations of the \(L\)-triomino. There is also a “skip” branch in the DFS: if \((r+2,c)\) was already covered by a placement chosen at a larger column, the search simply moves left.
Let \(S\) be the set of all \(2W\)-bit profiles, and let \(T(s,t)\) be the number of local completions that start from stored profile \(s\), add pieces whose lowest cells lie in the new row, and end with next profile \(t\).
If \(F_k(s)\) denotes the number of ways to process the first \(k\) board rows and finish with profile \(s\), then the row-to-row transition is
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$$
The crucial validity condition is that the oldest of the three rows must be completely filled at the end of the local search. No later piece can reach that far upward, so any unfinished cell there would make the whole partial tiling impossible.
Take width \(W=4\). Suppose the current stored profile is 1111 | 0110: the older row is already complete, while in the next row only the two middle cells are covered. The newly appended third row starts as 0000.
Now place an \(L\)-triomino on the left covering \((r+1,0),(r+2,0),(r+2,1)\), and a mirrored \(L\)-triomino on the right covering \((r+1,3),(r+2,2),(r+2,3)\). After those two placements the three rows become 1111, 1111, 1111.
So this local completion is valid, and after dropping the oldest row the next stored profile is again 1111 | 1111. This shows why a hole in the second frontier row is not yet fatal: it may be completed by a piece whose lowest cell lies in the new row.
Let \(\mathbf{1}\) denote the profile whose two stored rows are completely filled. The dynamic program starts from \(F_0(\mathbf{1})=1\). That encodes the top boundary: nothing may protrude above the rectangle, so the two fictitious rows above the board are treated as already closed.
After all \(H\) actual rows have been processed, the answer is \(F_H(\mathbf{1})\). Ending at the full profile means that no unfinished triomino protrudes below the bottom edge. For Problem 161, the implementations evaluate this at \(W=9\) and \(H=12\).
The C++, Python, and Java implementations all perform the same row-by-row dynamic program. A profile is encoded as a bitmask for two frontier rows. The C++ and Java versions keep dense arrays indexed by that mask, while the Python version stores only the currently reachable masks in dictionaries.
Each DP layer represents one more processed row. For every active profile, the implementation enumerates all valid local completions of the three-row window, counts how many times each next profile occurs, and adds that multiplicity to the next layer.
The local enumeration is a depth-first search over the columns of the new row. It tries the six geometric placements above whenever their required cells are still free and their columns stay inside the board. When the search reaches the left end, it accepts the transition only if the oldest frontier row is fully occupied; the next profile is then obtained by discarding that row and shifting the remaining mask down by one row.
The Python implementation caches the transition list for every profile that it has already explored. The C++ and Java implementations recompute those transfers as needed but use fixed-size integer arrays for fast accumulation. Despite those engineering differences, all three programs realize the same transfer matrix.
For width \(W\), the stored state space has size \(2^{2W}=4^W\). In Problem 161, \(W=9\), so there are at most \(2^{18}=262{,}144\) possible profiles, although many of them are never reachable.
For each active profile, transition generation is a bounded DFS over at most \(W\) columns with only local branching from the six triomino placements and the skip case. Thus the method is exponential in the narrow dimension \(W\), but linear in the height once transitions are available. This is exactly the regime where profile DP is effective.
The dense-array implementations use \(O(2^{2W})\) memory for the current and next layers. The Python version stores fewer profiles at once, but it still traverses the same underlying state graph.
Gesucht ist die Anzahl der Pflasterungen eines \(9\times12\)-Rechtecks mit Triominos. Die Implementierungen erlauben alle sechs Orientierungen: die beiden geraden Trominos und die vier \(L\)-förmigen Trominos.
Da jedes Teil genau drei Zellen bedeckt, ist die naheliegende notwendige Bedingung \(3 \mid 9\cdot12\) erfüllt. Die Schwierigkeit liegt also nicht in der Existenz, sondern in der exakten Zählung. Eine direkte Suche scheitert daran, dass eine lokale Entscheidung Zellen noch ein oder zwei Zeilen später beeinflussen kann.
Das Rechteck wird von oben nach unten verarbeitet. Zu jedem Zeitpunkt merkt sich die dynamische Programmierung, welche Zellen in zwei aufeinanderfolgenden Frontzeilen bereits besetzt sind. Ein Bitwert 1 bedeutet: Diese Zelle ist durch früher gewählte Steine schon bedeckt. Ein Bitwert 0 bedeutet: Diese Zelle muss noch durch einen weiter nach unten reichenden Stein geschlossen werden.
Darum benötigt der gespeicherte Zustand bei Breite \(W\) nur \(2W\) Bits. Während eines Übergangs wird darunter eine frische dritte Zeile angehängt, sodass die lokale Suche auf einer temporären \(3W\)-Bitmaske arbeitet. Am Ende wird die älteste Zeile verworfen, und die beiden übrigen Zeilen bilden das nächste gespeicherte Profil.
Genau darin steckt die Kompression: Die vollständige Pflasterung ist riesig, aber alle zukünftigen Entscheidungen hängen nur vom Belegungsmuster der nächsten beiden Zeilen ab.
Die rekursive Suche durchläuft die neu angehängte untere Zeile von rechts nach links. Für die aktuelle Spalte \(c\) wird jeder neue Stein der Zelle \((r+2,c)\) zugeordnet, also der tiefsten Zelle dieser Platzierung im Drei-Zeilen-Fenster. Relativ zu den Zeilen \(r,r+1,r+2\) sind die sechs erlaubten Formen
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
Das sind genau die beiden geraden Triominos und die vier Drehungen des \(L\)-Triominos. Zusätzlich gibt es einen „Überspringen“-Zweig in der Tiefensuche: Falls \((r+2,c)\) bereits durch eine in einer größeren Spalte gewählte Platzierung bedeckt wurde, läuft die Suche einfach nach links weiter.
Sei \(S\) die Menge aller \(2W\)-Bit-Profile, und sei \(T(s,t)\) die Anzahl der lokalen Vervollständigungen, die beim gespeicherten Profil \(s\) starten, Steine mit tiefster Zelle in der neuen Zeile hinzufügen und beim nächsten Profil \(t\) enden.
Wenn \(F_k(s)\) die Anzahl der Möglichkeiten bezeichnet, nach den ersten \(k\) Rechteckzeilen mit Profil \(s\) zu enden, lautet der Zeilenübergang
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$$
Die entscheidende Gültigkeitsbedingung lautet: Am Ende der lokalen Suche muss die älteste der drei Zeilen vollständig gefüllt sein. Spätere Steine können nicht mehr so weit nach oben reichen; jede dort verbleibende Lücke macht die gesamte partielle Pflasterung unmöglich.
Nehmen wir \(W=4\). Angenommen, das aktuelle gespeicherte Profil ist 1111 | 0110: Die ältere Zeile ist schon komplett, in der nächsten Zeile sind aber nur die beiden mittleren Zellen bedeckt. Die neu angehängte dritte Zeile startet als 0000.
Setzt man links ein \(L\)-Triomino auf \((r+1,0),(r+2,0),(r+2,1)\) und rechts das gespiegelte \(L\)-Triomino auf \((r+1,3),(r+2,2),(r+2,3)\), dann werden die drei Zeilen zu 1111, 1111, 1111.
Diese lokale Vervollständigung ist also gültig, und nach dem Verwerfen der ältesten Zeile ist das nächste gespeicherte Profil wieder 1111 | 1111. Das Beispiel zeigt, warum eine Lücke in der zweiten Frontzeile noch kein Widerspruch ist: Sie kann durch einen Stein geschlossen werden, dessen tiefste Zelle erst in der neuen Zeile liegt.
Sei \(\mathbf{1}\) das Profil, in dem beide gespeicherten Zeilen vollständig gefüllt sind. Das dynamische Programm startet mit \(F_0(\mathbf{1})=1\). Das kodiert den oberen Rand: Über das Rechteck darf nichts hinausragen, also werden die beiden fiktiven Zeilen oberhalb des Bretts als bereits abgeschlossen behandelt.
Nachdem alle \(H\) echten Zeilen verarbeitet wurden, ist die Antwort \(F_H(\mathbf{1})\). Das Enden im vollen Profil bedeutet, dass kein unvollständiges Triomino unter dem unteren Rand herausragt. Für Problem 161 wird dies bei \(W=9\) und \(H=12\) ausgewertet.
Die C++-, Python- und Java-Implementierungen führen alle dieselbe zeilenweise Dynamik aus. Ein Profil wird als Bitmaske für zwei Frontzeilen kodiert. Die C++- und Java-Versionen verwenden dichte Arrays, die direkt über diese Maske indiziert werden, während die Python-Version nur die aktuell erreichbaren Masken in Dictionaries speichert.
Jede DP-Schicht steht für eine weitere verarbeitete Zeile. Für jedes aktive Profil enumeriert die Implementierung alle gültigen lokalen Vervollständigungen des Drei-Zeilen-Fensters, zählt, wie oft jedes Folgeprofil auftritt, und addiert diese Multiplizität zur nächsten Schicht.
Die lokale Enumeration ist eine Tiefensuche über die Spalten der neuen Zeile. Sie probiert die sechs geometrischen Platzierungen immer dann aus, wenn die benötigten Zellen noch frei sind und die beteiligten Spalten innerhalb des Bretts liegen. Erreicht die Suche das linke Ende, wird der Übergang nur akzeptiert, wenn die älteste Frontzeile vollständig besetzt ist; das Folgeprofil entsteht dann, indem diese Zeile verworfen und die verbleibende Maske um eine Zeile nach unten geschoben wird.
Die Python-Implementierung puffert die Übergangsliste für jedes bereits untersuchte Profil. Die C++- und Java-Implementierungen berechnen diese Übergänge bei Bedarf neu, nutzen aber feste Ganzzahl-Arrays für schnelle Akkumulation. Trotz dieser technischen Unterschiede realisieren alle drei Programme dieselbe Transfermatrix.
Für Breite \(W\) hat der gespeicherte Zustandsraum Größe \(2^{2W}=4^W\). In Problem 161 ist \(W=9\), also gibt es höchstens \(2^{18}=262{,}144\) mögliche Profile, auch wenn viele davon nie erreichbar sind.
Für jedes aktive Profil besteht die Übergangserzeugung aus einer beschränkten Tiefensuche über höchstens \(W\) Spalten, mit nur lokaler Verzweigung durch die sechs Triomino-Platzierungen und den Überspringen-Fall. Damit ist die Methode exponentiell in der schmalen Dimension \(W\), aber linear in der Höhe, sobald die Übergänge feststehen. Genau in diesem Bereich ist Profil-DP stark.
Die dichten Implementierungen benötigen \(O(2^{2W})\) Speicher für aktuelle und nächste Schicht. Die Python-Version hält gleichzeitig weniger Profile, bewegt sich aber auf demselben zugrunde liegenden Zustandsgraphen.
İstenen şey, \(9\times12\) boyutlu bir dikdörtgenin triomino taşlarıyla kaç farklı biçimde döşenebildiğini saymaktır. Uygulamalar altı yönelimin tamamını kabul eder: iki doğrusal tromino ve dört \(L\) biçimli tromino.
Her taş tam üç kare kapladığı için ilk gerekli koşul \(3 \mid 9\cdot12\) eşitliğidir ve bu koşul sağlanır. Asıl güçlük, varlık sorusu değil tam sayımdır; çünkü bir satırdaki tercih, bir veya iki satır aşağıdaki boşlukları doğrudan etkiler.
Tahtayı yukarıdan aşağıya doğru işleyelim. Her adımda dinamik programlama, art arda gelen iki sınır satırındaki hangi hücrelerin zaten dolu olduğunu tutar. Bit değeri 1 ise o hücre daha önce seçilmiş taşlar tarafından kapatılmıştır; bit değeri 0 ise hücre ancak daha aşağı uzanan bir taşla tamamlanacaktır.
Bu yüzden saklanan durum, genişlik \(W\) için yalnızca \(2W\) bitten oluşur. Bir geçiş sırasında bu iki satırın altına yeni bir üçüncü satır eklenir; dolayısıyla yerel arama geçici olarak \(3W\) bitlik bir maske üzerinde çalışır. Arama bittiğinde en yaşlı satır atılır ve kalan iki satır sonraki profili oluşturur.
Asıl sıkıştırma burada yatar: küresel döşeme çok büyüktür, fakat gelecekteki bütün kararlar yalnızca sonraki iki satırın doluluk desenine bağlıdır.
Özyinelemeli arama yeni eklenen en alt satırı sağdan sola tarar. Geçerli sütun \(c\) için her yeni taş, üç satırlık pencere içindeki en alt hücresi olan \((r+2,c)\) noktasına bağlanır. \(r,r+1,r+2\) satırlarına göre altı izinli şekil şunlardır:
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
Bunlar tam olarak iki doğrusal triomino ile \(L\)-triominonun dört dönüşüdür. DFS içinde bir de “atla” dalı vardır: \((r+2,c)\) hücresi daha büyük bir sütunda seçilmiş bir yerleşim tarafından zaten kapatılmışsa arama yalnızca sola ilerler.
\(S\), tüm \(2W\)-bit profillerin kümesi olsun. \(T(s,t)\), saklanan \(s\) profilinden başlayıp en alt hücresi yeni satırda olan taşlar ekleyerek \(t\) sonraki profiline ulaşan yerel tamamlamaların sayısı olsun.
\(F_k(s)\), ilk \(k\) satır işlendiğinde profilin \(s\) olmasının yol sayısını gösterirse satırdan satıra geçiş
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t)$$
şeklindedir. Buradaki kritik geçerlilik koşulu şudur: yerel aramanın sonunda üç satırın en eskisi bütünüyle dolu olmalıdır. Daha sonra seçilecek hiçbir taş bu kadar yukarı uzanamayacağı için orada kalan tek bir boşluk bile o kısmi döşemeyi geçersiz kılar.
\(W=4\) alalım. Geçerli profilin 1111 | 0110 olduğunu düşünelim: yaşlı satır tamamen doludur, ikinci satırda ise yalnızca ortadaki iki hücre kapalıdır. Yeni eklenen üçüncü satır başlangıçta 0000 olsun.
Şimdi solda \((r+1,0),(r+2,0),(r+2,1)\) hücrelerini kaplayan bir \(L\)-triomino, sağda da \((r+1,3),(r+2,2),(r+2,3)\) hücrelerini kaplayan aynalanmış bir \(L\)-triomino yerleştirelim. Bu iki yerleşimden sonra üç satırın durumu 1111, 1111, 1111 olur.
Demek ki bu yerel tamamlama geçerlidir ve en yaşlı satır atıldığında sonraki profil yine 1111 | 1111 olur. Bu örnek, ikinci sınır satırındaki bir boşluğun neden hemen çelişki olmadığını gösterir: o boşluk, en alt hücresi yeni satırda olan bir taşla sonradan kapatılabilir.
\(\mathbf{1}\), saklanan iki satırın da tamamen dolu olduğu profil olsun. Dinamik program \(F_0(\mathbf{1})=1\) durumundan başlar. Bu, üst sınırı kodlar: dikdörtgenin üstüne hiçbir taş taşamaz; bu nedenle tahta üzerindeki iki hayali üst satır zaten kapanmış kabul edilir.
Bütün \(H\) gerçek satırlar işlendiğinde cevap \(F_H(\mathbf{1})\) olur. Tam dolu profilde bitmek, dikdörtgenin alt kenarının altına sarkan eksik bir triomino kalmadığı anlamına gelir. Problem 161 için uygulamalar bunu \(W=9\) ve \(H=12\) için hesaplar.
C++, Python ve Java uygulamalarının üçü de aynı satır-satır dinamik programı yürütür. Profil, iki sınır satırını temsil eden bir bit maskesi olarak kodlanır. C++ ve Java sürümleri bu maskeyle indislenen yoğun diziler kullanırken Python sürümü yalnızca o anda erişilebilir maskeleri sözlüklerde tutar.
Her DP katmanı işlenmiş bir satır daha demektir. Her aktif profil için uygulama, üç satırlık pencerenin bütün geçerli yerel tamamlamalarını üretir, her sonraki profilin kaç kez oluştuğunu sayar ve bu çokluğu bir sonraki katmana ekler.
Yerel üretim, yeni satırın sütunları üzerinde çalışan bir derinlik öncelikli aramadır. Gerekli hücreler boşsa ve kullanılan sütunlar tahta sınırları içinde kalıyorsa yukarıdaki altı geometrik yerleşim denenir. Arama en sola ulaştığında geçiş yalnızca en yaşlı sınır satırı tamamen doluysa kabul edilir; ardından bu satır atılır ve kalan maske bir satır aşağı kaydırılarak sonraki profil elde edilir.
Python uygulaması daha önce incelenmiş her profil için geçiş listesini önbelleğe alır. C++ ve Java uygulamaları bu geçişleri gerektiğinde yeniden üretir ama hızlı toplama için sabit boyutlu tamsayı dizileri kullanır. Mühendislik tercihleri farklı olsa da üçü de aynı geçiş matrisini uygular.
Genişlik \(W\) için saklanan durum uzayının boyutu \(2^{2W}=4^W\) olur. Problem 161'de \(W=9\) olduğundan en fazla \(2^{18}=262{,}144\) profil vardır; bunların önemli bir kısmı pratikte hiç erişilmez.
Her aktif profil için geçiş üretimi, en fazla \(W\) sütun üzerinde çalışan sınırlı bir DFS'tir; dallanma yalnızca altı triomino yerleşimi ve atlama durumundan gelir. Dolayısıyla yöntem dar boyut \(W\) açısından üstelseldir, fakat geçişler hazır olduğunda yükseklik açısından doğrusaldır. Profil DP'nin güçlü olduğu rejim tam da budur.
Yoğun dizi kullanan sürümler mevcut ve sonraki katmanlar için \(O(2^{2W})\) bellek kullanır. Python sürümü aynı anda daha az profil saklar, fakat yine aynı temel durum grafiği üzerinde dolaşır.
Se pide contar cuántas teselaciones de un rectángulo \(9\times12\) pueden hacerse con triominós. Las implementaciones admiten las seis orientaciones: los dos trominós rectos y las cuatro versiones en forma de \(L\).
Como cada pieza cubre exactamente tres casillas, la condición necesaria más evidente es \(3 \mid 9\cdot12\), y aquí sí se cumple. Por tanto, la dificultad no es decidir si existe una teselación, sino enumerarlas todas exactamente. Un backtracking directo sería inabordable, porque una elección local puede condicionar una o dos filas posteriores.
Se procesa el tablero de arriba hacia abajo. En cada instante, la programación dinámica recuerda qué celdas de dos filas consecutivas de la frontera ya están ocupadas. Un bit con valor 1 significa que esa celda ya fue cubierta por piezas elegidas antes; un bit con valor 0 significa que todavía debe completarse mediante una pieza que baje más.
Por eso el estado almacenado solo necesita \(2W\) bits para anchura \(W\). Durante una transición se añade una tercera fila fresca por debajo de esas dos filas, de modo que la búsqueda local trabaja sobre una máscara temporal de \(3W\) bits. Cuando esa búsqueda termina, se descarta la fila más antigua y las dos filas restantes forman el siguiente perfil.
Esa es la compresión esencial: la teselación global es enorme, pero todas las decisiones futuras dependen únicamente del patrón de ocupación de las dos filas siguientes.
La búsqueda recursiva recorre de derecha a izquierda la nueva fila inferior. Para la columna actual \(c\), cada pieza nueva se asocia con la celda \((r+2,c)\), que es la celda más baja de esa colocación dentro de la ventana de tres filas. Con respecto a las filas \(r,r+1,r+2\), las seis formas permitidas son
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
Estas son exactamente los dos triominós rectos y las cuatro rotaciones del triominó en \(L\). Además existe una rama de “saltar” en la DFS: si \((r+2,c)\) ya quedó cubierto por una colocación elegida en una columna mayor, la búsqueda simplemente continúa hacia la izquierda.
Sea \(S\) el conjunto de todos los perfiles de \(2W\) bits, y sea \(T(s,t)\) el número de completaciones locales que parten del perfil almacenado \(s\), añaden piezas cuya celda más baja cae en la fila nueva y terminan en el perfil siguiente \(t\).
Si \(F_k(s)\) denota el número de formas de procesar las primeras \(k\) filas del tablero y acabar con el perfil \(s\), entonces la transición fila a fila es
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$$
La condición clave de validez es que la más antigua de las tres filas debe quedar completamente llena al final de la búsqueda local. Ninguna pieza futura podrá alcanzar una fila tan alta, de modo que cualquier hueco restante allí invalida la construcción parcial.
Tomemos \(W=4\). Supongamos que el perfil almacenado actual es 1111 | 0110: la fila más antigua ya está completa, mientras que en la fila siguiente solo están cubiertas las dos celdas centrales. La tercera fila recién añadida empieza como 0000.
Coloquemos ahora un triominó en \(L\) a la izquierda cubriendo \((r+1,0),(r+2,0),(r+2,1)\), y otro triominó en \(L\) reflejado a la derecha cubriendo \((r+1,3),(r+2,2),(r+2,3)\). Después de esas dos colocaciones, las tres filas pasan a ser 1111, 1111, 1111.
Esa completación local es válida, y al descartar la fila más antigua el perfil siguiente vuelve a ser 1111 | 1111. El ejemplo ilustra por qué un hueco en la segunda fila de la frontera todavía no es fatal: puede cerrarse con una pieza cuya celda más baja aparezca en la fila nueva.
Sea \(\mathbf{1}\) el perfil en el que las dos filas almacenadas están completamente llenas. El programa dinámico empieza en \(F_0(\mathbf{1})=1\). Eso codifica el borde superior: no se permite que ninguna pieza sobresalga por encima del rectángulo, así que las dos filas ficticias superiores se tratan como ya cerradas.
Después de procesar las \(H\) filas reales, la respuesta es \(F_H(\mathbf{1})\). Terminar en el perfil lleno significa que no queda ningún triominó inacabado sobresaliendo por debajo del borde inferior. En el Problema 161, las implementaciones evalúan esto en \(W=9\) y \(H=12\).
Las implementaciones en C++, Python y Java ejecutan la misma programación dinámica fila por fila. Un perfil se codifica como una máscara de bits para dos filas de frontera. Las versiones de C++ y Java usan arreglos densos indexados por esa máscara, mientras que la versión de Python guarda en diccionarios solo las máscaras alcanzables en ese momento.
Cada capa de DP representa una fila más ya procesada. Para cada perfil activo, la implementación enumera todas las completaciones locales válidas de la ventana de tres filas, cuenta cuántas veces aparece cada perfil siguiente y añade esa multiplicidad a la capa siguiente.
La enumeración local es una búsqueda en profundidad sobre las columnas de la fila nueva. Va probando las seis colocaciones geométricas de arriba siempre que las celdas necesarias sigan libres y las columnas involucradas queden dentro del tablero. Cuando la búsqueda alcanza el extremo izquierdo, solo acepta la transición si la fila de frontera más antigua está completamente ocupada; el perfil siguiente se obtiene entonces descartando esa fila y desplazando la máscara restante una fila hacia abajo.
La implementación en Python memoriza la lista de transiciones de cada perfil ya explorado. Las implementaciones en C++ y Java recalculan esas transferencias cuando hace falta, pero usan arreglos enteros de tamaño fijo para acumular con rapidez. A pesar de esas diferencias de ingeniería, los tres programas realizan la misma matriz de transferencia.
Para anchura \(W\), el espacio de estados almacenados tiene tamaño \(2^{2W}=4^W\). En el Problema 161, \(W=9\), así que hay como máximo \(2^{18}=262{,}144\) perfiles posibles, aunque muchos nunca llegan a ser alcanzables.
Para cada perfil activo, la generación de transiciones es una DFS acotada sobre a lo sumo \(W\) columnas, con ramificación puramente local procedente de las seis colocaciones del triominó y del caso de salto. Por ello, el método es exponencial en la dimensión estrecha \(W\), pero lineal en la altura una vez que las transferencias están disponibles. Ese es precisamente el escenario en el que el profile DP funciona bien.
Las implementaciones con arreglos densos usan \(O(2^{2W})\) memoria para la capa actual y la siguiente. La versión de Python mantiene menos perfiles simultáneamente, pero sigue recorriendo el mismo grafo de estados subyacente.
本题要求计算：用 triomino 铺满一个 \(9\times12\) 矩形，一共有多少种不同方案。实现中允许全部六种朝向，也就是两种直条 tromino 和四种 \(L\) 形 tromino。
由于每块骨牌恰好覆盖 3 个方格，最直接的必要条件是 \(3 \mid 9\cdot12\)，而这里显然满足。真正困难的地方不在于“能否铺满”，而在于“如何精确计数”，因为某一行里的局部选择会把约束传到下一行，甚至下下行。
把整个矩形按从上到下的顺序处理。在任意时刻，动态规划只记录前沿中连续两行里哪些格子已经被占用。某一位为 1，表示这个格子已经被之前选定的骨牌覆盖；某一位为 0，表示这个格子还没有完成，必须依靠继续向下延伸的骨牌来补上。
因此，对宽度 \(W\) 来说，真正存储的状态只需要 \(2W\) 个二进制位。进行一次状态转移时，会在这两行下面临时接上一条新的第三行，所以局部搜索实际操作的是一个临时的 \(3W\) 位掩码。搜索结束后，最上面那一行会被丢弃，剩下的两行就构成下一步保存的轮廓。
这正是压缩的核心：完整铺法的全局信息极其庞大，但所有未来决策真正依赖的，只是接下来两行的占用模式。
递归搜索会从右向左扫描新接上的最底下一行。对当前列 \(c\) 来说，每一个新放入的骨牌都归属于 \((r+2,c)\) 这个格子，也就是它在三行窗口中的最低格。相对于三行 \(r,r+1,r+2\)，六种允许的形状是
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
它们恰好对应两种直 triomino 和四种 \(L\) 形 triomino。除此之外，深度优先搜索还有一个“跳过”分支：如果 \((r+2,c)\) 已经被更右侧某次放置覆盖，那么当前只需继续向左扫描，不必再新放一块骨牌。
记 \(S\) 为所有 \(2W\) 位轮廓状态的集合，记 \(T(s,t)\) 为从存储状态 \(s\) 出发、只在新加入的那一行上引入“最低格”的骨牌、最后得到下一状态 \(t\) 的局部补全方案数。
如果 \(F_k(s)\) 表示处理完前 \(k\) 行之后处于状态 \(s\) 的方案数，那么逐行递推就是
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$$
这里最关键的合法性条件是：局部搜索结束时，三行中最老的那一行必须已经完全填满。因为后续任何新骨牌都不可能再伸到那么高，所以如果那一行还留有空格，这个部分铺法就不可能扩展成完整解。
取 \(W=4\)。假设当前存储的轮廓是 1111 | 0110：较老的那一行已经全满，而下一行只有中间两个格子已被覆盖。新接上的第三行初始为 0000。
现在在左侧放一个 \(L\) 形 triomino，覆盖 \((r+1,0),(r+2,0),(r+2,1)\)；再在右侧放一个镜像的 \(L\) 形 triomino，覆盖 \((r+1,3),(r+2,2),(r+2,3)\)。放完以后，三行就都变成 1111、1111、1111。
于是这个局部补全是合法的，删去最老的那一行之后，下一状态又回到 1111 | 1111。这个例子说明：第二条前沿行里暂时存在空位并不意味着失败，因为它完全可能由“最低格落在新行里”的骨牌在下一步补齐。
记 \(\mathbf{1}\) 为“两条存储行全部填满”的轮廓。动态规划从 \(F_0(\mathbf{1})=1\) 开始。它编码的是上边界条件：任何骨牌都不允许伸出矩形顶部，所以矩形上方那两条虚拟行被视为已经封闭。
当全部 \(H\) 条真实行都处理完成后，答案就是 \(F_H(\mathbf{1})\)。最终回到全满轮廓，等价于说明没有任何未完成的 triomino 伸出矩形底边。对于 Problem 161，程序计算的是 \(W=9\)、\(H=12\) 这一实例。
C++、Python 和 Java 三个实现执行的是同一个逐行动态规划。一个轮廓状态被编码成两条前沿行的位掩码。C++ 与 Java 使用按掩码直接索引的稠密数组；Python 则用字典仅保存当前真正可达的状态。
每一层 DP 对应“又处理完了一行”。对于每个活跃状态，实现都会枚举三行窗口的全部合法局部补全，统计每个下一状态出现了多少次，再把这个重数加入下一层。
局部枚举本质上是对新行各列做一次深度优先搜索。只要所需格子仍为空闲、涉及的列也没有越界，就尝试上面的六种几何放置方式。搜索到最左端时，只有在最老的那条前沿行已经全部占满的情况下，这个转移才被接受；随后丢弃那一行，并把剩余掩码整体下移一行，得到下一状态。
Python 实现会缓存每个已经探索过的轮廓所对应的转移列表。C++ 与 Java 则按需重新生成这些转移，但用固定大小的整数数组来高效累加。虽然工程细节不同，三份程序实际实现的是同一个转移矩阵。
对宽度 \(W\) 而言，存储状态空间的规模是 \(2^{2W}=4^W\)。在 Problem 161 中 \(W=9\)，因此理论上最多有 \(2^{18}=262{,}144\) 个轮廓，当然其中很多状态永远不会被访问到。
对每个活跃状态，转移生成都是一个至多跨越 \(W\) 列的有界 DFS，分支只来自六种 triomino 放置和一个跳过分支。因此，这个方法在较窄维度 \(W\) 上是指数级的，但在转移可用之后对高度 \(H\) 只是线性的。这正是 profile DP 最适合发挥作用的场景。
使用稠密数组的实现需要 \(O(2^{2W})\) 空间来保存当前层和下一层。Python 同时保留的状态较少，但它遍历的底层状态图与另外两种实现完全相同。
Нужно подсчитать число разбиений прямоугольника \(9\times12\) триомино. Реализации допускают все шесть ориентаций: два прямых тромино и четыре \(L\)-образных.
Так как каждая плитка покрывает ровно три клетки, базовое необходимое условие \(3 \mid 9\cdot12\) выполнено. Значит, задача состоит не в проверке существования разбиения, а в точном подсчёте. Прямой перебор непрактичен, потому что локальное решение может создавать ограничения на одну или две строки ниже.
Будем обрабатывать доску сверху вниз. В каждый момент динамика хранит информацию о том, какие клетки уже заняты в двух последовательных граничных строках. Бит 1 означает, что клетка уже покрыта ранее выбранными фигурами; бит 0 означает, что эту клетку ещё предстоит закрыть фигурой, уходящей ниже.
Поэтому сохраняемое состояние при ширине \(W\) требует только \(2W\) битов. Во время одного перехода под этими двумя строками временно добавляется свежая третья строка, так что локальный поиск работает с маской длины \(3W\). Когда поиск закончен, самая старая строка отбрасывается, а две оставшиеся образуют следующий сохраняемый профиль.
Именно здесь возникает сжатие состояния: полная укладка огромна, но все будущие решения зависят только от рисунка занятости двух следующих строк.
Рекурсивный поиск проходит новую нижнюю строку справа налево. Для текущего столбца \(c\) каждая новая фигура привязывается к клетке \((r+2,c)\), то есть к своей нижней клетке внутри окна из трёх строк. Относительно строк \(r,r+1,r+2\) допустимы шесть форм
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
Это ровно два прямых триомино и четыре поворота \(L\)-триомино. Кроме того, в DFS есть ветвь «пропустить»: если клетка \((r+2,c)\) уже покрыта фигурой, выбранной правее, поиск просто сдвигается влево.
Пусть \(S\) обозначает множество всех \(2W\)-битных профилей, а \(T(s,t)\) обозначает число локальных достроек, которые стартуют из сохранённого профиля \(s\), добавляют фигуры с нижней клеткой в новой строке и заканчиваются следующим профилем \(t\).
Если \(F_k(s)\) обозначает число способов обработать первые \(k\) строк доски и закончить профилем \(s\), то переход между строками имеет вид
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$$
Ключевое условие корректности такое: к концу локального поиска самая старая из трёх строк должна быть заполнена полностью. Никакая будущая фигура уже не сможет дотянуться так высоко, поэтому любая оставшаяся там дырка делает частичную укладку невозможной.
Возьмём \(W=4\). Пусть текущий сохранённый профиль равен 1111 | 0110: более старая строка уже заполнена, а в следующей покрыты только две центральные клетки. Вновь добавленная третья строка начинается как 0000.
Теперь поставим слева \(L\)-триомино на клетки \((r+1,0),(r+2,0),(r+2,1)\), а справа зеркальное \(L\)-триомино на клетки \((r+1,3),(r+2,2),(r+2,3)\). После этих двух размещений три строки становятся равны 1111, 1111, 1111.
Значит, такая локальная достройка допустима, и после удаления самой старой строки следующий сохранённый профиль снова равен 1111 | 1111. Этот пример показывает, почему дырка во второй граничной строке ещё не означает провал: её может закрыть фигура, чья нижняя клетка находится в новой строке.
Обозначим через \(\mathbf{1}\) профиль, в котором обе сохраняемые строки полностью заполнены. Динамика стартует из состояния \(F_0(\mathbf{1})=1\). Это кодирует верхнюю границу: никакая фигура не может выступать выше прямоугольника, поэтому две фиктивные строки над доской считаются уже закрытыми.
После обработки всех \(H\) реальных строк ответом будет \(F_H(\mathbf{1})\). Возврат к полному профилю в конце означает, что никакое незаконченное триомино не выступает ниже нижней границы. В Problem 161 программы вычисляют это для \(W=9\) и \(H=12\).
Реализации на C++, Python и Java выполняют одну и ту же построчную динамику. Профиль кодируется битовой маской для двух граничных строк. Версии на C++ и Java используют плотные массивы, индексируемые этой маской, а версия на Python хранит в словарях только реально достижимые в данный момент маски.
Каждый слой DP соответствует ещё одной обработанной строке. Для каждого активного профиля реализация перечисляет все допустимые локальные достройки окна из трёх строк, считает, сколько раз возникает каждый следующий профиль, и добавляет эту кратность в следующий слой.
Локальный перебор представляет собой поиск в глубину по столбцам новой строки. Он пробует шесть перечисленных выше геометрических размещений, если нужные клетки ещё свободны и все задействованные столбцы остаются внутри доски. Когда поиск доходит до левого края, переход принимается только в том случае, если самая старая граничная строка заполнена полностью; после этого она удаляется, а оставшаяся маска сдвигается вниз на одну строку.
Реализация на Python кэширует список переходов для каждого уже исследованного профиля. Реализации на C++ и Java пересчитывают эти переходы по мере необходимости, но пользуются массивами фиксированного размера для быстрого накопления. При всех инженерных различиях все три программы реализуют одну и ту же матрицу переходов.
При ширине \(W\) размер пространства сохраняемых состояний равен \(2^{2W}=4^W\). В Problem 161 при \(W=9\) это даёт максимум \(2^{18}=262{,}144\) возможных профилей, хотя многие из них никогда не достигаются.
Для каждого активного профиля генерация переходов представляет собой ограниченный DFS по не более чем \(W\) столбцам, где ветвление возникает только из шести размещений триомино и случая пропуска. Поэтому метод экспоненциален по узкому измерению \(W\), но линеен по высоте после того, как переходы доступны. Именно в таком режиме профильная динамика особенно эффективна.
Плотные реализации используют \(O(2^{2W})\) памяти для текущего и следующего слоя. Версия на Python одновременно хранит меньше профилей, но движется по тому же базовому графу состояний.
المطلوب هو عدّ عدد الطرق التي يمكن بها تبليط مستطيل \(9\times12\) بقطع triomino. التنفيذات تسمح بجميع الاتجاهات الستة: قطعتان مستقيمتان وأربع قطع على شكل \(L\).
بما أنّ كل قطعة تغطي ثلاث خلايا بالضبط، فإن الشرط الضروري الأول هو \(3 \mid 9\cdot12\)، وهو متحقق هنا. لذلك فالصعوبة ليست في وجود تبليط من عدمه، بل في العدّ الدقيق، لأن قرارًا محليًا في صف واحد قد يفرض قيودًا على الصف التالي أو الذي بعده.
نُعالج اللوح من الأعلى إلى الأسفل. في كل لحظة تحتفظ البرمجة الديناميكية بمعلومة الخلايا المشغولة في صفّين متتاليين على الواجهة. القيمة 1 في البت تعني أن الخلية مغطاة بالفعل بقطعة اختيرت سابقًا، والقيمة 0 تعني أن هذه الخلية ما زالت تحتاج إلى قطعة تمتد أكثر نحو الأسفل.
لهذا السبب لا تحتاج الحالة المخزنة إلا إلى \(2W\) بت عندما يكون العرض \(W\). أثناء انتقال واحد نضيف صفًا ثالثًا جديدًا تحت هذين الصفين، ولذلك تعمل عملية البحث المحلية على قناع مؤقت طوله \(3W\) بت. وعندما ينتهي هذا البحث يُحذف الصف الأقدم، ويكوّن الصفان الباقيان الملف التالي.
هذه هي فكرة الضغط الأساسية: التبليط الكامل كبير جدًا، لكن كل القرارات المستقبلية لا تعتمد إلا على نمط الإشغال في الصفين التاليين.
البحث التراجعي يمر على الصف السفلي الجديد من اليمين إلى اليسار. عند العمود الحالي \(c\)، تُنسب كل قطعة جديدة إلى الخلية \((r+2,c)\)، أي إلى أخفض خلية لها داخل نافذة الصفوف الثلاثة. وبالنسبة إلى الصفوف \(r,r+1,r+2\)، فإن الأشكال الستة المسموح بها هي
$$\begin{aligned} &\{(r,c),(r+1,c),(r+2,c)\},\\ &\{(r+2,c-2),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+2,c-1),(r+2,c)\},\\ &\{(r+1,c-1),(r+1,c),(r+2,c)\},\\ &\{(r+1,c),(r+1,c+1),(r+2,c)\}. \end{aligned}$$
وهذه هي بالضبط القطعتان المستقيمتان وأربع دورانات لقطعة \(L\). وهناك أيضًا فرع «تخطَّ» في DFS: إذا كانت الخلية \((r+2,c)\) قد غُطّيت بالفعل بواسطة قطعة اختيرت في عمود أكبر، فإن البحث يكتفي بالانتقال يسارًا.
لتكن \(S\) مجموعة جميع الملفات ذات \(2W\) بت، ولتكن \(T(s,t)\) عدد الإكمالات المحلية التي تبدأ من الملف المخزن \(s\)، ثم تضيف قطعًا تكون أخفض خلاياها في الصف الجديد، وتنتهي عند الملف التالي \(t\).
إذا كان \(F_k(s)\) يمثل عدد الطرق لمعالجة أول \(k\) صفوف من اللوح والانتهاء بالملف \(s\)، فإن انتقال الصفوف يكتب على الصورة
$$F_{k+1}(t)=\sum_{s\in S} F_k(s)\,T(s,t).$$
شرط الصحة الحاسم هو أن الصف الأقدم من بين الصفوف الثلاثة يجب أن يكون ممتلئًا بالكامل عند نهاية البحث المحلي. فلا توجد قطعة لاحقة يمكنها أن تصل إلى ذلك الارتفاع، وأي فراغ متبقٍّ هناك يجعل التبليط الجزئي غير قابل للإكمال.
خذ \(W=4\). افترض أن الملف الحالي هو 1111 | 0110: الصف الأقدم مكتمل، بينما الصف التالي لا يحتوي إلا على الخليتين الوسطيتين المغطاتين. الصف الثالث المضاف حديثًا يبدأ على الصورة 0000.
الآن ضع قطعة \(L\) على اليسار تغطي \((r+1,0),(r+2,0),(r+2,1)\)، ثم ضع قطعة \(L\) معكوسة على اليمين تغطي \((r+1,3),(r+2,2),(r+2,3)\). بعد هاتين الإضافتين تصبح الصفوف الثلاثة هي 1111 و1111 و1111.
إذًا فهذا الإكمال المحلي صالح، وبعد حذف الصف الأقدم يعود الملف التالي إلى 1111 | 1111. يوضح هذا المثال لماذا لا يكون الفراغ في الصف الثاني من الواجهة تناقضًا مباشرًا: فقد يُستكمل لاحقًا بواسطة قطعة تقع أخفض خلاياها في الصف الجديد.
لنرمز بـ \(\mathbf{1}\) إلى الملف الذي يكون فيه الصفان المخزنان ممتلئين تمامًا. تبدأ البرمجة الديناميكية من \(F_0(\mathbf{1})=1\). وهذا يشفّر الحافة العلوية: لا يُسمح لأي قطعة أن تخرج فوق المستطيل، ولذلك يُعامل الصفان التخيليان فوق اللوح على أنهما مغلقان سلفًا.
بعد معالجة جميع الصفوف الحقيقية وعددها \(H\)، تكون الإجابة هي \(F_H(\mathbf{1})\). والانتهاء عند الملف الممتلئ يعني أنه لا توجد قطعة triomino غير مكتملة تخرج أسفل الحافة السفلية. في Problem 161 تُقيَّم هذه الخطة عند \(W=9\) و\(H=12\).
تنفذ تطبيقات C++ وPython وJava البرمجة الديناميكية نفسها صفًا بعد صف. يُمثَّل الملف بقناع بتات لصفَّي الواجهة. نسختا C++ وJava تستعملان مصفوفات كثيفة مفهرسة مباشرة بهذا القناع، بينما تحتفظ نسخة Python في القواميس فقط بالأقنعة القابلة للوصول في تلك اللحظة.
كل طبقة من طبقات DP تمثل صفًا إضافيًا تمّت معالجته. ولكل ملف نشط، يقوم التنفيذ بتعداد جميع الإكمالات المحلية الصحيحة لنافذة الصفوف الثلاثة، ويحسب عدد مرات ظهور كل ملف تالٍ، ثم يضيف هذا التعدد إلى الطبقة التالية.
التعداد المحلي هو بحث بعمق أول على أعمدة الصف الجديد. يحاول الأوضاع الهندسية الستة السابقة كلما كانت الخلايا المطلوبة ما تزال فارغة وكانت الأعمدة الداخلة في الوضع داخل حدود اللوح. وعندما يصل البحث إلى الطرف الأيسر، لا يُقبل الانتقال إلا إذا كان الصف الأقدم من صفوف الواجهة ممتلئًا بالكامل؛ ثم يُحذف هذا الصف ويُزاح القناع المتبقي صفًا واحدًا إلى الأسفل للحصول على الملف التالي.
تنفذ نسخة Python تخزينًا مؤقتًا لقائمة الانتقالات الخاصة بكل ملف سبق استكشافه. أما نسختا C++ وJava فتعيدان توليد هذه الانتقالات عند الحاجة، لكنهما تستخدمان مصفوفات صحيحة ثابتة الحجم من أجل التجميع السريع. وعلى الرغم من اختلاف التفاصيل الهندسية، فإن البرامج الثلاثة تحقق مصفوفة الانتقال نفسها.
عند العرض \(W\)، يكون حجم فضاء الحالات المخزنة هو \(2^{2W}=4^W\). وفي Problem 161 حيث \(W=9\)، نحصل نظريًا على حد أقصى مقداره \(2^{18}=262{,}144\) ملفًا ممكنًا، مع أن عددًا كبيرًا منها لا يصبح قابلًا للوصول أبدًا.
وبالنسبة إلى كل ملف نشط، فإن توليد الانتقالات هو DFS محدود على ما لا يزيد على \(W\) أعمدة، وتأتي التفرعات فقط من الأوضاع الستة للـ triomino ومن حالة التخطي. لذلك فالطريقة أسية في البعد الضيق \(W\)، لكنها خطية في الارتفاع عندما تكون الانتقالات متاحة. وهذا بالضبط هو المجال الذي تكون فيه profile DP فعالة.
تستخدم النسخ المعتمدة على المصفوفات الكثيفة ذاكرة مقدارها \(O(2^{2W})\) للطبقة الحالية والطبقة التالية. أما نسخة Python فتحفظ عددًا أقل من الملفات في اللحظة نفسها، لكنها تتحرك فوق الرسم البياني نفسه للحالات.