Problem 275: Balanced Sculptures

Project Euler Problem 275 Solution

EulerSolve provides an optimized solution for Project Euler Problem 275, Balanced Sculptures, with C++, Python, Java, and a step-by-step mathematical explanation.

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

Detailed mathematical approach

Problem Summary

A balanced sculpture of order $n$ is a polyomino, a set of unit squares joined along common edges in which holes are allowed, ^[2] made of $n+1$ tiles: $n$ blocks and one plinth. The plinth is centred at $(0,0)$, every block has a $y$-coordinate greater than zero, and the centre of mass of all blocks together has $x$-coordinate $0$. A sculpture and its mirror image in the $y$-axis count as one. The statement shows the $18$ sculptures of order $6$ and gives $964$ for order $10$ and $360505$ for order $15$; we must count the balanced sculptures of order $18$. ^[1]

The whole solution in one sentence: the computer grows connected sets of squares upward from the plinth so that every balanced set of $18$ blocks is reached exactly once, abandons a partial set whenever a simple bound shows that it can no longer be balanced, and counts each mirror pair once by adding the number of symmetric sets to the number of balanced ones and halving the total.

Mathematical Approach

1. Cells and the balance condition

We describe each tile by its centre. Tiles with a common edge have centres at distance $1$ along one axis, and every tile is linked to the plinth at $(0,0)$ by such steps, so all centres are lattice points; the tile centred at $(x,y)$ is the cell $(x,y)$. The blocks are equal unit squares with their centres of mass at their centres, and the centre of mass of several parts is the average of their centres of mass weighted by their masses, ^[3] so the blocks $(x_1,y_1),\dots,(x_n,y_n)$ have their centre of mass on the $y$-axis exactly when

$$s=x_1+x_2+\dots+x_n=0.$$

Including the plinth would change nothing, since its $x$-coordinate is $0$. We call a set of blocks balanced when its sum $s$ is $0$.

2. The plinth fixes the first block

The neighbours $(1,0)$, $(-1,0)$ and $(0,-1)$ of the plinth have $y\le0$ and cannot be blocks, so the polyomino is connected only if its fourth neighbour $(0,1)$ is a block. As the plinth touches no other tile, the blocks alone are connected too: a path of tiles between two blocks that passes through the plinth enters and leaves it through $(0,1)$, and cutting out this detour leaves a path of blocks.

We call a connected set of $n$ cells with $y\ge1$ that contains $(0,1)$ an anchored set. Together with the plinth, every anchored set is a polyomino of $n+1$ tiles with all blocks above the plinth; holes are allowed, so nothing else has to be checked. Before mirror images are identified, the sculptures of order $n$ are therefore exactly the balanced anchored sets. Let $N(n)$ be their number, and $S(n)$ the number of anchored sets that coincide with their own mirror image.

3. Orders one to four by hand

$n=1$: the only anchored set is $\{(0,1)\}$, and it is balanced.
$n=2$: the second block is $(-1,1)$, $(1,1)$ or $(0,2)$, and only $(0,2)$ gives $s=0$.
$n=3$: the other two blocks have $x$-coordinates with sum $0$. Either both lie on the axis, which gives the column $(0,1),(0,2),(0,3)$, or they have $x=-1$ and $x=1$, since reaching a cell with $|x|\ge2$ would use up both remaining blocks. No block is left to connect them, so they are the neighbours $(-1,1)$ and $(1,1)$ of $(0,1)$, a row of three.
$n=4$: a block with $|x|\ge2$ needs blocks with $x=\pm1$ and $x=\pm2$ on the same side, and the one block left would need $x\le-3$ to cancel their sum of at least $3$, too far away to be connected. So either all four blocks lie on the axis, in a column, or one block has $x=-1$, one has $x=1$ and two lie on the axis. A single side block cannot link $(0,1)$ to a higher axis cell, so the axis blocks are $(0,1)$ and $(0,2)$, and each side block sits at height $1$ or $2$. This gives $1+2\cdot2=5$ balanced sets, as a list of all $33$ anchored sets of four cells confirms.

