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

  • $\begingroup$ one optimization would be to generate the selections lexicographically and "skip" impossible selections as soon as a mistake is found. But this is not good when the numebrs on the grid are large. $\endgroup$
    – user26358
    Aug 22, 2017 at 23:37
  • 2
    $\begingroup$ (Assuming Yuval's guess.) If all squares have $0$, this is Independent Set, which is NP-complete. Hence, this problem is at least as hard (special case reduction). I'm sure there's a better algorithm than brute-force, though. $\endgroup$
    – Raphael
    Aug 23, 2017 at 7:49
  • 3
    $\begingroup$ @Raphael The problem is easy if all squares have 0, since it's a particular graph. The best you can do is pick a "generalized diagonal" consisting of $n$ vertices, one on each row and column. $\endgroup$ Aug 23, 2017 at 7:58
  • $\begingroup$ @YuvalFilmus Quite right, my bad. $\endgroup$
    – Raphael
    Aug 23, 2017 at 9:21
  • $\begingroup$ @D.W that sounds interesting, could you give a sketch of the dp? $\endgroup$
    – user26358
    Aug 24, 2017 at 19:36

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.