# What is the smallest polyomino that can't surround a $1\times 1$ hole?

Given a polyomino $$P$$, we can ask if it is possible for disjoint copies of $$P$$ to surround a single cell in the square grid - i.e., for the complement of their union to have a connected component of size $$1$$.

We can further refine this into polyominoes that weakly surround a cell (just covering the four edge-adjacent cells) and those that strongly surround a cell (covering all $$8$$ squares which share a vertex with the hole). Thanks to Julian Rosen for clarifying this distinction.

My original intuition was that this is always possible, but I was having trouble proving it; after enough struggling to show it was true, I started searching for counterexamples. Here is a polyomino with $$48$$ cells which does not even weakly surround a one-celled region, which is not too difficult to verify by hand:

After some modifications, I've reduced this down to a simply-connected solution with $$26$$ cells:

I have a size-$$23$$ example of a polyomino which does not strongly surround a hole:

What is the smallest polyomino that cannot surround a single-celled hole? I am interested in this question for both the weak and strong cases.

I've written some code to explore this, and have confirmed that all of the $$1,227,708$$ free polyominoes on at most $$14$$ cells can strongly surround a hole. How much can we tighten these bounds?

• I am not asking whether polyominoes tile the plane; I'm asking whether the complement of disjoint copies of them can have connected components of size $1$. Here is an image of a polyomino surrounding a $1\times 1$ hole, for reference. Commented Jan 15, 2021 at 16:46
• Is it correct that to surround a square, we should cover the 8 adjacent squares (including the diagonally adjacent ones)? Commented Jan 15, 2021 at 22:24
• This is just a idle thought, but what about looking at the problem in reverse; i.e., given a unit square hole (either weakly or strongly surrounded), establish some kind of constraint on how its neighbors may be connected, which in turn limits the features of a polyomino that cannot leave such a hole. Perhaps this is too nebulous or difficult but it was just something that seemed to offer a different perspective than generating polyominoes and then seeing if they can be arranged to leave such a hole. Commented Feb 1, 2021 at 20:54
• Your size-$23$ upper bound is nicely symmetric. It would be easier to verify (if true) that there are no smaller examples with that symmetry. Commented Feb 2, 2021 at 22:07
• I just wanted to comment on what a nicely formulated problem this is (can't +1 more than once!) It's simply stated but the answer is non-trivial. Also, in a sense this is the hardest problem of this type. A natural generalization is to look for minimal polyominoes that cannot (strongly) surround a hole of shape $P$, for some polyomino $P$. For all $P$ with size > $1$ that I've checked, the minimal polyominoes have size $\le 11$, making them easy enough to find through exhaustive search. Commented Feb 5, 2021 at 18:54

This is by no means a complete answer, but as I mentioned in my last comment, we can make some headway by restricting a computer search to particular symmetry classes. I've been able to check all the free polyominoes of size $$N \le 23$$ that have a horizontal or vertical symmetry axis (a class that contains OP's size-$$23$$ non-strongly-surrounding example). Within this symmetry class, there are no non-weakly-surrounding examples of size $$N \le 23$$, and the smallest non-strongly-surrounding examples have size $$N=23$$; so OP's example is minimal. Of the $$464188$$ size-$$23$$ free polyominoes with a horizontal or vertical axis of symmetry, there are just two that cannot strongly surround a single cell: the example given in the question, and the polyomino pictured below.

Heuristically, one might expect minimal examples to have some symmetry, because symmetric polyominoes have the fewest "different-looking local regions", and hence the fewest different possibilities for packing local regions around a hole. Next steps, then, might be to check the other two large symmetry classes for free polyominoes: $$180^\circ$$ rotational symmetry around a point, and reflection symmetry across a diagonal.

Update: Checking the polyominoes with rotational symmetry around a point turned up the following minimal (within that class) non-strongly-surrounding example, with size $$20$$:

Second update: Checking the polyominoes with a diagonal reflection symmetry, there are exactly two minimal (within that class) non-strongly-surrounding examples with size $$19$$. One is formed by removing an interior cell from the previous example (as already pointed out in a comment), and the other is new:

Third update: In order to make progress on the non-weakly-surrounding case (which is a more stringent criterion, so the minimal examples are at least as large), I looked at polyominoes with both vertical and horizontal reflection symmetries. The size-$$25$$ example below provides an improved upper bound for this case.

• Thanks for this investigation! I notice that both your example and the one in the OP have the line of reflection passing through a cell; did you also check cases where the line coincides with edges between cells? (Obviously this doesn't have $N=23$ examples, since the number of cells must be even, but perhaps it does for lower even $N$.) Commented Feb 4, 2021 at 15:56
• @RavenclawPrefect: Yes, the reflection-symmetric cases do include both types of line; I checked polyominoes of both even and odd width. Commented Feb 4, 2021 at 16:29
• You can remove one of the central squares in your last picture to get a size-19 example. It loses its rotational symmetry, of course, but it's still symmetric about one of its diagonals. Commented Feb 4, 2021 at 16:38
• Would this size-16 version not work, then? It also has 180 degree rotational symmetry, but I'm struggling to see how it fails. Commented Feb 4, 2021 at 16:51
• @MishaLavrov: It can strongly surround a hole as shown here. Commented Feb 4, 2021 at 17:09