Project Euler

Balanced Sculptures

A balanced sculpture of order n consists of a plinth at position (0, 0) and n unit-square blocks at integer coordinates with y >= 1, forming a connected polyomino (adjacency via shared edges; holes...

Source sync Apr 19, 2026

Problem #0275

Level Level 18

Solved By 725

Languages C++, Python

Answer 15030564

Length 571 words

searchmodular_arithmeticgraph

Let us define a balanced sculpture of order $n$ as follows:

A polyomino made up of $n + 1$ tiles known as the blocks ($n$ tiles) and the plinth (remaining tile);
the plinth has its centre at position ($x = 0, y = 0$);
the blocks have $y$-coordinates greater than zero (so the plinth is the unique lowest tile)
the centre of mass of all the blocks, combined, has $x$-coordinate equal to zero.

When counting the sculptures, any arrangements which are simply reflections about the $y$-axis, are not counted as distinct. For example, the $18$ balanced sculptures of order $6$ are shown below; note that each pair of mirror images (about the $y$-axis) is counted as one sculpture:

Problem illustration

There are $964$ balanced sculptures of order $10$ and $360505$ of order $15$.

How many balanced sculptures are there of order $18$?

Problem 275: Balanced Sculptures

Mathematical Foundation

Theorem 1 (Burnside’s Lemma for Reflection Symmetry). Let $T$ be the number of fixed (i.e., oriented) balanced sculptures and $S$ the number of those that are symmetric under reflection $x \mapsto -x$ . Then the number of distinct balanced sculptures up to reflection is

\frac{T + S}{2}.

Proof. The group $G = \{e, \sigma\}$ where $\sigma$ is $y$ -axis reflection acts on the set of fixed balanced sculptures. By Burnside’s lemma, the number of orbits is

\frac{1}{|G|}\sum_{g \in G} |\operatorname{Fix}(g)| = \frac{|\operatorname{Fix}(e)| + |\operatorname{Fix}(\sigma)|}{2} = \frac{T + S}{2}. \quad\square

Lemma 1 (Forced Cell). In any balanced sculpture of order $n \ge 1$ , the cell $(0, 1)$ is occupied.

Proof. The plinth occupies $(0, 0)$ . All $n$ blocks satisfy $y \ge 1$ . The polyomino must be connected. The only cell at $y \ge 1$ adjacent to $(0, 0)$ is $(0, 1)$ (since $(1, 0)$ and $(-1, 0)$ have $y = 0$ , and $(0, -1)$ has $y < 0$ ). If $(0, 1)$ were unoccupied, no block would be adjacent to the plinth, violating connectivity. $\square$

Lemma 2 (Balance as Zero-Sum). The balance condition $\sum_{i=1}^{n} x_i = 0$ is equivalent to requiring that the centre of mass of the $n$ blocks has $x$ -coordinate zero.

Proof. The $x$ -coordinate of the centre of mass is $\bar{x} = \frac{1}{n}\sum x_i$ . This equals zero iff $\sum x_i = 0$ . $\square$

Theorem 2 (Redelmeier Enumeration with Excluded Set). The fixed polyominoes rooted at $(0, 0)$ with all blocks at $y \ge 1$ can be enumerated without duplication by maintaining:

A set $P$ of placed cells (the current polyomino).
An ordered “untried” frontier $U$ of cells adjacent to $P$ at $y \ge 1$ .
An “excluded” set $E$ of cells permanently skipped.

At each step, the lexicographically smallest cell $c \in U$ is either added to $P$ (with its unvisited neighbours joining $U$ ) or moved to $E$ . The excluded set ensures a skipped cell is never re-added to $U$ by a later placement.

Proof. This is Redelmeier’s algorithm (1981) adapted to rooted polyominoes. The key invariant is that each polyomino is generated exactly once: the generation order is determined by the lexicographic processing of frontier cells, and the excluded set prevents revisiting decisions. The correctness proof proceeds by induction on the number of cells: at each branch point, the two sub-trees partition the set of polyominoes containing $c$ and those not containing $c$ (with $c$ in $E$ ). $\square$

Lemma 3 (Balance Pruning). During the DFS, if $|x_{\text{sum}}|$ exceeds $r \cdot x_{\max}$ where $r$ is the number of remaining cells to place and $x_{\max}$ is the maximum $|x|$ -coordinate reachable, the branch can be pruned.

Proof. Each remaining cell contributes at most $x_{\max}$ to the absolute change in $x_{\text{sum}}$ . If the current imbalance exceeds the maximum possible correction, no completion can achieve $x_{\text{sum}} = 0$ . $\square$

Editorial

Order n = n blocks + 1 plinth = n+1 tiles. Plinth at (0,0). Blocks at y >= 1. Connected polyomino. x_sum of blocks = 0. Reflections about y-axis identified. Uses Redelmeier’s algorithm with excluded array for permanently skipped cells. Note: This Python version is significantly slower than the C++ version. For ORDER=18, use the C++ solution. We count fixed balanced sculptures (T). We then count symmetric balanced sculptures (S). Finally, branch 1: Add c.

Pseudocode

Count fixed balanced sculptures (T)
Count symmetric balanced sculptures (S)
Branch 1: Add c
undo: remove c from P, restore U
Branch 2: Skip c permanently
undo: remove c from E, restore c to U

Complexity Analysis

Time: The search tree is bounded by the total number of polyominoes of order $n + 1$ (plinth plus $n$ blocks), which grows exponentially but is tractable for $n = 18$ with pruning. Empirically, the computation takes approximately 60 seconds in optimized C++.
Space: $O(n \cdot W)$ where $W$ is the width of the grid visited. The DFS stack depth is $O(n)$ , and each level stores $O(W)$ frontier and excluded cells.

Answer

\boxed{15030564}

C++ project_euler/problem_275/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 275: Balanced Sculptures
 *
 * Order n = n blocks + 1 plinth = n+1 tiles.
 * Plinth at (0,0). Blocks at y >= 1. All tiles connected.
 * x_sum of blocks = 0. Reflections identified.
 *
 * Redelmeier with excluded[] array for permanently skipped cells.
 * Optimized: use bool arrays instead of set for untried membership.
 */

const int ORDER_VAL = 18;
int ORDER;
const int MAXC = 20;

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

const int W = 2 * MAXC + 1; // 41
const int H = MAXC + 1;     // 21
inline int encode(int x, int y) { return y * W + (x + MAXC); }
inline int dec_x(int c) { return c % W - MAXC; }
inline int dec_y(int c) { return c / W; }

const int MAXCELLS = H * W; // 861
bool placed[MAXCELLS];
bool excluded[MAXCELLS];
bool in_untried[MAXCELLS];

long long result_total = 0;
long long result_sym = 0;

int cells_arr[25];
int n_placed;
int x_sum;

// Use a fixed-size array for untried, sorted
void dfs(int* untried, int untried_sz) {
    if (n_placed == ORDER) {
        if (x_sum == 0) {
            result_total++;
            bool sym = true;
            for (int i = 0; i < ORDER; i++) {
                int x = dec_x(cells_arr[i]), y = dec_y(cells_arr[i]);
                int mirror = encode(-x, y);
                if (!placed[mirror]) { sym = false; break; }
            }
            if (sym) result_sym++;
        }
        return;
    }

    int remaining = ORDER - n_placed;
    if (abs(x_sum) > remaining * MAXC) return;
    if (untried_sz == 0) return;

    int c = untried[0];
    int cx = dec_x(c), cy = dec_y(c);

    // Branch 1: Add c
    {
        placed[c] = true;
        in_untried[c] = false;
        cells_arr[n_placed] = c;
        n_placed++;
        x_sum += cx;

        // Find new neighbors
        int added[4];
        int n_added = 0;
        for (int d = 0; d < 4; d++) {
            int nx = cx + dx[d], ny = cy + dy[d];
            if (ny < 1 || ny > MAXC || nx < -MAXC || nx > MAXC) continue;
            int nc = encode(nx, ny);
            if (!placed[nc] && !excluded[nc] && !in_untried[nc]) {
                in_untried[nc] = true;
                added[n_added++] = nc;
            }
        }

        // Build new untried = (old - c) merged with added
        // Both old untried (from index 1) and added are sorted (added needs sorting)
        sort(added, added + n_added);
        int new_untried[100]; // should be enough
        int new_sz = 0;
        int ai = 0;
        for (int i = 1; i < untried_sz; i++) {
            while (ai < n_added && added[ai] < untried[i]) {
                new_untried[new_sz++] = added[ai++];
            }
            new_untried[new_sz++] = untried[i];
        }
        while (ai < n_added) {
            new_untried[new_sz++] = added[ai++];
        }

        dfs(new_untried, new_sz);

        // Undo
        n_placed--;
        x_sum -= cx;
        placed[c] = false;
        for (int i = 0; i < n_added; i++) in_untried[added[i]] = false;
    }

    // Branch 2: Skip c
    {
        excluded[c] = true;
        in_untried[c] = false;
        dfs(untried + 1, untried_sz - 1);
        excluded[c] = false;
        in_untried[c] = true;
    }
}

int main(int argc, char* argv[]) {
    ORDER = (argc > 1) ? atoi(argv[1]) : ORDER_VAL;
    memset(placed, false, sizeof(placed));
    memset(excluded, false, sizeof(excluded));
    memset(in_untried, false, sizeof(in_untried));

    // Place plinth at (0, 0)
    placed[encode(0, 0)] = true;
    n_placed = 0;
    x_sum = 0;

    // Initial untried: y >= 1 neighbors of (0, 0) = just (0, 1)
    int init_untried[4];
    int init_sz = 0;
    for (int d = 0; d < 4; d++) {
        int nx = dx[d], ny = dy[d];
        if (ny < 1 || ny > MAXC || nx < -MAXC || nx > MAXC) continue;
        int nc = encode(nx, ny);
        init_untried[init_sz++] = nc;
        in_untried[nc] = true;
    }
    sort(init_untried, init_untried + init_sz);

    dfs(init_untried, init_sz);

    long long answer = (result_total + result_sym) / 2;
    if (argc > 1) {
        printf("ORDER=%d: total=%lld sym=%lld answer=%lld\n",
               ORDER, result_total, result_sym, answer);
    } else {
        printf("%lld\n", answer);
    }
    return 0;
}

Python project_euler/problem_275/solution.py

"""
Problem 275: Balanced Sculptures

Order n = n blocks + 1 plinth = n+1 tiles.
Plinth at (0,0). Blocks at y >= 1. Connected polyomino.
x_sum of blocks = 0. Reflections about y-axis identified.

Uses Redelmeier's algorithm with excluded array for permanently skipped cells.

Note: This Python version is significantly slower than the C++ version.
For ORDER=18, use the C++ solution.
"""

import sys
sys.setrecursionlimit(1000000)

ORDER = 18
MAXC = 20
W = 2 * MAXC + 1
H = MAXC + 1

DX = [0, 0, -1, 1]
DY = [-1, 1, 0, 0]

def encode(x, y):
    return y * W + (x + MAXC)

def dec_x(c):
    return c % W - MAXC

def dec_y(c):
    return c // W

MAXCELLS = H * W
placed = [False] * MAXCELLS
excluded = [False] * MAXCELLS
in_untried = [False] * MAXCELLS

result_total = 0
result_sym = 0

cells_arr = [0] * 25
n_placed = 0
x_sum = 0

def dfs(untried):
    global n_placed, x_sum, result_total, result_sym

    if n_placed == ORDER:
        if x_sum == 0:
            result_total += 1
            sym = True
            for i in range(ORDER):
                x = dec_x(cells_arr[i])
                y = dec_y(cells_arr[i])
                mirror = encode(-x, y)
                if not placed[mirror]:
                    sym = False
                    break
            if sym:
                result_sym += 1
        return

    remaining = ORDER - n_placed
    if abs(x_sum) > remaining * MAXC:
        return
    if not untried:
        return

    c = untried[0]
    cx = dec_x(c)
    cy = dec_y(c)

    # Branch 1: Add c
    placed[c] = True
    in_untried[c] = False
    cells_arr[n_placed] = c
    n_placed += 1
    x_sum += cx

    added = []
    for d in range(4):
        nx = cx + DX[d]
        ny = cy + DY[d]
        if ny < 1 or ny > MAXC or nx < -MAXC or nx > MAXC:
            continue
        nc = encode(nx, ny)
        if not placed[nc] and not excluded[nc] and not in_untried[nc]:
            in_untried[nc] = True
            added.append(nc)

    added.sort()
    new_untried = []
    ai = 0
    for i in range(1, len(untried)):
        while ai < len(added) and added[ai] < untried[i]:
            new_untried.append(added[ai])
            ai += 1
        new_untried.append(untried[i])
    while ai < len(added):
        new_untried.append(added[ai])
        ai += 1

    dfs(new_untried)

    n_placed -= 1
    x_sum -= cx
    placed[c] = False
    for nc in added:
        in_untried[nc] = False

    # Branch 2: Skip c
    excluded[c] = True
    in_untried[c] = False
    dfs(untried[1:])
    excluded[c] = False
    in_untried[c] = True

def solve():
    global n_placed, x_sum

    # Place plinth at (0, 0)
    placed[encode(0, 0)] = True
    n_placed = 0
    x_sum = 0

    # Initial untried: y >= 1 neighbors of (0, 0) = just (0, 1)
    init_untried = []
    for d in range(4):
        nx, ny = DX[d], DY[d]
        if ny < 1 or ny > MAXC or nx < -MAXC or nx > MAXC:
            continue
        nc = encode(nx, ny)
        init_untried.append(nc)
        in_untried[nc] = True
    init_untried.sort()

    dfs(init_untried)

    answer = (result_total + result_sym) // 2
    print(answer)

if __name__ == "__main__":
    solve()