Extremal fences with polyforms

Source: arXiv:2607.22379 · Published 2026-07-24 · By Alexis Langlois-Rémillard, Mia N. Müßig, Érika Roldán

TL;DR

This paper explores an isoperimetric problem in discrete geometry concerning polyforms — connected subsets of tiles in the three regular plane tessellations: squares (polyominoes), hexagons (polyhexes), and triangles (polyiamonds). The core question asks for the maximum area that a fence composed of given polyforms (sets of polyforms arranged to enclose a region) can enclose. The authors present a series of challenges starting from tetrominoes and pentominoes on square grids, and extend to tetrahexes and hexiamonds on hexagonal and triangular grids respectively. They revisit and translate Shimauchi's classical 1978 proof that the maximum enclosed area achievable by a fence built from all 12 pentominoes is 128 square tiles.

A significant contribution is the formulation of these fence challenges as integer linear programming (ILP) problems, solved with modern solvers such as Gurobi, allowing exhaustive enumeration of maximum-area fence configurations and verification of Shimauchi's bound. They also enumerate the number of maximal fence configurations achieving the global optima for each polyform set: 1440 for pentominoes enclosing 128 tiles, 2 for tetrahexes enclosing 35 tiles, and 546 for hexiamonds enclosing 116 tiles. Beyond providing new geometric insights and computational methods for extremal polyforms, the authors propose multiple open challenges in higher dimensions and larger polyforms, demonstrating the complexity and richness of these discrete isoperimetric problems.

Key findings

• Shimauchi's proof from 1978 that the maximum interior area enclosed by a fence made of all 12 pentominoes is exactly 128 tiles is confirmed and translated to English.
• The number of distinct fence configurations that achieve the maximal enclosed area 128 with pentominoes is exactly 1440.
• Extremal fence configurations enclosing 35 tiles with tetrahexes number 2 distinct arrangements.
• Extremal fence configurations enclosing 116 tiles with hexiamonds number 546 distinct arrangements.
• An ILP formulation enables enumeration and verification of all maximal fence configurations for small polyforms in all three regular plane tessellations.
• All pentomino extremal fence configurations fit inside a 20×20 square, bounding the search space.
• The maximal fence perimeter for pentomino configurations is 52 tiles, constrained by geometric properties of the polyforms.
• Attempts to solve the hexomino fence problem via ILP required two months of computation to find a fence enclosing 1586 tiles, close but not verified maximal, illustrating computational complexity.

Threat model

n/a — The work is a mathematical and computational exploration of isoperimetric extremal problems for polyforms. No security adversary or attacker considered.

Methodology — deep read

The paper focuses on an extremal combinatorial geometry problem involving polyforms—polyominoes (square tiles), polyhexes (hexagonal tiles), and polyiamonds (triangular tiles) on the three regular plane tessellations. The problem is to arrange a fixed set of polyforms as a fence enclosing a maximal interior area, subject to topological constraints that the complement set of tiles splits into exactly two connected polyforms with no shared vertices.

1. Threat Model & Assumptions: The adversary analogy does not apply; the problem is combinatorial, exploring maximal area enclosures given a fixed polyform set. Assumptions include a strict definition of fences where interior and exterior are separated and complements form exactly two connected components. Polyforms can be rotated and flipped.

2. Data: The base polyform sets include the 5 tetrominoes, all 12 pentominoes, the 7 tetrahexes, and 12 hexiamonds. No randomness—problems are deterministic combinatorial constructions. The search space is over finite board regions (e.g., 20×20 for pentominoes). Extensive handouts and an interactive web app support user experiments.

3. Architecture / Algorithm: The core technical contribution is an ILP model encoding fence construction constraints:

   • Variables: binary variables xl denote tile interiors, yl denote fence tiles, and zl encode placement of polyforms with a given orientation covering a tile.
   • Constraints: (a) interior tiles' neighbors are either also inside or part of fence, (b) no tile is both fence and interior, (c) each polyform placed exactly once without overlap, (d) fence tiles are exactly those covered by polyforms, (e) exterior board edges are neither interior nor fence.

4. Training Regime: Not applicable; this is a combinatorial optimization solved by ILP solvers. The implementation uses Gurobi with careful region size choices (e.g., 22×22 for pentominoes) to balance tractability and completeness.

5. Evaluation Protocol: Maximize the sum of interior tiles, compare to known maxima and Shimauchi's proof. Enumeration of maximum fence configurations is possible. Some challenges remain open for larger polyforms due to combinatorial explosion.

6. Reproducibility: The authors provide open-source code repositories for the ILP model and companion interactive app. Shimauchi's original proof is translated and presented in detail for validation. The datasets are public polyform enumerations. The model does not ensure connected interior but relies on heuristic assumptions that maximal solutions will be connected.

A concrete example is the pentomino fence challenge: using all 12 pentominoes, the ILP encodes tile assignments and polyform placements on a 22×22 region. The solver maximizes the interior area subject to fence constraints and confirms that the maximum area is 128 tiles, agreeing with Shimauchi's proof. Further analysis partitions pentominoes into families by geometric properties to tighten bounds and optimize ILP size.

Technical innovations

• A generalized ILP formulation encoding fence building from polyforms across multiple plane tessellations, supporting rotations and flips.
• Translation and computer-aided verification of Shimauchi's 1978 pentomino fence maximal area proof.
• Enumeration of maximal fence configurations at scale using ILP solvers providing exact combinatorial counts.
• Extension of the fence problem framework from squares to hexagonal and triangular tessellations with new extremal solutions.

Datasets

• Tetrominoes — 5 pieces — standard polyforms
• Pentominoes — 12 pieces — standard polyforms
• Tetrahexes — 7 pieces — hexagonal tessellation
• Hexiamonds — 12 pieces — triangular tessellation

Baselines vs proposed

• Gardner's pentomino fence solution (area 127) vs Shimauchi's maximum (area 128)
• ILP confirmed Shimauchi's max area: 128 tiles with pentominoes vs Gardner's 127
• Tetrahex fence maximum area: ILP found 35 tiles (2 configurations)
• Hexiamond fence maximum area: ILP found 116 tiles (546 configurations)
• Hexomino fence: best known ILP solution encloses 1586 tiles after 2 months vs unknown true maximum

Limitations

• ILP model does not enforce connectedness of enclosed interior area, relying on heuristics that maximal solutions are connected.
• Computational complexity rapidly grows with polyform size and variety, currently limiting solving beyond pentomino/tetrahex/hexiamond sets.
• Shimauchi-style geometric arguments and ILP remain challenging to scale to 3D or non-Euclidean tessellations.
• Proofs and enumerations rely on bounding the search region (e.g., 20×20 squares)—extreme solutions outside the bounding box might be missed theoretically.
• No adversarial or robustness analysis; focus is purely combinatorial maximal area construction.
• Some open problems (e.g., hexomino fence global maximum, min-max fence configurations) remain unsolved due to combinatorial explosion.

Open questions / follow-ons

• Can Shimauchi’s proof technique and ILP approach be adapted to prove maximal fence areas for tetrahex and hexiamond fence problems?
• What is the exact maximum enclosed area for hexomino fences, and can computational techniques be scaled to solve this?
• Can the connectedness constraint on the interior be efficiently encoded and solved in ILP or SAT frameworks without prohibitive slowdown?
• How do these discrete fence problems generalize to higher dimensions (e.g., pentacubes) and non-Euclidean tessellations?

Why it matters for bot defense

While this paper addresses pure combinatorial geometry, the underlying techniques bear relevance to CAPTCHA and bot-defense practitioners involved in combinatorial puzzle generation and verification. The ILP modeling approach and solver usage illustrate how complex discrete layout and packing constraints can be effectively encoded and optimized, a method similarly applicable when generating or verifying human-solvable but bot-hard puzzles such as CAPTCHAs involving polyform placements or tiling puzzles. Understanding exact maximal configurations and complexities informs designers about the combinatorial hardness and uniqueness of solutions, key factors for CAPTCHA strength. The collaboration of geometric insight with computational proofs demonstrated here could inspire rigorous CAPTCHA challenge designs that integrate spatial reasoning and topology constraints with provable hardness. However, the direct application requires adaptation, since this work does not deal with adversarial attacks or human interaction modeling.

Cite

@article{arxiv2607_22379,
  title={ Extremal fences with polyforms },
  author={ Alexis Langlois-Rémillard and Mia N. Müßig and Érika Roldán },
  journal={arXiv preprint arXiv:2607.22379},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.22379}
}

Read the full paper

• arXiv:2607.22379 (abstract)
• arXiv:2607.22379 (PDF)