ILP Part 101 — Polyominoes

This is the one hundred and first part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we’re going to solve Polyominoes. We have a set of polyominoes that needs to enclose an area of the greatest possible area. Let’s see the solution:

We start with the definition of pieces (lines 1-32). They are encoded as strings so we can rotate them easily later on. Next goes a couple of helper variables.

Our model has three sets of variables. First is heads that indicates if a given piece was put on a board at a given place with a given rotation (lines 42-50).

Next, we have bit flags indicating if a given field belongs to the interior of the enclosed area (lines 52-56), and similar flags for the boundary (58-62).

Next, we have a helper function to rate a piece (lines 64-78).

And then we go with rules. First, we make sure that each piece is put somewhere. So we sum all of the flags for each piece, and set it to one (lines 80-94).

Then, we need to make sure that we don’t put pieces too close to the boundary. We set corresponding flags to zer (lines 96-122).

Next, we need to exclude some invalid solutions. First, for every field we calculate which pieces could “impact it”. So we check all the positions of all the pieces in the all possible rotations, and store the result in a helper array. This is in lines 124-154.

Now, we can make sure that there is a boundary. It needs to be only in the fields covered by the polyominoes, and nowhere else. So we take all the pieces that impact a given field, and make sure that the boundary is set to the sum of those. This is in lines 156-165.

Next, we need to make sure that pieces do not overlap. So for each field we make sure that there is at most one impacting piece selected (lines 167-177).

Next, we extend the interior. We encode the logic that if a given field is internal and there is a field right next to it that is not on the boundary, then the neighbouring field must be internal as well. This is in lines 180-210. We also need to make sure some fields are external (lines 212-226). We do it for a whole “frame” encompassing the board, otherwise the solver might decide to put everything “inside-out”, so the interior is actually the exterior that is implicitly bounded by the area outside of the board.

This works in the following way. When a field is truly in the interior, then it will expand as much as possible. However, fields outside of the shape cannot be marked as internal because then there would be a case of neighbours of the frame. We take any field which is right next to the frame, and since the frame is not on the boundary, it needs to be marked as internal as well. However, we explicitly block that.

Finally, we need to make sure there are no fields that are both interior and boundary (which otherwise would be allowed and might change the optimal solution). This is in lines 228-239).