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?

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

1 Answer 1


Because you want to maximize the number of active grey squares, we can ignore inactive grey squares. We can also ignore black squares.

Here is a highly symmetric coloring with $80$ active grey squares: enter image description here

And here's a rotationally symmetric coloring with $82$: enter image description here

But the maximum turns out to be $83$, obtained via integer linear programming: enter image description here


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .