We count lattice sculptures made of \(n\) unit blocks, attached to a single support at \((0,0)\). The support lies on the vertical axis, so mechanical balance means the center of mass must remain above that axis. Sculptures are considered up to mirror reflection \((x,y)\mapsto(-x,y)\).
The support itself is not counted as a block. The first real block is forced to be \((0,1)\), and every other block lies in the half-plane \(y>0\). Connectivity is by 4-neighborhood adjacency.
If a block sits at \((x,y)\), any path from the support to that block needs at least \(y+|x|\) steps through occupied cells. Since only \(n\) blocks are available, we must have
$$y+|x|\le n.$$
Therefore every possible block lies inside the finite diamond
$$0<y\le n,\qquad |x|\le n-y.$$
This is exactly the domain precomputed in buildDomain().
Each block has equal mass, so the horizontal moment about the support axis is proportional to the sum of the \(x\)-coordinates of all occupied blocks. Hence balance is equivalent to
$$\sum_{(x,y)\in S} x = 0.$$
The DFS maintains this as an integer sumx. Terminal states are accepted only when sumx == 0.
The difficulty is not checking balance; it is enumerating every connected sculpture exactly once. The solver uses a Redelmeier-style canonical DFS.
Occupied set. occ stores the support and currently chosen blocks.
Frontier. U stores block cells adjacent to the occupied set that are still available to be
added.
Forbidden set. forb stores cells that this branch has decided not to use.
At each step the algorithm removes one frontier cell \(u\), recursively explores the branch that includes it, then marks \(u\) as forbidden before continuing. This single decision order is what prevents duplicates from different insertion orders.
After the mandatory first block \((0,1)\), the initial frontier is just
$$\{(-1,1),(1,1),(0,2)\}.$$
If one branch chooses not to use \((1,1)\), that cell becomes forbidden in that branch, so the same final sculpture cannot later be rebuilt by first taking \((0,2)\) and then returning to \((1,1)\).
Suppose the current horizontal sum is sumx and \(r\) blocks remain to be placed. Even in the most
favorable continuation, the total correction we can still apply is limited.
The code builds a list of all positive-domain \(x\)-coordinates, sorts it in descending order, and defines
$$B(r)=\text{sum of the }r\text{ largest }x\text{-values in the domain}.$$
Because the domain is symmetric, \(B(r)\) is also the largest possible magnitude of a correction in the negative direction. Therefore, if
$$|\text{sumx}| > B(r),$$
then not even an unrealistically optimal choice of the remaining blocks could restore balance. The branch is safely pruned.
This bound ignores connectivity and already-occupied cells, so it is optimistic. That is exactly why it is safe: if even the optimistic bound cannot recover, the real branch certainly cannot.
The DFS counts anchored sculptures in a fixed coordinate system, so a sculpture and its mirror are both generated unless the shape is itself symmetric.
Let
$$N=\text{all balanced anchored sculptures},\qquad S=\text{those fixed by }(x,y)\mapsto(-x,y).$$
The symmetry group has two elements: identity and reflection. Burnside's lemma gives the number of distinct sculptures up to reflection as
$$\frac{N+S}{2}.$$
The method isSymmetric() checks exactly whether every occupied cell is paired with its mirror image.
A simple balanced sculpture for \(n=6\) is
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}.$$
It is connected, symmetric, and satisfies
$$0+0+0+0-1+1=0.$$
The source includes several validation checkpoints:
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
These are especially useful because they verify the canonical generation, pruning, and symmetry quotient all at once.
Domain construction. buildDomain() creates all cells in the diamond
\(|x|\le n-y\), \(0\le y\le n\), precomputes 4-neighbors, and stores the mirror index of each cell.
Initial state. initialState() forbids all other ground cells \(y=0\), places the support
and the mandatory block \((0,1)\), and initializes the first frontier.
Main DFS. dfs() performs the include/forbid recursion, updates sumx, and
applies the maxCorr pruning test before exploring deeper.
Symmetry count. At a terminal state with exactly \(n\) blocks and sumx == 0, the code
increments total and, if mirrored occupancy also holds, increments sym.
Thread splitting. generateTasks() expands the top few levels of the search tree into
independent tasks, and worker threads process those tasks in parallel. This changes performance, not the underlying
mathematics.
The worst-case search is exponential in \(n\), as is standard for polyomino-type enumeration. The practical runtime is much smaller because three reductions work together:
1. canonical frontier generation removes permutation duplicates;
2. forbidden cells prevent the same connected set from reappearing in another order;
3. the balance bound cuts branches that cannot possibly return to \(\sum x=0\).
Memory usage is \(O(n+|U|)\) along each recursion path, with additional storage for the precomputed domain and mirror tables.
Gezählt werden Gitter-Skulpturen aus \(n\) Einheitsblöcken, die an einem einzelnen Stützpunkt \((0,0)\) befestigt sind. Mechanisches Gleichgewicht bedeutet, dass der Schwerpunkt über der vertikalen Achse der Stütze bleibt. Spiegelbilder \((x,y)\mapsto(-x,y)\) gelten als identisch.
Die Stütze selbst zählt nicht als Block. Der erste echte Block ist fest \((0,1)\), und alle weiteren Blöcke liegen im Halbebenenbereich \(y>0\). Zusammenhang gilt über 4-Nachbarschaft.
Liegt ein Block bei \((x,y)\), dann benötigt jeder Weg von der Stütze zu diesem Block mindestens \(y+|x|\) Schritte durch besetzte Zellen. Bei insgesamt nur \(n\) Blöcken muss also gelten
$$y+|x|\le n.$$
Daher liegen alle möglichen Blöcke im endlichen Diamanten
$$0<y\le n,\qquad |x|\le n-y.$$
Genau diesen Bereich baut buildDomain() vorab auf.
Alle Blöcke haben dieselbe Masse. Das horizontale Drehmoment um die Stützachse ist daher proportional zur Summe der \(x\)-Koordinaten aller besetzten Blöcke. Also ist Gleichgewicht äquivalent zu
$$\sum_{(x,y)\in S} x = 0.$$
Die Suche verwaltet diesen Wert als Ganzzahl sumx. Endzustände werden nur akzeptiert, wenn
sumx == 0 gilt.
Die eigentliche Schwierigkeit liegt nicht in der Balanceprüfung, sondern darin, jede zusammenhängende Skulptur genau einmal zu erzeugen. Der Solver verwendet dafür eine Redelmeier-artige kanonische DFS.
Belegte Zellen. occ enthält die Stütze und die bisher gewählten Blöcke.
Frontier. U enthält benachbarte Blockzellen, die als Nächstes hinzugefügt werden könnten.
Forbidden. forb markiert Zellen, die in diesem Zweig bewusst nicht mehr benutzt werden
dürfen.
In jedem Schritt nimmt der Algorithmus eine Frontier-Zelle \(u\), verfolgt rekursiv den Zweig mit \(u\), und markiert \(u\) danach als verboten, bevor der nächste Zweig betrachtet wird. Genau diese feste Entscheidungsreihenfolge verhindert Mehrfacherzeugungen durch verschiedene Einfügeordnungen.
Nach dem erzwungenen ersten Block \((0,1)\) lautet die anfängliche Frontier
$$\{(-1,1),(1,1),(0,2)\}.$$
Wenn ein Zweig entscheidet, \((1,1)\) nicht zu nehmen, wird diese Zelle dort verboten. Dieselbe Endskulptur kann daher nicht später noch einmal über erst \((0,2)\), dann \((1,1)\) aufgebaut werden.
Sei die aktuelle horizontale Summe sumx, und es verbleiben \(r\) Blöcke. Selbst im günstigsten Fall ist
die noch mögliche Korrektur begrenzt.
Der Code sammelt alle positiven \(x\)-Werte des Domänenbereichs, sortiert sie absteigend und definiert
$$B(r)=\text{Summe der }r\text{ größten }x\text{-Werte der Domäne}.$$
Wegen der Links-Rechts-Symmetrie der Domäne ist \(B(r)\) zugleich die größte mögliche Korrektur im negativen Sinn. Sobald also
$$|\text{sumx}| > B(r),$$
kann selbst eine unrealistisch optimale Wahl der verbleibenden Blöcke das Gleichgewicht nicht mehr herstellen. Der Ast wird sicher abgeschnitten.
Die Schranke ignoriert Zusammenhang und bereits belegte Zellen und ist deshalb optimistisch. Genau dadurch ist sie sicher: Wenn schon die optimistische Schranke nicht reicht, kann der reale Ast erst recht nicht funktionieren.
Die DFS zählt verankerte Skulpturen in einem festen Koordinatensystem. Eine Skulptur und ihr Spiegelbild werden daher beide erzeugt, sofern die Form nicht selbst spiegelsymmetrisch ist.
Seien
$$N=\text{alle balancierten verankerten Skulpturen},\qquad S=\text{die unter }(x,y)\mapsto(-x,y)\text{ fixen}. $$
Die Symmetriegruppe hat zwei Elemente: Identität und Spiegelung. Nach Burnside ergibt sich die Anzahl der verschiedenen Skulpturen bis auf Spiegelung zu
$$\frac{N+S}{2}.$$
isSymmetric() prüft genau, ob jede belegte Zelle zusammen mit ihrer Spiegelzelle vorkommt.
Eine einfache balancierte Skulptur für \(n=6\) ist
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}.$$
Sie ist zusammenhängend, spiegelsymmetrisch und erfüllt
$$0+0+0+0-1+1=0.$$
Die Quelle enthält mehrere Validierungswerte:
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
Diese prüfen kanonische Erzeugung, Pruning und Spiegelquotient zugleich.
Domänenaufbau. buildDomain() erzeugt alle Zellen im Diamanten
\(|x|\le n-y\), \(0\le y\le n\), berechnet 4-Nachbarn und speichert zu jeder Zelle den Spiegelindex.
Initialzustand. initialState() verbietet alle anderen Bodenzellen \(y=0\), setzt die
Stütze und den Pflichtblock \((0,1)\), und initialisiert die erste Frontier.
Haupt-DFS. dfs() führt die Include/Forbidden-Rekursion aus, aktualisiert
sumx und prüft vor tieferem Abstieg die Schranke maxCorr.
Symmetriezählung. Bei einem Endzustand mit genau \(n\) Blöcken und sumx == 0 werden
total und bei Bedarf auch sym erhöht.
Thread-Aufteilung. generateTasks() entfaltet die oberen Ebenen des Suchbaums in
unabhängige Aufgaben, die danach von Threads bearbeitet werden. Das ändert nur die Laufzeit, nicht die Mathematik.
Wie bei Polyomino-Enumeration üblich ist die Worst-Case-Suche exponentiell in \(n\). Praktisch wird der Suchbaum aber stark verkleinert durch drei Ideen:
1. kanonische Frontier-Erzeugung entfernt Permutationsduplikate;
2. verbotene Zellen verhindern dieselbe Form in anderer Erzeugungsreihenfolge;
3. die Balance-Schranke schneidet Äste ab, die niemals zu \(\sum x=0\) zurückkehren können.
Der Speicherbedarf pro Rekursionspfad ist \(O(n+|U|)\), hinzu kommen die vorab berechnete Domäne und die Spiegeltabellen.
\((0,0)\) destek noktasına bağlı \(n\) adet birim bloktan oluşan kafes heykeller sayılır. Denge şartı, ağırlık merkezinin destek ekseni olan \(x=0\) doğrusu üzerinde kalmasıdır. Aynadaki görüntüler \((x,y)\mapsto(-x,y)\) aynı heykel kabul edilir.
Destek noktası blok sayılmaz. İlk gerçek blok zorunlu olarak \((0,1)\)'dir ve diğer bütün bloklar \(y>0\) yarı düzlemindedir. Bağlılık 4-komşuluk ile tanımlanır.
Bir blok \((x,y)\) noktasındaysa, destekten o bloğa giden herhangi bir yol en az \(y+|x|\) adım gerektirir. Toplam yalnızca \(n\) blok olduğundan
$$y+|x|\le n$$
olmak zorundadır. Dolayısıyla bütün aday bloklar sonlu elmas bölgesi içinde kalır:
$$0<y\le n,\qquad |x|\le n-y.$$
buildDomain() tam olarak bu bölgeyi önceden kurar.
Tüm blokların kütlesi eşit olduğundan, destek ekseni etrafındaki yatay moment blokların \(x\)-koordinatları toplamıyla orantılıdır. Bu yüzden denge koşulu
$$\sum_{(x,y)\in S} x = 0$$
şeklindedir. DFS bu değeri sumx olarak taşır ve yalnızca sumx == 0 olan son durumları kabul
eder.
Zor olan dengeyi kontrol etmek değil, her bağlı heykeli tam bir kez üretmektir. Çözüm Redelmeier tarzı kanonik bir DFS kullanır.
Dolu küme. occ, desteği ve seçilmiş blokları tutar.
Frontier. U, dolu kümeye komşu olup sıradaki adımda eklenebilecek hücreleri tutar.
Forbidden. forb, o dalda artık kullanılamayacak hücreleri işaretler.
Her adımda frontier'den bir hücre \(u\) çekilir, önce \(u\)'yu içeren dal gezilir, sonra \(u\) forbidden olarak işaretlenip diğer dallara geçilir. Aynı şeklin farklı ekleme sıralarıyla ikinci kez oluşmamasını sağlayan şey tam bu karar sırasıdır.
Zorunlu ilk blok \((0,1)\)'den sonra ilk frontier
$$\{(-1,1),(1,1),(0,2)\}$$
olur. Bir dal \((1,1)\)'i kullanmamaya karar verirse, o hücre o dal için forbidden olur; böylece önce \((0,2)\)'yi alıp sonra \((1,1)\)'e dönerek aynı son heykel tekrar üretilemez.
Mevcut yatay toplam sumx ve kalan blok sayısı \(r\) olsun. En iyimser devamda bile yapılabilecek düzeltme
sınırlıdır.
Kod, domain içindeki tüm pozitif \(x\) değerlerini toplayıp azalan sırada dizer ve
$$B(r)=\text{domain içindeki en büyük }r\text{ adet }x\text{ değerinin toplamı}$$
şeklinde bir üst sınır kurar. Domain simetrik olduğu için aynı sınır negatif yönde de geçerlidir. Bu nedenle eğer
$$|\text{sumx}| > B(r)$$
ise, kalan bloklar en iyimser biçimde bile seçilse dengeye dönmek imkansızdır. Dal güvenle budanır.
Bu sınır bağlılığı ve daha önce doldurulmuş hücreleri dikkate almaz; yani bilerek iyimserdir. Güvenli olmasının sebebi de budur: iyimser sınır yetmiyorsa, gerçek dal hiç yetmez.
DFS, sabit bir koordinat sisteminde destekli heykelleri sayar. Bu yüzden bir heykel ile ayna görüntüsü, şekil zaten simetrik değilse ayrı ayrı üretilir.
Şimdi
$$N=\text{tüm dengeli destekli heykeller},\qquad S=\text{ayna altında sabit kalanlar}$$
olsun. Simetri grubu iki elemanlıdır: özdeşlik ve yansıma. Burnside lemmasına göre aynaya göre ayırt edilen gerçek sayı
$$\frac{N+S}{2}$$
olur. isSymmetric() tam olarak her dolu hücrenin ayna eşinin de dolu olup olmadığını kontrol eder.
\(n=6\) için basit bir dengeli heykel
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}$$
şeklindedir. Bu yapı bağlıdır, ayna simetriktir ve
$$0+0+0+0-1+1=0$$
eşitliğini sağlar. Kaynak kod şu doğrulama değerlerini kullanır:
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
Bunlar kanonik üretim, budama ve ayna düzeltmesini birlikte test eder.
Domain kurulumu. buildDomain(), \(|x|\le n-y\), \(0\le y\le n\) elmasını kurar;
4-komşuları ve her hücrenin ayna indeksini önceden hesaplar.
Başlangıç durumu. initialState(), diğer tüm yer hücrelerini \(y=0\) forbidden yapar,
desteği ve zorunlu blok \((0,1)\)'i yerleştirir, ilk frontier'i hazırlar.
Ana DFS. dfs() include/forbidden özyinelemesini yürütür, sumx değerini
günceller ve daha derine gitmeden önce maxCorr budamasını uygular.
Simetri sayımı. Tam \(n\) blok yerleşmiş ve sumx == 0 ise total artar;
ayrıca ayna koşulu da sağlanıyorsa sym artar.
İş parçacığına bölme. generateTasks(), ağacın üst birkaç seviyesini bağımsız görevlere
ayırır. Bu yalnızca performansı değiştirir; matematiksel sayım aynı kalır.
Polyomino benzeri sayım problemlerinde olduğu gibi en kötü durum araması \(n\)'e göre üstel büyür. Pratikte ise üç fikir arama ağacını ciddi biçimde küçültür:
1. kanonik frontier üretimi, sıra permütasyonlarından gelen tekrarları kaldırır;
2. forbidden hücreler, aynı bağlı kümenin başka sırayla yeniden kurulmasını engeller;
3. denge üst sınırı, \(\sum x=0\)'a dönemeyecek dalları erken keser.
Tek bir özyineleme yolu boyunca bellek kullanımı \(O(n+|U|)\) düzeyindedir; buna domain ve ayna tabloları da eklenir.
Se cuentan esculturas en rejilla formadas por \(n\) bloques unitarios, unidas a un soporte único en \((0,0)\). El equilibrio mecánico significa que el centro de masa debe quedar sobre el eje vertical del soporte. Dos esculturas reflejadas por \((x,y)\mapsto(-x,y)\) se consideran la misma.
El soporte no cuenta como bloque. El primer bloque real está forzado en \((0,1)\), y todos los demás cumplen \(y>0\). La conectividad es por vecindad de 4 direcciones.
Si un bloque está en \((x,y)\), cualquier camino desde el soporte hasta él necesita al menos \(y+|x|\) pasos por celdas ocupadas. Como solo hay \(n\) bloques disponibles, debe cumplirse
$$y+|x|\le n.$$
Por tanto, todos los bloques posibles están dentro del rombo finito
$$0<y\le n,\qquad |x|\le n-y.$$
Eso es exactamente lo que preconstruye buildDomain().
Todos los bloques tienen la misma masa, así que el momento horizontal respecto al eje del soporte es proporcional a la suma de las coordenadas \(x\). Por ello, la condición de equilibrio es
$$\sum_{(x,y)\in S} x = 0.$$
La DFS mantiene este valor en sumx y solo acepta estados terminales con sumx == 0.
La dificultad real no es comprobar el equilibrio, sino generar cada escultura conectada exactamente una vez. El programa usa una DFS canónica de estilo Redelmeier.
Ocupados. occ guarda el soporte y los bloques elegidos.
Frontera. U guarda las celdas vecinas a la figura actual que todavía pueden añadirse.
Prohibidos. forb guarda las celdas que esta rama ya decidió no usar.
En cada paso, el algoritmo toma una celda de la frontera \(u\), explora recursivamente la rama que la incluye y luego marca \(u\) como prohibida antes de continuar. Ese orden único de decisiones evita duplicados debidos a órdenes distintos de inserción.
Después del bloque obligatorio \((0,1)\), la frontera inicial es
$$\{(-1,1),(1,1),(0,2)\}.$$
Si una rama decide no usar \((1,1)\), esa celda pasa a ser prohibida, así que la misma figura final no puede reconstruirse más tarde tomando primero \((0,2)\) y luego regresando a \((1,1)\).
Supongamos que la suma horizontal actual es sumx y quedan \(r\) bloques por colocar. Incluso en la mejor
continuación imaginable, la corrección posible es limitada.
El código recoge todos los valores positivos de \(x\) del dominio, los ordena en forma descendente y define
$$B(r)=\text{la suma de los }r\text{ mayores valores de }x\text{ del dominio}.$$
Como el dominio es simétrico, \(B(r)\) también es la mayor corrección posible en sentido negativo. Por lo tanto, si
$$|\text{sumx}| > B(r),$$
ni siquiera una continuación irrealmente favorable podría devolver la suma a cero. La rama se poda con seguridad.
La cota ignora conectividad y celdas ya ocupadas, así que es optimista. Precisamente por eso es segura.
La DFS cuenta esculturas ancladas en un sistema de coordenadas fijo. Por tanto, una escultura y su reflejo aparecen ambas, salvo que la figura ya sea simétrica.
Sea
$$N=\text{todas las esculturas equilibradas ancladas},\qquad S=\text{las fijas por }(x,y)\mapsto(-x,y).$$
El grupo de simetría tiene dos elementos: identidad y reflexión. Por Burnside, el número real de esculturas distintas módulo espejo es
$$\frac{N+S}{2}.$$
isSymmetric() comprueba exactamente que cada celda ocupada tenga su pareja reflejada ocupada también.
Una escultura equilibrada simple para \(n=6\) es
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}.$$
Es conectada, simétrica y cumple
$$0+0+0+0-1+1=0.$$
El código incorpora estos puntos de control:
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
Esos valores verifican simultáneamente la generación canónica, la poda y el cociente por simetría.
Construcción del dominio. buildDomain() crea todas las celdas del rombo
\(|x|\le n-y\), \(0\le y\le n\), precomputando vecinos de 4 direcciones y el índice reflejado de cada celda.
Estado inicial. initialState() prohíbe las demás celdas del suelo \(y=0\), coloca el
soporte y el bloque obligatorio \((0,1)\), e inicializa la primera frontera.
DFS principal. dfs() ejecuta la recursión include/forbid, actualiza sumx y
aplica la poda maxCorr antes de seguir profundizando.
Conteo de simetría. En un estado terminal con exactamente \(n\) bloques y sumx == 0, el
programa incrementa total y, si la ocupación es simétrica, también sym.
División en tareas. generateTasks() expande los niveles superiores del árbol de búsqueda
para producir tareas independientes; después, varios hilos las procesan. Eso solo mejora el rendimiento.
Como en la enumeración de polióminos, el peor caso es exponencial en \(n\). En la práctica el árbol se reduce mucho gracias a tres ideas:
1. la generación canónica de la frontera elimina duplicados por permutación;
2. las celdas prohibidas impiden reconstruir la misma figura en otro orden;
3. la cota de equilibrio corta ramas que nunca podrán volver a \(\sum x=0\).
La memoria a lo largo de una rama es \(O(n+|U|)\), además de las tablas del dominio y de espejos.
我们要统计由 \(n\) 个单位方块组成、连接在支点 \((0,0)\) 上的格点雕塑。力学平衡意味着质心必须落在支撑轴 \(x=0\) 上。镜像变换 \((x,y)\mapsto(-x,y)\) 下等价的雕塑视为同一种。
支点本身不算方块。第一个真实方块固定为 \((0,1)\)，其余所有方块都满足 \(y>0\)。连通性采用 4 邻接。
若某个方块位于 \((x,y)\)，那么从支点走到该方块的任意路径，至少需要 \(y+|x|\) 步已占据单元。由于总共只有 \(n\) 个方块，因此必须满足
$$y+|x|\le n.$$
于是所有可能方块都落在有限菱形区域内：
$$0<y\le n,\qquad |x|\le n-y.$$
buildDomain() 预先构造的正是这个区域。
每个方块质量相同，因此相对于支撑轴的水平力矩与所有方块的 \(x\)-坐标和成正比。所以平衡条件等价于
$$\sum_{(x,y)\in S} x = 0.$$
DFS 用整数 sumx 维护这个值，只有在终止时 sumx == 0 的状态才被接受。
真正困难的地方不是检查平衡，而是保证每个连通雕塑只生成一次。这里使用的是 Redelmeier 风格的规范 DFS。
已占据集合。 occ 保存支点和当前选中的方块。
前沿集合。 U 保存与已占据区域相邻、仍可加入的方块单元。
禁止集合。 forb 保存当前分支已经决定不使用的单元。
每一步，算法从前沿中取出一个单元 \(u\)，先递归探索“包含 \(u\)”的分支，再把 \(u\) 标记为禁止后继续。正是这种唯 一决策顺序，消除了不同插入顺序带来的重复。
在强制加入 \((0,1)\) 之后，初始前沿正好是
$$\{(-1,1),(1,1),(0,2)\}.$$
如果某个分支决定不用 \((1,1)\)，那么它在该分支中就会进入 forbidden，所以同一个最终雕塑不能再通过“先加 \((0,2)\)，后回头加 \((1,1)\)”的顺序重新生成。
设当前水平和为 sumx，还剩 \(r\) 个方块未放。即便在最理想的延伸下，我们还能做出的修正量也是有限的。
代码收集所有正区域单元的 \(x\)-坐标并按降序排序，定义
$$B(r)=\text{区域中最大的 }r\text{ 个 }x\text{ 值之和}.$$
由于区域左右对称，\(B(r)\) 同时也是向负方向修正时可能达到的最大绝对值。因此，一旦
$$|\text{sumx}| > B(r),$$
那么即使剩余方块以不现实的最优方式摆放，也不可能把总和修回 0，当前分支就可以安全剪掉。
这个上界忽略了连通性和已占用单元，因此它是乐观的。也正因为它乐观，所以它是安全的。
DFS 在固定坐标系中统计锚定雕塑，因此除非图形本身对称，否则一个雕塑和它的镜像都会被枚举到。
设
$$N=\text{所有平衡的锚定雕塑},\qquad S=\text{在 }(x,y)\mapsto(-x,y)\text{ 下不变的雕塑}. $$
对称群只有两个元素：恒等与反射。由 Burnside 引理可知，按镜像合并后的真实数量为
$$\frac{N+S}{2}.$$
isSymmetric() 做的正是检查每个已占用单元的镜像是否也被占用。
当 \(n=6\) 时，一个简单的平衡雕塑是
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}.$$
它连通、镜像对称，并满足
$$0+0+0+0-1+1=0.$$
源码内置了若干校验点：
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
这些值会同时检验规范化生成、剪枝和镜像商的正确性。
区域构造。 buildDomain() 构造菱形区域 \(|x|\le n-y\), \(0\le y\le n\)，并预计算
4 邻接与每个单元的镜像下标。
初始状态。 initialState() 把其他所有地面单元 \(y=0\) 设为 forbidden，放入支点和
强制方块 \((0,1)\)，并初始化最初的 frontier。
主 DFS。 dfs() 执行 include/forbid 递归，更新 sumx，并在深入之前应用
maxCorr 剪枝。
对称计数。 当状态恰好有 \(n\) 个方块且 sumx == 0 时，代码增加 total；
如果镜像条件也成立，则增加 sym。
任务拆分。 generateTasks() 将搜索树上层切成独立任务，再交给多个线程处理。这只影响性能，
不改变数学计数方式。
和多连方枚举一样，最坏情况下搜索对 \(n\) 是指数级的。但实际搜索树会被三件事大幅压缩：
1. 规范化 frontier 生成消除了顺序排列导致的重复；
2. forbidden 集合阻止同一连通集合以不同顺序重建；
3. 平衡上界提前剪掉永远不可能回到 \(\sum x=0\) 的分支。
沿单条递归路径的内存开销约为 \(O(n+|U|)\)，外加预计算的区域与镜像表。
Нужно подсчитать решётчатые «скульптуры» из \(n\) единичных блоков, прикреплённые к опоре в точке \((0,0)\). Условие равновесия означает, что центр масс должен лежать над осью опоры \(x=0\). Конфигурации, переходящие друг в друга зеркальным отражением \((x,y)\mapsto(-x,y)\), считаются одинаковыми.
Сама опора блоком не считается. Первый настоящий блок фиксирован: \((0,1)\). Все остальные блоки лежат в полуплоскости \(y>0\). Связность понимается по 4-соседям.
Если блок расположен в точке \((x,y)\), любой путь от опоры до него требует не менее \(y+|x|\) шагов по занятым клеткам. Так как блоков всего \(n\), обязательно
$$y+|x|\le n.$$
Значит, все возможные клетки лежат внутри конечного ромба
$$0<y\le n,\qquad |x|\le n-y.$$
Именно эту область заранее строит buildDomain().
Все блоки имеют одинаковую массу, поэтому горизонтальный момент относительно оси опоры пропорционален сумме \(x\)-координат занятых клеток. Следовательно, равновесие эквивалентно
$$\sum_{(x,y)\in S} x = 0.$$
DFS хранит это значение в целой переменной sumx. Терминальные состояния принимаются только при
sumx == 0.
Сложность задачи не в проверке баланса, а в том, чтобы сгенерировать каждую связную скульптуру ровно один раз. Для этого используется DFS в стиле Редельмайера.
Занятые клетки. occ хранит опору и уже выбранные блоки.
Фронтир. U хранит соседние клетки, которые ещё можно добавить.
Запрещённые клетки. forb хранит клетки, которые текущая ветка уже решила не использовать.
На каждом шаге алгоритм извлекает из фронтира клетку \(u\), сначала рекурсивно рассматривает ветку с включением \(u\), а затем помечает \(u\) как запрещённую и продолжает дальше. Именно этот фиксированный порядок решений и уничтожает дубликаты, возникающие из-за разных порядков добавления.
После обязательного первого блока \((0,1)\) стартовый фронтир равен
$$\{(-1,1),(1,1),(0,2)\}.$$
Если ветка решает не брать \((1,1)\), эта клетка становится forbidden, и ту же итоговую фигуру уже нельзя позже построить в порядке «сначала \((0,2)\), потом \((1,1)\)».
Пусть текущая горизонтальная сумма равна sumx, и осталось поставить \(r\) блоков. Даже в самом
благоприятном продолжении максимально возможная коррекция ограничена.
Код собирает все положительные координаты \(x\) в домене, сортирует их по убыванию и определяет
$$B(r)=\text{сумма }r\text{ наибольших }x\text{-координат домена}.$$
Поскольку домен симметричен, эта же величина ограничивает коррекцию и в отрицательную сторону. Поэтому, если
$$|\text{sumx}| > B(r),$$
то даже нереально удачный выбор оставшихся блоков уже не сможет вернуть сумму к нулю. Ветка безопасно отсекается.
Эта оценка игнорирует связность и уже занятые клетки, то есть является оптимистичной. Именно поэтому она безопасна.
DFS считает закреплённые скульптуры в фиксированной системе координат. Поэтому фигура и её зеркало порождаются обе, если только сама фигура не симметрична.
Обозначим
$$N=\text{все сбалансированные закреплённые скульптуры},\qquad S=\text{те, что инвариантны при }(x,y)\mapsto(-x,y).$$
Группа симметрий состоит из двух элементов: тождественного и отражения. По лемме Бёрнсайда число различных фигур с точностью до зеркала равно
$$\frac{N+S}{2}.$$
Метод isSymmetric() проверяет именно то, что каждая занятая клетка имеет занятого зеркального партнёра.
Простейшая сбалансированная скульптура для \(n=6\):
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}.$$
Она связна, зеркально симметрична и удовлетворяет
$$0+0+0+0-1+1=0.$$
В исходнике зашиты следующие контрольные точки:
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
Они одновременно проверяют каноническую генерацию, отсечения и зеркальный фактор.
Построение домена. buildDomain() создаёт все клетки ромба \(|x|\le n-y\), \(0\le y\le n\),
заранее вычисляя 4-соседей и зеркальный индекс каждой клетки.
Начальное состояние. initialState() запрещает все прочие клетки земли \(y=0\), ставит
опору и обязательный блок \((0,1)\), затем формирует первый фронтир.
Основной DFS. dfs() выполняет рекурсию include/forbid, обновляет sumx и
перед углублением применяет отсечение по maxCorr.
Подсчет симметрии. В терминальном состоянии с ровно \(n\) блоками и sumx == 0 код
увеличивает total, а если фигура зеркально симметрична, то и sym.
Разбиение по задачам. generateTasks() раскрывает верхние уровни дерева поиска в
независимые задания, которые затем обрабатываются потоками. Это влияет только на скорость.
Как и в задачах перечисления полиомино, худший случай экспоненциален по \(n\). На практике дерево сильно сокращают три идеи:
1. каноническая генерация фронтира убирает дубликаты по порядку добавления;
2. forbidden-клетки не позволяют восстановить ту же фигуру в другом порядке;
3. оценка баланса отсекает ветви, которые уже никогда не вернутся к \(\sum x=0\).
Память вдоль одной рекурсивной ветви имеет порядок \(O(n+|U|)\), плюс предвычисленный домен и таблицы зеркал.
نعدّ منحوتات شبكية مكوّنة من \(n\) كتل وحدية، متصلة بدعامة واحدة عند \((0,0)\). شرط الاتزان الميكانيكي يعني أن مركز الكتلة يجب أن يبقى فوق محور الدعامة \(x=0\). الأشكال المرتبطة بانعكاس مرآتي \((x,y)\mapsto(-x,y)\) تُعد شكلاً واحداً.
الدعامة نفسها لا تُحسب ضمن الكتل. أول كتلة حقيقية مفروضة عند \((0,1)\)، وجميع الكتل الأخرى تحقق \(y>0\). الاتصال يتم عبر جوار من أربع جهات.
إذا وُجدت كتلة عند \((x,y)\)، فإن أي مسار من الدعامة إليها يحتاج إلى ما لا يقل عن \(y+|x|\) خطوة عبر خلايا مشغولة. وبما أن عدد الكتل الكلي هو \(n\)، فلا بد من تحقق
$$y+|x|\le n.$$
ومن ثم فجميع الخلايا الممكنة تقع داخل معين منتهٍ:
$$0<y\le n,\qquad |x|\le n-y.$$
وهذا هو بالضبط المجال الذي تبنيه buildDomain() مسبقاً.
جميع الكتل ذات الكتلة نفسها، ولذلك فإن العزم الأفقي حول محور الدعامة يتناسب مع مجموع إحداثيات \(x\) للكتل المشغولة. لذا يكون الاتزان مكافئاً للشرط
$$\sum_{(x,y)\in S} x = 0.$$
تتابع DFS هذه الكمية في متغير صحيح هو sumx، ولا تقبل إلا الحالات النهائية التي تحقق
sumx == 0.
الصعوبة الحقيقية ليست في اختبار الاتزان، بل في توليد كل منحوتة متصلة مرة واحدة فقط. لهذا تستعمل الخوارزمية DFS قانونية على نمط Redelmeier.
مجموعة الإشغال. occ تخزن الدعامة والكتل المختارة حتى الآن.
الحدود. U تخزن الخلايا المجاورة التي يمكن إضافتها لاحقاً.
مجموعة المنع. forb تخزن الخلايا التي قرر هذا الفرع عدم استعمالها.
في كل خطوة، تسحب الخوارزمية خلية حدودية \(u\)، ثم تزور أولاً الفرع الذي يضم \(u\)، وبعد الرجوع تجعل \(u\) ممنوعة قبل متابعة بقية الفروع. هذا الترتيب الوحيد للقرارات هو الذي يمنع تكرار الشكل نفسه عبر ترتيبات إضافة مختلفة.
بعد الكتلة الإجبارية \((0,1)\)، تكون الحدود الابتدائية
$$\{(-1,1),(1,1),(0,2)\}.$$
فإذا قرر فرع ما عدم استعمال \((1,1)\)، تصبح هذه الخلية ممنوعة في ذلك الفرع، وبالتالي لا يمكن إعادة بناء الشكل النهائي نفسه لاحقاً عبر أخذ \((0,2)\) أولاً ثم الرجوع إلى \((1,1)\).
افترض أن المجموع الأفقي الحالي هو sumx وبقي \(r\) كتل لم توضع بعد. حتى في أكثر امتداد متفائل، فإن
مقدار التصحيح الممكن يبقى محدوداً.
تجمع الشيفرة جميع قيم \(x\) الموجبة في المجال، وترتبها تنازلياً، ثم تعرّف
$$B(r)=\text{مجموع أكبر }r\text{ قيم من }x\text{ في المجال}. $$
ولأن المجال متناظر، فإن \(B(r)\) نفسه يعطي أكبر مقدار ممكن للتصحيح في الاتجاه السالب. لذلك إذا تحقق
$$|\text{sumx}| > B(r),$$
فإنه حتى مع اختيار متفائل جداً للكتل المتبقية لن يمكن إعادة المجموع إلى الصفر، وبذلك يُقصّ الفرع بأمان.
هذا الحد يتجاهل الاتصال والخلايا المشغولة سابقاً، أي أنه متفائل عمداً. ولهذا السبب يكون آمناً.
تعدّ DFS المنحوتات المثبتة داخل جهاز إحداثيات ثابت. لذلك تُولَّد المنحوتة وصورتها المرآتية معاً ما لم تكن البنية نفسها متناظرة.
لنعرف
$$N=\text{جميع المنحوتات المتزنة المثبتة},\qquad S=\text{المنحوتات الثابتة تحت }(x,y)\mapsto(-x,y).$$
زمرة التناظر هنا مؤلفة من عنصرين: الهوية والانعكاس. وطبقاً للمّة Burnside فإن عدد المنحوتات المختلفة حتى التناظر المرآتي هو
$$\frac{N+S}{2}.$$
وتتحقق الدالة isSymmetric() تماماً من أن كل خلية مشغولة لها نظير مرآتي مشغول أيضاً.
منحوتة متزنة بسيطة عندما \(n=6\) هي
$$S=\{(0,1),(0,2),(0,3),(0,4),(-1,1),(1,1)\}.$$
وهذه البنية متصلة، متناظرة مرآتياً، وتحقق
$$0+0+0+0-1+1=0.$$
ويحوي المصدر نقاط تحقق مهمة:
$$f(6)=18,\qquad f(10)=964,\qquad f(15)=360505,\qquad f(18)=15030564.$$
وهذه القيم تختبر في الوقت نفسه التوليد القانوني، والتقليم، وقسمة التناظر.
بناء المجال. تنشئ buildDomain() جميع الخلايا داخل المعين \(|x|\le n-y\)،
\(0\le y\le n\)، وتحسب مسبقاً جيران الاتجاهات الأربع وفهرس المرآة لكل خلية.
الحالة الابتدائية. تجعل initialState() جميع خلايا الأرض الأخرى \(y=0\) ممنوعة،
وتضع الدعامة والكتلة الإلزامية \((0,1)\)، ثم تهيئ أول frontier.
الـ DFS الأساسية. تنفذ dfs() عودية include/forbid، وتحدّث sumx، وتطبق
تقليم maxCorr قبل التعمق أكثر.
عدّ التناظر. عند حالة نهائية فيها بالضبط \(n\) كتل و sumx == 0 تزيد الشيفرة
total، وإذا تحققت المرآتية تزيد أيضاً sym.
تقسيم المهام. تقوم generateTasks() بتوسيع المستويات العليا من شجرة البحث إلى مهام
مستقلة ثم تعالجها الخيوط. هذا يؤثر في السرعة فقط، لا في الرياضيات.
كما في مسائل تعداد polyomino، يظل أسوأ حال للبحث أسياً في \(n\). لكن عملياً تُضغط الشجرة كثيراً بفضل ثلاث أفكار:
1. التوليد القانوني للـ frontier يزيل التكرارات الناتجة عن اختلاف ترتيب الإضافة؛
2. الخلايا الممنوعة تمنع إعادة بناء الشكل نفسه بترتيب آخر؛
3. حد الاتزان يقطع الفروع التي لا يمكنها أبداً الرجوع إلى \(\sum x=0\).
استهلاك الذاكرة على طول مسار عودي واحد من رتبة \(O(n+|U|)\)، مع إضافة جداول المجال والمرآة المحسوبة مسبقاً.