Detailed mathematical approach

Problem Summary

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)\).

Mathematical Approach

1) Finite search domain

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().

2) Balance is the zero-torque condition

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.

3) Canonical connected generation via frontier and forbidden sets

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)\).

4) Why the pruning bound is valid

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.

5) Mirror identification and Burnside's lemma

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.

6) Small example and validation points

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.

How the Code Works

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.

Complexity Analysis

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.

Further Reading

1. Problem page: https://projecteuler.net/problem=275
2. Polyomino enumeration: https://en.wikipedia.org/wiki/Polyomino
3. Burnside's lemma: https://en.wikipedia.org/wiki/Burnside%27s_lemma