Of the five sets of order four, the column and the two sets with both side blocks at the same height are symmetric, while $\{(-1,1),(0,1),(0,2),(1,2)\}$ and $\{(1,1),(0,1),(0,2),(-1,2)\}$ are mirror images of each other and count once. So there are $1$, $1$, $2$ and $4$ sculptures of orders one to four.

4. Counting each mirror pair once

Let $\rho(x,y)=(-x,y)$ be the reflection in the $y$-axis. It maps neighbouring cells to neighbouring cells, keeps every $y$-coordinate, fixes $(0,1)$ and turns $s$ into $-s$, so it maps balanced anchored sets to balanced anchored sets, and applying it twice changes nothing. The balanced anchored sets therefore fall into classes $\{B,\rho(B)\}$, with one member when $\rho(B)=B$ and two members otherwise. A symmetric set is always balanced, since its cells off the axis cancel in pairs. Counting the classes gives

$$S(n)+\frac{N(n)-S(n)}{2}=\frac{N(n)+S(n)}{2}.$$

This is Burnside's lemma for the group $\{\mathrm{id},\rho\}$: the number of classes is the average number of sets fixed by the two elements of the group. ^[4] For order four it gives $(5+3)/2=4$; for order six, $N(6)=27$ and $S(6)=9$ give the $18$ of the statement, and for order ten $(1825+103)/2=964$. For $n=1,2,\dots,12$ the values are

$N(n)$: 1, 1, 2, 5, 12, 27, 70, 192, 589, 1825, 5870, 18952;
$S(n)$: 1, 1, 2, 3, 6, 9, 18, 30, 59, 103, 202, 362;
sculptures $(N(n)+S(n))/2$: 1, 1, 2, 4, 9, 18, 44, 111, 324, 964, 3036, 9657.

5. Where the blocks can lie

Every block $(x,y)$ of an anchored set of order $n$ satisfies $|x|+y\le n$. Indeed, the set contains a path of blocks from $(0,1)$ to $(x,y)$. Each step changes one coordinate by $1$, so the path needs at least $|x|+(y-1)$ steps and contains at least $|x|+y$ blocks, and there are only $n$ of them. The search can therefore be restricted to the triangle

$$R_n=\{(x,y):\ y\ge1,\ |x|+y\le n\},$$

which has $2(n-y)+1$ cells in row $y$ and $1+3+\dots+(2n-1)=n^2$ cells in total, $324$ for $n=18$. It is symmetric under $\rho$, and for $j=1,\dots,n$ the value $x=n-j$ occurs in exactly $j$ of its cells, in the rows $y=1,\dots,j$.

6. Generating each connected set once

Redelmeier's algorithm lists the connected sets of a graph that contain a fixed start cell, here the sets of cells of $R_n$ that contain $(0,1)$, never produces the same set twice, and needs memory only for the current path of its search. ^[5] A node of its search consists of

the current set $P$, which is connected and contains $(0,1)$;
a set $F$ of forbidden cells, which stay empty in every set produced below the node;
the untried cells $U$: the cells of $R_n$ that are adjacent to $P$ but lie neither in $P$ nor in $F$.

For $n\ge2$ the root has $P=\{(0,1)\}$, $F=\varnothing$ and $U=\{(1,1),(-1,1),(0,2)\}$. A node with fewer than $n$ cells takes its untried cells one after another in some order $u_1,u_2,\dots,u_m$. For $u_i$ it creates a child with the set $P\cup\{u_i\}$ and the forbidden set $F\cup\{u_1,\dots,u_{i-1}\}$. The child's untried cells are $u_{i+1},\dots,u_m$ together with the neighbours of $u_i$ in $R_n$ that lie in none of $P$, $F$ and $U$. These are again exactly the free neighbours of the child's set, because a neighbour of $P\cup\{u_i\}$ is a neighbour of $P$, hence untried or forbidden, or a neighbour of $u_i$.

7. Why no set is produced twice or missed

