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

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.

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());
    }
}