# Filling a grid with skinny trominoes which have arrows on their ends

Let's have a 10x10 square grid with 7 empty small squares. This grid is to be filled with skinny trominoes which have arrows at their ends (see figure 1). What is the maximum number of arrows which can point at the empty squares? You can place the 7 empty squares anywhere on the grid. Below is a 10x10 grid with 4 arrows pointing at the empty squares.

• It only counts if the arrows are directly adjacent to the empty squares, then?
– Deusovi
Oct 16, 2021 at 19:14
• Also, do you have reason to believe there is a 'nice' logical solution here? This seems like a tricky optimization problem that doesn't necessarily have a clean deductive path.
– Deusovi
Oct 16, 2021 at 19:15
• The arrows point directly at the empty squares. They are numbered in the diagram. Oct 16, 2021 at 19:23

The maximum is

$$2+1+3+4+3+4+4=21$$

 1  2  2  3  3  .  4  4  5  5
1  1  2  3  6  6  .  4  5  7
8  8  .  9  6 10 10  .  7  7
8 11 12  9  9 10 13 14 15 15
11 11 12 12  . 13 13 14 14 15
16 16 17 17 18 19 20 20 21 21
22 16 17 18 18 19 19 20 21 23
22 22  . 24 24 25 25  . 23 23
26 26 27 28 24 25 29 30 31 31
26 27 27 28 28 29 29 30 30 31


I obtained this solution via integer linear programming, with a binary decision variable $$x_t$$ for each of the $$(10-1)^2 \cdot 4=324$$ possible trominoes, a binary decision variable $$y_{i,j}$$ for each of the $$10^2=100$$ cells to indicate whether that cell is empty, and a binary decision variable $$z_{t,i,j}$$ to indicate whether tromino $$t$$ is selected and points to empty cell $$(i,j)$$. Let $$T_{i,j}$$ denote the set of trominoes that contain cell $$(i,j)$$. The problem is to maximize $$\sum_{t,i,j} z_{t,i,j}$$ subject to linear constraints: \begin{align} \sum_{t\in T_{i,j}} x_t + y_{i,j} &= 1 \tag1 \\ \sum_{i,j} y_{i,j} &=7 \tag2 \\ z_{t,i,j} &\le x_t \tag3 \\ z_{t,i,j} &\le y_{i,j} \tag4 \end{align} Constraint $$(1)$$ forces each cell to be covered by exactly one tetromino or to be empty. Constraint $$(2)$$ forces exactly $$7$$ cells to be empty. Constraints $$(3)$$ and $$(4)$$ enforce the logical implication $$z_{t,i,j} \implies (x_t \land y_{i,j})$$.

To kickstart,

There is a way for an empty square to be pointed by 4 arrows at once, but needs 5x5 area. Thus if there are only 4 empty squares, we can get a perfect 16 points.

But as we are given 7 empty squares,

I tried to put the empty squares on the right-bottom quadrant as the following:

Which gives a total of

20 points.