Call $Q$ a completion of a node if $Q$ is a connected set of $n$ cells of $R_n$ with $P\subseteq Q$ and no forbidden cell. We show by induction on $n-|P|$ that the search below a node produces each of its completions exactly once. If $|P|=n$, the only completion is $P$ itself. Otherwise let $Q$ be a completion. Since $Q$ is connected and larger than $P$, some cell of $Q$ outside $P$ is adjacent to $P$; it is not forbidden, so it is untried, and we let $u_i$ be the first untried cell that lies in $Q$. Then $Q$ is a completion of child $i$, because $u_1,\dots,u_{i-1}$ are not in $Q$. It is no completion of a child $j\lt i$, whose set contains $u_j\notin Q$, nor of a child $j\gt i$, which forbids $u_i\in Q$. Conversely, every completion of a child is a completion of the node. So the completions of the node are divided among its children without overlap, and the induction hypothesis finishes the proof. At the root the completions are all anchored sets of order $n$, because these lie in $R_n$ by Section 5.

8. Worked example: the search for order three

The program takes the untried cells in the reverse order of their discovery, the newest first, so for $n=3$ the root takes $(0,2)$, then $(-1,1)$, then $(1,1)$.

Child $(0,2)$: the set $\{(0,1),(0,2)\}$ adds the untried cells $(1,2)$, $(-1,2)$ and $(0,3)$ to $(1,1)$ and $(-1,1)$, so it has five completions. Only the column with $(0,3)$ is balanced.
Child $(-1,1)$, with $(0,2)$ forbidden: the untried cells are $(1,1)$, $(-2,1)$ and $(-1,2)$, which give three completions; only the row $(-1,1),(0,1),(1,1)$ is balanced.
Child $(1,1)$, with $(0,2)$ and $(-1,1)$ forbidden: the untried cells are $(2,1)$ and $(1,2)$, which give two completions, neither balanced.

The search thus produces $5+3+2=10$ anchored sets of three cells, each once. The set $\{(-1,1),(0,1),(0,2)\}$, for example, appears below the first child only, because the second child forbids $(0,2)$. Both balanced sets are symmetric, which gives the $2$ sculptures of order three.

9. Stopping early: the balance bound

Let $B(r)$ be the sum of the $r$ largest $x$-coordinates of cells of $R_n$, with $B(0)=0$. By Section 5 the largest values are $n-1$ once, $n-2$ twice, $n-3$ three times and so on; for $n=6$ this gives $B(1),\dots,B(6)=5,9,13,16,19,22$.

Claim. If a node has $k$ blocks with sum $s$, $r=n-k$ blocks are still missing and $|s|\gt B(r)$, then no completion of the node is balanced.

Proof. The missing blocks are $r$ different cells of $R_n$, so the sum $t$ of their $x$-coordinates is at most $B(r)$. Since $R_n$ is symmetric, the $r$ smallest $x$-coordinates add up to $-B(r)$, so $t\ge-B(r)$. A balanced completion needs $s+t=0$, hence $|s|=|t|\le B(r)$.

For example, for $n=6$ the node with the row $(0,1),(1,1),(2,1),(3,1),(4,1)$ has $s=10$ and one missing block, and $10\gt B(1)=5$, so the search abandons it. The test ignores that the missing blocks must touch the set and avoid its cells; that makes it weaker, but safe, as the rejection test of backtracking must be. ^[6] With $r=0$ it is the balance condition itself.

10. How late the bound acts

The $x$-coordinates of a connected set of $k$ cells that contains $(0,1)$ form a range of consecutive integers containing $0$. If the $i$-th largest of them is $v\ge1$, the values $0,1,\dots,v-1$ occur in cells other than these $i$, so $v\le k-i$. Hence $s\le0+1+\dots+(k-1)=k(k-1)/2$, and by symmetry $|s|\le k(k-1)/2$. For $n=18$, a node with $k\le13$ blocks has $|s|\le78$ and at least five missing blocks, while $B(5)=79$, so the bound never acts there; at $k=14$ the row $(0,1),(1,1),\dots,(13,1)$ has $s=91\gt B(4)=64$ and is abandoned.

How the Code Works

The C++ program ^[7] keeps the search region in a table of Cell records with coordinates, up to four neighbour indices nbr and the index mirror of the mirror image, and stores sets of cells as Bitsets of $384$ bits. A search node is a Task: the bitsets occ, forb and inU of occupied, forbidden and untried cells, the untried cells as a stack U of up to $128$ indices with length uCount, the occupied cells placed, the number k of blocks and their sum sumx, which is $s$.

The constructor of Solver calls buildDomain, which lists the cells with $0\le y\le n$ and $|x|\le n-y$, the triangle $R_n$ plus $2n+1$ ground cells, and finds their neighbours in the order right, left, up, down. Then buildMaxCorr sorts the $x$-coordinates of the cells with $y\gt0$ in decreasing order and stores their prefix sums maxCorr[r], the numbers $B(r)$ of Section 9. initialState forbids the ground cells other than the plinth, occupies the plinth and $(0,1)$ with $k=1$ and $s=0$, and pushes $(1,1)$, $(-1,1)$ and $(0,2)$ onto U.

dfs is the search of Sections 6 to 9. It first applies the bound, abs(sumx) > maxCorr[remaining]. At $k=n$ it increments total, the count $N$, if $s=0$, and also sym, the count $S$, if isSymmetric finds the mirror image of every occupied cell occupied. Otherwise it pops the newest untried cell $u$, occupies it, pushes the neighbours of $u$ with $y\gt0$ that are neither occupied, forbidden nor untried, and recurses with $k+1$ blocks and the sum $s+x_u$. Afterwards it pops these neighbours again, frees $u$, forbids it and notes it in a local array processed. When the stack is empty, it lifts the ban on the processed cells and pushes them back in reverse order, so that U is exactly as the node received it; the caller relies on this when it removes its own pushed neighbours from the top of the same array.

solve first runs generateTasks, the same recursion as dfs but stopped at splitDepth blocks, $8$ for $n\ge18$ and otherwise $\max(2,\lfloor n/2\rfloor)$, which stores a copy of every node reached there. Each stored node is then finished by dfs, the counters are added up, and the result is $(N+S)/2$ as in Section 4. For $n=18$ the bound cannot act in the first eight levels (Section 10), so $5046$ nodes are stored, one per anchored set of eight cells. main reads the order with -n, by default $18$; the option --validate first recomputes the orders $6$, $10$ and $15$ of the statement and the order $18$, compares them with stored values and stops with exit code $2$ on a mismatch.

The bitsets hold $384$ cells, enough for the $361$ cells of order $18$ but not for the $400$ of order $19$. For $n=1$ the split depth $2$ exceeds $n$, so the only anchored set $\{(0,1)\}$ is never stored and the program prints $0$ instead of $1$; the orders $2$ to $15$ all come out right. The sum $s$ is an int with $|s|\le153$ by Section 10, and the counters are unsigned 64-bit integers, far larger than any count here.

The Python and Java files are bridges to solutionsCpp/Euler275.cpp: Python's solve finds that folder from the location of its own file, Java's ensureBridgeBinary from the working directory. Each keeps its own hidden binary, rebuilt with clang++ or g++ and -std=c++17 -O2 when it is missing or older than the source, runs it without options, hence for order $18$ and without --validate, and returns the printed number found by parse_output or parseOutput, so all counting happens in C++.

Complexity and Verification

An anchored set is a fixed polyomino, one distinguished up to translation only, ^[2] placed with one cell of its lowest row at $(0,1)$; a fixed polyomino with $w$ cells in its lowest row gives $w$ anchored sets, so the $6$ fixed trominoes give the $10$ sets of Section 8. The number of fixed polyominoes grows roughly like $\lambda^n$ with $\lambda\approx4.06$; ^[2] there are $1\,540\,820\,542$ with $18$ cells, ^[8] which give $2\,960\,730\,377$ anchored sets. Without the bound, the search tree for $n=18$ would have all $4\,000\,668\,837$ anchored sets with at most $18$ cells as nodes; with the bound it has $1\,853\,038\,234$ nodes, $46\%$ of them, since most nodes lie at $14$ or more blocks, where the bound acts. The published program enters each of its $5046$ stored nodes twice, once in generateTasks and once in dfs. Each step from a node to a child adds and removes at most four neighbours, and the symmetry test at a balanced leaf inspects at most $n+1$ cells, so for $C$ nodes and $L$ balanced leaves the search costs $O(C+nL)$, plus $O(n^2\log n)$ for building and sorting the region. This grows exponentially with $n$; on our test machine the published program needed about two seconds for order $18$. The memory is small: $(n+1)^2$ cells, a recursion of depth at most $n$ with a local array of $128$ integers per level, and the $5046$ stored nodes of $800$ bytes in a vector with room for $8192$, about 6.6 MB in our builds.

The program checks itself with --validate, which passes. For this article we also verified:

An independent brute force grows sets cell by cell and removes duplicates with a hash set, without Redelmeier's order and without the bound. For every $n\le12$ it gives the same $N(n)$, $S(n)$ and sculpture counts, and its numbers of anchored sets, such as $957\,522$ for twelve cells, match the search without the bound.
A literal check of the definition grows polyominoes from the plinth itself and identifies mirror images by a canonical representative instead of Burnside's lemma; it gives 1, 1, 2, 4, 9, 18, 44, 111, 324 and 964 sculptures for $n=1,\dots,10$.
A Python transcription of the search gives the same $N(n)$, $S(n)$ and number of nodes as an instrumented copy of the C++ search for every $n\le15$, for example $36\,633\,444$ nodes, $N(15)=718\,474$ and $S(15)=2536$, hence the $360505$ sculptures of the statement.
Shifting the anchored sets so that their lowest rows start at a common point leaves 1, 2, 6, 19, 63, 216, 760, 2725, 9910 and 36446 different sets for $n=1,\dots,10$, the numbers of fixed polyominoes. ^[8]
The C++ program built with Clang 22 and with GCC 16, the Python bridge and the Java bridge print the same value for order $18$.

Footnotes and References

The references below supply the background facts used above; the reduction to anchored sets, the proofs and all counts are worked out in this article.

Project Euler 275 — Balanced Sculptures. The official statement defines balanced sculptures of order n, gives 18, 964 and 360505 for the orders 6, 10 and 15, and asks for the number of order 18.
Wikipedia — Polyomino. Fixed polyominoes are distinguished up to translation only, and the article estimates the number of fixed polyominoes with n cells as cλⁿ/n with λ ≈ 4.0626.
Wikipedia — Center of mass. The centre of mass of point masses mᵢ at positions rᵢ is Σmᵢrᵢ / Σmᵢ, and the centre of mass of a whole is the weighted average of the centres of mass of its parts.
Wikipedia — Burnside's lemma. For a finite group acting on a set, the number of orbits equals the average number of points fixed by an element of the group.
M. Moffie, Counting Polyominoes in Two and Three Dimensions. M.Sc. thesis, Technion, 2003. Section 1.2 presents Redelmeier's algorithm for counting the connected subgraphs of a graph that contain a given vertex, driven by an untried set, and notes that it never produces the same subgraph twice. The original paper is D. H. Redelmeier, Counting polyominoes: yet another attack, Discrete Mathematics 36 (1981), 191–203.
Wikipedia — Backtracking. Backtracking abandons a partial candidate as soon as it cannot be completed to a valid solution; its rejection test may only fire when no extension can be a solution.
C++ — Euler275.cpp. The linked immutable revision contains buildDomain, buildMaxCorr, dfs, generateTasks and the checks run by --validate. It is the implementation record for this article.
OEIS A001168 — Number of fixed polyominoes with n cells. For n = 1, …, 10 its terms are 1, 2, 6, 19, 63, 216, 760, 2725, 9910 and 36446, and the term for n = 18 is 1540820542.

Problem 275 source code

C++

#include <algorithm>
#include <array>
#include <atomic>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <thread>
#include <unordered_map>
#include <utility>
#include <vector>

using std::array;
using std::cout;
using std::cerr;
using std::max;
using std::size_t;
using std::string;
using std::uint64_t;
using std::vector;

struct Bitset {
    static constexpr int WORDS = 6;
    uint64_t w[WORDS]{};

    inline void set(int i) { w[i >> 6] |= (1ULL << (i & 63)); }
    inline void reset(int i) { w[i >> 6] &= ~(1ULL << (i & 63)); }
    inline bool test(int i) const { return (w[i >> 6] >> (i & 63)) & 1ULL; }
};

struct Cell {
    int x = 0;
    int y = 0;
    int deg = 0;
    int nbr[4]{};
    int mirror = -1;
};

struct Task {
    Bitset occ, forb, inU;
    array<int, 128> U{};
    int uCount = 0;

