Maximizing number of selected squares in a grid

Question

We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected square has a number of selected neighbours less than or equal to its number.

Is there a known way to find the maximum number of elements in a good selection? Clearly there is a $\mathcal O(2^{n^2}n^2)$ brute force algorithm (we can test for goodness of a selection in time $\mathcal O (n^2)$ by precomputing number of selected squares in each row and column).

Answer 1

There is a dynamic programming algorithm whose running time is $O(2^{4n})$.

Suppose we have already chosen a configuration for the first $i$ columns. Mark a cell in the $i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" if the cell to its right can be selected.

Let $c \in \{R,G\}^n$ be a sequence of $n$ colors, and $x \in \{0,1\}^n$ be a sequence of $n$ bits. Define $A[i,c,x]$ to be the maximum number of elements in a good selection for the first $i$ columns that induces the coloring $x$ on the $i$th column and where $x$ describes which cells are selected in the $i$th column. Then it is easy to calculate $A[i+1,c',x']$ from $A[i,c,x]$: we have

$$A[i+1,c',x'] = |x'| + \max_{c,x} A[i,c,x],$$

where the max is taken over all $c,x$ that are consistent with $c',x'$ (i.e., such that it's possible to have a selection for the first $i+1$ columns that has selection $x$ in column $i$, selection $x'$ in column $i+1$, colors $c$ in column $i$, and colors $c'$ in column $i+1$). To be consistent, we must have $c_j=R \implies x'_j=0$ for all $j$, and $x_j + x'_{j-1} + x'_{j+1}$ must be at most the number in column $i+1$, row $j$ (and $c'_j=R$ iff they are equal).

This yields a dynamic programming algorithm with $O(n \times 2^{4n})$ running time: we need to fill in $n \times 2^{2n}$ entries of $A[\cdot,\cdot,\cdot]$, and each entry requires us to compute a max over at most $2^{2n}$ numbers.