Correctness of the greedy algorithm

Question

I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of only 0's from it. A 1 in the sheet (represented by the matrix) indicates that we cannot cut the region out from the sheet. Given such a matrix, find the maximum number of blocks which can be extracted.

For instance, if the given matrix is:

There can be 2 blocks which can be extracted out of this.

My Solution:
I am using a greedy algorithm to solve the problem. I traverse from all the corners of the matrix (top-left, top-right, bottom-left, bottom-right) - one by one, extracting out the blocks on a first encountered first extracted basis. Finally I return the maximum of the 4 values that I get. From each corner, I traverse an entire row first (horizontally), only then I move up or down in the matrix.

The algorithm is as follows:

1) Starting from the top-left corner of the matrix (0,0), I iterate along all the columns
in this row from left to right. 

2) If a zero is encountered at a position (i,j), I check if this is a possible 
contender to be the top-left corner of a 2x2 block consisting of all zeros -
which would be the case when values at (i, j+1), (i+1, j) and (i+1, j+1) are all zeros.

3) If it is, I fill the 2x2 block {(i,j), {i,j+1), (i+1,j), (i+1,j+1)} with 1's, and a
counter is incremented.

4) Steps 2 through 3 are repeated for all rows from the top to bottom.

5) I restore the original matrix in the problem, and start again from the top-right corner 
of the matrix (0, N) - N being the number of columns in the matrix, and iterate along 
all the columns in this row, from right to left.

6) If a zero is encountered at a position (i,j), I check if this is a possible contender 
to be the top-right corner of a 2x2 block consisting of all zeros - which would be the 
case when values at (i, j-1), (i+1, j) and (i+1, j-1) are all zeros.

7) If it is, I fill the 2x2 block {(i,j), {i,j-1), (i+1,j), (i+1,j-1)} with 1's, and a
different counter is incremented.

8) Steps 6 through 7 are repeated for all rows from the top to bottom.

9) Likewise, the matrix is traversed two more times from bottom-left and bottom-right
corners, checking for a '0', which can be a possible bottom-right or bottom-left corner
for a 2x2 block consisting of all zeros. Each of these matrix traversals are performed on
the original matrix given in the problem - i.e. changes made in top-left traversal are 
discarded while traversing the matrix from top-right and so on.

10) The 4 traversals of the matrix give us 4 different counters, and the maximum of
these 4 values is returned as the result.

So far I have not been able to come with a test case which shows that the algorithm is incorrect. As I am not very good with proving correctness of algorithms, I need some help to figure out if this algorithm is correct.

Thanks!

Answer 1

If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.

But there is an 8 blocks solution (on the right).

---

The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.

Repeating the search in different directions will not fix this, as it is possible to build symmetric patterns that result to the same behavior in all directions.

Answer 2

The example provided by Valentin Lorentz can be slightly modified to break your solution for one order of traversal:

1 0 0 1
0 0 0 0 
0 0 0 0

You can build a larger test case that contains all 4 rotations of this one, so your greedy will mess up at least one of them.

Although I don't know a proof for NP-Hardness or anything of the kind, I highly suspect this problem does not have a polynomial solution. A similar problem that asked for 3x2 or 2x3 pieces can be found here: http://web.ics.upjs.sk/ceoi/documents/tasks/bugs-tsk.pdf.

Its solution, which is fairly sophisticated, uses dynamic programming and requires exponential time in one of the matrix's dimensions: http://web.ics.upjs.sk/ceoi/documents/tasks/bugs-sol.pdf

I'm 99% sure that your problem requires a similar approach.

An interesting case - and one that actually has a polynomial solution - is asking the same problem with 2x1 or 1x2 tiles (a.k.a domino pieces). Its solution is also more complicated than a simple greedy though.

Answer 3

My own solution to this problem:

Apparently this problem could be of an exponential type, and striving to find a fast solution might be hopeless. So my design approach is to allow a brute-force search at some place, while trying to find a reasonable heuristic when easy solutions are possible.

