CODEWITHSUNDEEP
algorithm
alaj
alaj

Reputation: 187

How to determine layout that yields maximum number of squares inside a larger grid

I am trying to determine what algorithm to use to determine the layout that yields the maximum number of 2x2 square grids that can fit inside a larger non-uniform grid. The image below shows an example of a non-uniform grid (black lines) with a maximum of 12 fitted 2x2 square grids (blue boxes). Is there a systematic approach to determine the layout that yields maximum capacity? As can be seen in the image below the 2x2 square grids do not need to be horizontally or vertically aligned. Thanks!

enter image description here

Upvotes: 1

Views: 86

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

I'd try an integer program solver, (e.g., OR-Tools).

The formulation I have in mind is pretty standard. Let's suppose we have a grid with labeled squares like

  ab
cdefgh
ijklmn

For each square that can be the the upper left corner of a 2x2 (a, c, d, e, f, g), we have a 0-1 variable that will be 1 if that square is chosen and 0 otherwise. For every square, we have a constraint that the sum of variables of 2x2s overlapping that square is at most 1.

a ≤ 1            (a)
a ≤ 1            (b)
c ≤ 1            (c)
c + d ≤ 1        (d)
a + d + e ≤ 1    (e)
a + e + f ≤ 1    (f)
f + g ≤ 1        (g)
g ≤ 1            (h)
c ≤ 1            (i)
c + d ≤ 1        (j)
d + e ≤ 1        (k)
e + f ≤ 1        (l)
f + g ≤ 1        (m)
g ≤ 1            (n)

And naturally we want to maximize the sum of the variables:

max a + c + d + e + f + g

Upvotes: 2

Related Questions