Optimal Polyomino Fences
The $n$-omino fence problem asks how many cells can be surrounded by placing every $n$-omino exactly once in the grid. We present a new dynamic programming approach for this problem, allowing us to prove optimality for the pentomino and hexomino fence and to classify all possible pentomino orders by optimal area. For the first time we also provide strong heuristic solutions and upper bounds for all fences up to $n = 15$, after which we even approximate the $500$-omino fence with computational experiments. Finally, we generalize the problem to 3D, where we prove optimality for pentacubes and derive heuristic solutions for hexacubes and heptacubes.
Authors
- Alexis Langlois-Rémillard (ORCID: https://orcid.org/0000-0002-5919-8766)
- Zhi Ying Daniel Yu
- Maximilian Prietzel
- Günter Rote (ORCID: https://orcid.org/0000-0002-0351-5945)
- Helmut Podhaisky (ORCID: https://orcid.org/0000-0002-8030-421X)
- Mia Müßig
- Érika Roldán
- Mykhailo Lyader
- Matthes Norden
- Maximilian Brömme
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16883
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint