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

Question

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.

Answer 1

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})$.

Answer 2

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.

Answer 3

Trial answer with

20 pointing arrows; four 5x5 regions maximizing their central squares and a corner modification that allows the remaining three gaps to get a decent number of points: