# 2D packing problem, as a puzzle.

I have discovered a 2D packing problem that I cannot find the tools online to solve, so I have decided to present it to the Mathematics Stack Exchange as a fun puzzle.

In this problem there exist 4 possible different colors of squares, each 1 length unit by 1 length unit in size, on a 2d grid with size 12x12 length units^2: Red, blue, black and grey. This packing problem has, however, special rules to go along with it:

1. Red squares may not share any sides with blue squares, or they will transform into black squares.
2. Black squares have no interactions whatsoever and are, for the purposes of this problem, hindrances.
3. Grey squares are outliers in that they can assume and maintain an 'active' state when sharing sides with at least one red square and one blue square (it is irrelevant if on adjacent or on opposite sides of the grey square). Otherwise they assume and maintain an 'inactive' state.
4. It is not necessary for the 12x12 grid to be completely filled with squares.

What is the highest packing density of grey squares in the 'active' state that can be achieved given the conditions and rules specified above, and what does this most optimal packing look like visually?

Additional challenge: If the grid is expanded to infinite size in both positive and negative directions on both axes, how does the optimal packing change?

• Yes, 'touching' means 'two squares share a side' in this case. I will amend that to my question. Nov 6, 2022 at 23:08

Here is a highly symmetric coloring with $$80$$ active grey squares: And here's a rotationally symmetric coloring with $$82$$: But the maximum turns out to be $$83$$, obtained via integer linear programming: 