    array<int, 32> placed{};
    int k = 0;
    int sumx = 0;
};

class Solver {
  public:
    explicit Solver(int n) : n(n) {
        buildDomain();
        buildMaxCorr();
    }

    uint64_t solve(int threads) {
        Task st = initialState();

        vector<Task> tasks;
        int splitDepth = (n >= 18 ? 8 : max(2, n / 2));
        generateTasks(st, splitDepth, tasks);

        std::atomic<size_t> idx{0};
        vector<std::thread> pool;
        vector<uint64_t> total(threads, 0), sym(threads, 0);

        for (int t = 0; t < threads; ++t) {
            pool.emplace_back([&, t]() {
                while (true) {
                    size_t i = idx.fetch_add(1, std::memory_order_relaxed);
                    if (i >= tasks.size()) break;
                    Task local = tasks[i];
                    dfs(local, total[t], sym[t]);
                }
            });
        }
        for (auto& th : pool) th.join();

        uint64_t N = 0, S = 0;
        for (int t = 0; t < threads; ++t) {
            N += total[t];
            S += sym[t];
        }

        return (N + S) / 2;
    }

  private:
    int n;
    vector<Cell> dom;
    int root = -1;
    vector<int> maxCorr;

    inline bool isBlockCell(int idx) const { return dom[idx].y > 0; }

    void buildDomain() {
        vector<std::pair<int, int>> coords;
        coords.reserve((n + 1) * (n + 1));
        for (int y = 0; y <= n; ++y) {
            int lim = n - y;
            for (int x = -lim; x <= lim; ++x) coords.emplace_back(x, y);
        }

        std::unordered_map<long long, int> id;
        id.reserve(coords.size() * 2);

        auto key = [](int x, int y) -> long long {
            return (static_cast<long long>(static_cast<uint32_t>(x)) << 32) ^
                   static_cast<uint32_t>(y);
        };

        dom.resize(coords.size());
        for (int i = 0; i < static_cast<int>(coords.size()); ++i) {
            auto [x, y] = coords[i];
            dom[i].x = x;
            dom[i].y = y;
            id[key(x, y)] = i;
        }

        for (int i = 0; i < static_cast<int>(dom.size()); ++i) {
            int x = dom[i].x, y = dom[i].y;
            auto addNbr = [&](int nx, int ny) {
                auto it = id.find(key(nx, ny));
                if (it == id.end()) return;
                dom[i].nbr[dom[i].deg++] = it->second;
            };
            addNbr(x + 1, y);
            addNbr(x - 1, y);
            addNbr(x, y + 1);
            addNbr(x, y - 1);

            dom[i].mirror = id[key(-x, y)];
            if (x == 0 && y == 0) root = i;
        }
        if (root < 0) throw std::runtime_error("Root not found");
    }

    void buildMaxCorr() {
        vector<int> xs;
        xs.reserve(dom.size());
        for (const auto& c : dom) {
            if (c.y > 0) xs.push_back(c.x);
        }
        std::sort(xs.begin(), xs.end(), std::greater<int>());

        maxCorr.assign(n + 1, 0);
        long long pref = 0;
        for (int r = 1; r <= n; ++r) {
            pref += xs[r - 1];
            maxCorr[r] = static_cast<int>(pref);
        }
    }

    Task initialState() const {
        Task st;

        for (int i = 0; i < static_cast<int>(dom.size()); ++i) {
            if (dom[i].y == 0 && i != root) st.forb.set(i);
        }

        int firstBlock = -1;
        for (int ni = 0; ni < dom[root].deg; ++ni) {
            int v = dom[root].nbr[ni];
            if (dom[v].x == 0 && dom[v].y == 1) firstBlock = v;
        }
        if (firstBlock < 0) throw std::runtime_error("Missing (0,1)");

        st.occ.set(root);
        st.occ.set(firstBlock);
        st.placed[0] = root;
        st.placed[1] = firstBlock;
        st.k = 1;
        st.sumx = 0;

        for (int ni = 0; ni < dom[firstBlock].deg; ++ni) {
            int v = dom[firstBlock].nbr[ni];
            if (!isBlockCell(v)) continue;
            if (st.occ.test(v) || st.forb.test(v) || st.inU.test(v)) continue;
            st.U[st.uCount++] = v;
            st.inU.set(v);
        }
        return st;
    }

