10x10 grid with no unpainted hexominoes

What is the smallest number of cells you need to paint in an 10x10 grid, such that it contains no unpainted hexominoes? Note that a hexomino is a set of 6 adjacent cells (horizontally or vertically).

Here is a similar puzzle for pentominoes on an 8x8: 8x8 grid with no unpainted pentominoes

Good luck!

• This doesn't appear to me like it has a natural 'path' to the solution - are you sure it does? It looks like this is best solved with programming rather than any sort of human insight.
– Deusovi
Commented Oct 13, 2019 at 17:42
• @Deusovi This is not a logic puzzle. It does not necessarily have a single best solution, let alone a 'natural path'. The solution I have posted was found entirely with pen and paper, and I enjoyed it. It might not be optimal, but that's not the point. If you enjoy this kind of puzzle, have at it. If not, just pass it by. Your criticism seems contrary to acceptance without any real purpose. Commented Oct 13, 2019 at 18:28
• @DanielMathias I agree that it's not a logic puzzle! But I think all questions should have some sort of 'path' to the solution, whether that's hints built into a "What Is A ___ Word™" question. As for optimality, the question literally asks for the "smallest number of cells you need" -- optimality is the whole point. And I'm not sure optimality can be found in any other way than by computer search.
– Deusovi
Commented Oct 13, 2019 at 18:31
• @Deusovi The search (manual or otherwise) for the best solution is the point. Whether we find an optimal solution, or prove it optimal if we do, is in my opinion secondary. Not knowing if my solution is optimal will allow me to enjoy an attempt to find a better. I agree that puzzles with a specific or singular solution should have a logical path, this puzzle simply isn't in that category. Commented Oct 13, 2019 at 18:42

One very efficient way to separate areas by squares is to put them in diagonal lines. This utilises the diagonal, which is the longest dimension of the square.

Also, you can divide the plane into separate X-pentominoes (which have the maximum allowed connected area) by using diagonals of squares only.

That pentomino pattern has the annoying property that choosing any 10x10 square tends to bring in an overly paint-filled edge row. However, it's possible to "change the parity" of the pattern at one of the diagonals, which gives edges with no more than 3 painted squares on any of them.

While I have no proof that this is the best answer, the above observations give a reason to guess that this is likely to score pretty well:

The pattern has a total of

35 coloured squares.

EDIT: After giving it a couple of tries, any variation based on the X-pentomino seems to result in this exact solution after a couple of optimisations.

My best, but is it optimal?

Thirty seven painted tiles.

By using integer linear programming as in my answer to Least number of marked symbols, I found the following optimal values for $$n\in\{1,\dots,10\}$$: $$\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \min & 0 & 0 & 3 & 5 & 8 & 12 & 17 & 22 & 28 & 35 \\ \end{matrix}$$

• Thank you for your nice work. Please consider adding this to the OEIS. Commented Aug 27, 2020 at 1:22
• perhaps this is related to this sequence: oeis.org/A282513 Commented Aug 30, 2020 at 10:14
• @DmitryKamenetsky I submitted oeis.org/A337520, as well as the corresponding sequences for smaller polyominoes: oeis.org/A337501, oeis.org/A337502, oeis.org/A337503 Commented Aug 30, 2020 at 13:52
• That's great work! Perhaps we can add a file with all the best solutions. I've submitted a comment to A282513. It hasn't been approved yet, so should I remove it? Commented Aug 30, 2020 at 14:09