# Most polyominoes in an 8x8 grid

What is the most number of distinct free polyominoes you can form by painting an 8x8 grid in two colours? Here a polyomino is a set of orthogonally adjacent cells of the same colour, so polyominoes of the same colour cannot share an edge. Two free polyominoes are considered distinct if they are not a rigid transformation (translation, rotation, reflection, glide-reflection) of each other. Polyominoes of the same shape, but different colours are not considered distinct.

• Please update the description to specify that polyominoes of the same color cannot share an edge and also to clarify whether polyominoes of different colors are considered distinct. Commented Mar 12, 2023 at 16:26
• Added the requested clarifications. Commented Mar 13, 2023 at 10:44
• Are zero-square polyominoes allowed? Commented Mar 13, 2023 at 14:29

I believe 14 15 is the best possible (but I can't quite rule out 16).
Edit: OK, I found a solution with 16. This matches the knapsack upper bound and is definitely optimal:

16:

15:

14:

• This is very nice work! I am particularly impressed that you got some hexominoes in there. Commented Mar 12, 2023 at 5:54
• @DmitryKamenetsky Thanks. I actually found that 15 is possible. Commented Mar 12, 2023 at 6:39
• wow 15 is incredible! There are some big ones (including an 8), so I feel that 16 is possible... Commented Mar 12, 2023 at 7:04
• For example a white vertical domino can fit in the bottom right without affecting the count Commented Mar 12, 2023 at 7:16
• @justhalf Think greedy algorithm. You have 1x polyomino with 1 piece, 1 with 2, 2 with 3, 5 with 4 ... so you first take smaller and then go towards bigger ones. You can easily see that 16th will get total area to 64 already so you cannot possibly squeeze one more. Commented Mar 13, 2023 at 8:17

If polyominoes of the same color can share an edge and polyominoes of different colors are considered distinct, the maximum is

19, with 2 each of the 9 free polyominoes of size at most 4, and 1 free pentomino:

Under the intended interpretation (polyominoes of the same color cannot share an edge and polyominoes of different colors are not considered distinct), the maximum is

16:

If polyominoes of the same color cannot share an edge and polyominoes of different colors are considered distinct, the maximum is

19:

• As I read the problem I thought that two polyominoes of the same color could not share an edge. Otherwise the restriction to two colors does not matter as your solution shows. This is a good solution to another problem, so +1 Commented Mar 12, 2023 at 5:29
• Actually Ross is correct - that was my original intention of the problem. This solution is still interesting though, so +1. Commented Mar 12, 2023 at 5:30
• This is also a great answer, but I am accepting the other one as it was earlier. Commented Mar 13, 2023 at 11:29