    inline bool isSymmetric(const Task& st) const {
        for (int i = 0; i <= st.k; ++i) {
            int idx = st.placed[i];
            if (!st.occ.test(dom[idx].mirror)) return false;
        }
        return true;
    }

    void dfs(Task& st, uint64_t& total, uint64_t& sym) {
        int remaining = n - st.k;
        if (std::abs(st.sumx) > maxCorr[remaining]) return;

        if (st.k == n) {
            if (st.sumx == 0) {
                total++;
                if (isSymmetric(st)) sym++;
            }
            return;
        }

        int processedCount = 0;
        int processed[128];

        while (st.uCount > 0) {
            int u = st.U[--st.uCount];
            st.inU.reset(u);

            st.occ.set(u);
            st.placed[st.k + 1] = u;

            int addedStart = st.uCount;
            for (int ni = 0; ni < dom[u].deg; ++ni) {
                int v = dom[u].nbr[ni];
                if (!isBlockCell(v)) continue;
                if (st.occ.test(v) || st.forb.test(v) || st.inU.test(v)) continue;
                st.U[st.uCount++] = v;
                st.inU.set(v);
            }

            st.k++;
            st.sumx += dom[u].x;
            dfs(st, total, sym);
            st.sumx -= dom[u].x;
            st.k--;

            while (st.uCount > addedStart) {
                int v = st.U[--st.uCount];
                st.inU.reset(v);
            }
            st.occ.reset(u);

            st.forb.set(u);
            processed[processedCount++] = u;
        }

        for (int i = processedCount - 1; i >= 0; --i) {
            int u = processed[i];
            st.forb.reset(u);
            st.U[st.uCount++] = u;
            st.inU.set(u);
        }
    }

    void generateTasks(Task& st, int splitDepth, vector<Task>& out) {
        int remaining = n - st.k;
        if (std::abs(st.sumx) > maxCorr[remaining]) return;

        if (st.k >= splitDepth) {
            out.push_back(st);
            return;
        }

        int processedCount = 0;
        int processed[128];

        while (st.uCount > 0) {
            int u = st.U[--st.uCount];
            st.inU.reset(u);

            st.occ.set(u);
            st.placed[st.k + 1] = u;

            int addedStart = st.uCount;
            for (int ni = 0; ni < dom[u].deg; ++ni) {
                int v = dom[u].nbr[ni];
                if (!isBlockCell(v)) continue;
                if (st.occ.test(v) || st.forb.test(v) || st.inU.test(v)) continue;
                st.U[st.uCount++] = v;
                st.inU.set(v);
            }

            st.k++;
            st.sumx += dom[u].x;
            generateTasks(st, splitDepth, out);
            st.sumx -= dom[u].x;
            st.k--;

            while (st.uCount > addedStart) {
                int v = st.U[--st.uCount];
                st.inU.reset(v);
            }
            st.occ.reset(u);

            st.forb.set(u);
            processed[processedCount++] = u;
        }

        for (int i = processedCount - 1; i >= 0; --i) {
            int u = processed[i];
            st.forb.reset(u);
            st.U[st.uCount++] = u;
            st.inU.set(u);
        }
    }
};

static void usage(const char* argv0) {
    cerr << "Usage: " << argv0 << " [-n N] [-t THREADS] [--validate]\n";
}

int main(int argc, char** argv) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 18;
    int threads = static_cast<int>(std::thread::hardware_concurrency());
    if (threads <= 0) threads = 1;
    bool validate = false;

    for (int i = 1; i < argc; ++i) {
        string a = argv[i];
        if (a == "-n" && i + 1 < argc) {
            n = std::stoi(argv[++i]);
        } else if (a == "-t" && i + 1 < argc) {
            threads = max(1, std::stoi(argv[++i]));
        } else if (a == "--validate") {
            validate = true;
        } else {
            usage(argv[0]);
            return 1;
        }
    }

    auto run = [&](int nn) -> uint64_t {
        Solver s(nn);
        return s.solve(threads);
    };

    if (validate) {
        struct Check {
            int n;
            uint64_t expected;
        };
        vector<Check> checks = {
            {6, 18},
            {10, 964},
            {15, 360505},
            {18, 15030564},
        };
        for (const auto& c : checks) {
            uint64_t got = run(c.n);
            if (got != c.expected) {
                cerr << "Validation failed for n=" << c.n << " expected=" << c.expected
                     << " got=" << got << "\n";
                return 2;
            }
        }
    }

    cout << run(n) << "\n";
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""

    answer_candidates = []
    equal_candidates = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answer_candidates.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equal_candidates.append(m2.group(1).strip())

    if answer_candidates:
        return answer_candidates[-1]
    if equal_candidates:
        return equal_candidates[-1]
    return lines[-1]


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = subprocess.check_output([str(binary)], text=True)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