First shrink all the $2\times2$ blocks to their top-left cell, putting a $0$ when all four cells are $0$, and $1$ otherwise; the initial array will lose its last row and column. In image processing parlance, this is an erosion operation. It recasts the geometric reasoning from blocks to cells. [In what follows, a cell or a block are deemed to contain only zeroes, unless otherwise specified.]

Then, remark that two blocks can only be both counted if they don't overlap, i.e. if their corresponding cells are disconnected (not touching by an edge nor by a corner).

We can restate the problem as: "find a maximal subset of disconnected cells", or equivalently "remove a minimal number of cells so that the remaining ones are disconnected".

As an immediate consequence, we see that we should process separately all connected components in the array. This can be an important saving for fragmented cases. [Indeed, for a total of $N$ cells there are $2^N$ possible subsets. Assume they are forming connected components of sizes $N_1,N2,\cdots$ Then the number of subsets is $2^{N_1}2^{N_2}\cdots$ But if we process per-component and regroup the partial solutions as a hole, the number of possible subsets drops to $2^{N_1}+2^{N_2}+\cdots$ We trade multiplies for adds.]

The connected components and the cells that form them are easily enumerated by a seed-fill algorithm, such as $8$-ways recursion, seeding from a systematic scan of the array.

Now, for a single component, we will use brute force to remove a minimal subset. We do this by increasing number of removed cells, in an exhaustive way. So we use a combination generator that will output all combinations of a single cell, then of two, three... If the component is made of $K$ cells, the successive passes will include $K,\frac{K(K-1)}2,\frac{K(K-1)(K-2)}{3!}\cdots$ combinations, for a total of $2^K$. [This is where it can get nasty.]

For a given target combination, we proceed as follows: for every cell, initialize a counter telling how many connections it has. Then for every cell of the combination, decrement the counters of all neighbors. When a counter drops to zero, the corresponding cell is disconnected. So it suffices to check that all counters have dropped to zero.

As soon as the check of a combination "passes", an optimal solution is found for this component.

To summarize:

Shrink the blocks to cells
Enumerate all connected components (by seed-filling)
    For a given component, let of size K
        By increasing number of cells, let M
            Enumerate all combinations of M cells among K
                For a given combination
                    Initialize the connection counters
                    For all cells appearing in the combination
                        Decrease the connection counter of the neighboring cells
                    If all counts have dropped to zero
                        Done for this component

In the given example, the shrinking of the blocks leads to a single connected component.

If we try to remove a single cell, we never get a disconnected set.

But if we try in pairs, at the fifth attempt we get one. This is an optimal solution.

---

For the $7\times7$ pattern given in my other answer, the shrunk pattern is a $6\times6$ $\#$ shape with $20$ cells, forming a single component.

It takes at most $20+\frac{20\cdot19}2+\frac{20\cdot19\cdot18}{3!}+\cdots+\binom{20}{12}=910595$ attempts before a solution is found ($8$ remaining cells), over a possible total of $2^{20}=1048576$ combinations.

For the $8\times8$ pattern of @ValentinLorentz, there are four T-shaped components, each independently solved in at most $10$ attempts, for a total of $40$ (!).

---

Final comment: the method works for rectangular blocks of any size, just by adapting the shrinking operation.

Answer 4

Try with this one:

 1 0 0 1 1 0 0 1
 0 0 0 0 1 0 0 0
 0 0 0 0 1 0 0 0
 1 1 1 1 1 0 0 1
 1 0 0 1 1 1 1 1
 0 0 0 1 0 0 0 0
 0 0 0 1 0 0 0 0
 1 0 0 1 1 0 0 1

Example for the top left corner (the other cases are obtained through rotation):

Your algorithm (when running from the top left corner) will find this:

  +---+
 1|0 0|1
 0|0_0|0
 0 0 0 0

Whereas the optimal would be two blocks.

And when the algorithm runs from another corner, it will fail on an other pattern in the matrix

Answer 5

The order in which you go through the cells is not well defined. For instance, with this matrix, which one of the two squares would you find first when coming from the top left corner?

1 0 0
0 0 0
0 0 1

And I think I have a counterexample, depending on how you break ties:

1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1

With an interpretation of your algorithm, it the first square that would be found from any of the corners would be the middle one, whereas an optimal solution is 2.