This is a follow-up to the question How good can a "near-miss" polyomino packing be?.
Let $P$ be the heptomino shown below:
I am interested in the packing density of $P$ on the square grid. (Unlike all polyominoes on $6$ or fewer cells, $P$ does not tile the plane, so by a compactness argument this density must be strictly less than $1$.) The following packing, due to user nickgard here, attains a density of $14/15$:
On the other hand, $P$ cannot cover every cell on the following $65$-cell region, as can be verified by a computer search:
This means that the packing density of $P$ must be at most $64/65$. (Edit: To make this clearer, I've sketched out a more formal argument for why this is the case here.)
How much can we tighten these bounds? There may be smaller regions that $P$ does not cover, but I do not think there will be any size-$15$ ones, so I expect that new techniques will be needed to get an exact answer here.
Only a partial answer, but will hopefully spur discussion. I ran a heuristic search algorithm that tries to maximize the density over a rectangle of a fixed size with periodic boundary conditions. (Of course, tiling such a rectangle is sufficient to tile the plane, but this excludes any potential aperiodic tilings). The algorithm did recover the 14/15 tiling but did not find any better ones. Two tilings found by the algorithm are shown below, together with their densities. The first one shown is the second-best tiling after the 14/15 one, although it is rather uninteresting in that it it just several copies of that tiling stuck on top of each other, with rows 2 and 3 breaking the pattern. The second one is the best tiling that did not look like an obvious ``rip off" of the 14/15 one, although parts of it still strongly resemble that one.
The algorithm is very simple and I imagine could be improved considerably. Starting from a fixed tiling, it generates a number of new candidate tilings and then updates to the best among the candidate tilings (best in the sense of covering the greatest number of squares). To encourage exploration, there is also a small chance that at any step it will select a random candidate instead. To generate the candidates, I remove up to two randomly-selected tiles, and then try to add in up to two tiles in different locations or in different orientations than the removed tiles.
The real difficulty seems to be how to sample the candidates in a good way. As far as I can tell the large and irregular shape of the tiles means that there isn't an obvious way to locally modify a tiling to get another tiling. If there were, then I imagine that MCMC (or the heuristic algorithm above) would work quite well. So if you already have a pretty dense tiling, then it will be hard to move to a very dense tiling without some violent transformation of the tiling, making it difficult to explore the space of tilings.