if __name__ == "__main__":
    print(solve())

Java

import java.nio.file.*;
import java.util.*;
import java.util.regex.*;

public class Euler275 {
    private static final Pattern ANSWER_RE = Pattern.compile("answer\\s*:\\s*(.+)$", Pattern.CASE_INSENSITIVE);
    private static final Pattern EQUAL_RE = Pattern.compile("=\\s*(.+)$");

    private static String parseOutput(String stdout) {
        String[] lines = stdout.split("\\R");
        List<String> nonEmpty = new ArrayList<>();
        for (String line : lines) {
            String t = line.trim();
            if (!t.isEmpty()) {
                nonEmpty.add(t);
            }
        }
        if (nonEmpty.isEmpty()) {
            return "";
        }

        List<String> answers = new ArrayList<>();
        List<String> equals = new ArrayList<>();
        for (String line : nonEmpty) {
            Matcher m1 = ANSWER_RE.matcher(line);
            if (m1.find()) {
                answers.add(m1.group(1).trim());
            }
            Matcher m2 = EQUAL_RE.matcher(line);
            if (m2.find()) {
                equals.add(m2.group(1).trim());
            }
        }

        if (!answers.isEmpty()) {
            return answers.get(answers.size() - 1);
        }
        if (!equals.isEmpty()) {
            return equals.get(equals.size() - 1);
        }
        return nonEmpty.get(nonEmpty.size() - 1);
    }

    private static String pickCompiler() throws Exception {
        for (String compiler : List.of("clang++", "g++")) {
            Process probe = new ProcessBuilder("bash", "-lc", "command -v " + compiler)
                    .redirectErrorStream(true)
                    .start();
            String out = new String(probe.getInputStream().readAllBytes());
            int rc = probe.waitFor();
            if (rc == 0 && !out.trim().isEmpty()) {
                return compiler;
            }
        }
        throw new RuntimeException("No C++ compiler found (clang++/g++).");
    }

    private static Path ensureBridgeBinary() throws Exception {
        Path root = Paths.get(System.getProperty("user.dir"));
        Path src = root.resolve("solutionsCpp").resolve("Euler275.cpp");
        Path bin = root.resolve("solutionsCpp").resolve(".euler275_java_bridge");

        boolean rebuild = Files.notExists(bin)
                || Files.getLastModifiedTime(src).compareTo(Files.getLastModifiedTime(bin)) > 0;

        if (rebuild) {
            String compiler = pickCompiler();
            Process compile = new ProcessBuilder(
                    compiler,
                    "-std=c++17",
                    "-O2",
                    src.toString(),
                    "-o",
                    bin.toString())
                    .inheritIO()
                    .start();
            if (compile.waitFor() != 0) {
                throw new RuntimeException("Failed to compile Euler275 C++ bridge.");
            }
        }

        return bin;
    }

    private static String solveViaCppBridge() throws Exception {
        Path bin = ensureBridgeBinary();
        Process run = new ProcessBuilder(bin.toString())
                .redirectErrorStream(true)
                .start();
        String out = new String(run.getInputStream().readAllBytes());
        int rc = run.waitFor();
        if (rc != 0) {
            throw new RuntimeException("Euler275 C++ bridge failed.\n" + out);
        }
        String parsed = parseOutput(out);
        if (parsed.isEmpty()) {
            throw new RuntimeException("Euler275 C++ bridge produced empty output.");
        }
        return parsed;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(solveViaCppBridge());
    }
}