# 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. Mar 12 at 16:26
• Added the requested clarifications. Mar 13 at 10:44
• Are zero-square polyominoes allowed? Mar 13 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. Mar 12 at 5:54
• @DmitryKamenetsky Thanks. I actually found that 15 is possible. Mar 12 at 6:39
• wow 15 is incredible! There are some big ones (including an 8), so I feel that 16 is possible... Mar 12 at 7:04
• For example a white vertical domino can fit in the bottom right without affecting the count Mar 12 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. Mar 13 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 Mar 12 at 5:29
• Actually Ross is correct - that was my original intention of the problem. This solution is still interesting though, so +1. Mar 12 at 5:30
• This is also a great answer, but I am accepting the other one as it was earlier. Mar 13 at 11:29