We claim the answer is $\boxed{15}.$ We can rephrase the problem as follows. Alice and Bob are playing a game on a $4 \times 9$ grids. Alice will select $18$ of the grid's cells to color black. Bob will then attempt to pair up as many pairs of squares which are differently colored and lie in the same row or column as possible. Find the maximum number of pairs that Bob can guarantee, regardless of which cells Alice colors. First we will see that Alice can prevent Bob from getting more than $15$ pairs. Indeed, if Alice simply colors the upper-left $3 \times 6$ grid black, Bob cannot pair the three squares in the lower-right $1 \times 3$ and hence can only get at most $15$ pairs. Now, we will show that Bob can always get at least $15$ pairs. For $0 \le i \le 4$, let $x_i$ be the number of columns with exactly $i$ black squares, so that $x_0 + x_1 + x_2 + x_3 + x_4 = 9.$ Note that Bob can pair up all the squares in a column with $2$ black squares. Also, Bob can always pair up all the squares in any two columns with a total of $4$ black squares (easy to check). In view of the above, if $x_0 = x_4$, then $x_1 = x_3$ and so we are done. From here, it's not hard to deduce that Bob can leave at most $6$ squares unpaired, and we're done. $\square$