# Correctness of the greedy algorithm

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!

• What do you mean by "I traverse from all the corners of the matrix" ? – Yves Daoust Dec 3 '15 at 20:47
• @YvesDaoust, Of course, random testing won't necessarily be definitive -- failure to find a counterexample doesn't prove the method is correct. I do appreciate that. But that doesn't mean trying random testing is a bad idea. It might just find a counterexample, and if it does, it was worth the time spent. (continued) – D.W. Dec 3 '15 at 23:20
• The question asks for what the OP can do, and I'm suggesting something simple and straightforward the OP can try which might help. In my experience random testing is often effective at finding counterexamples to a proposed greedy algorithm -- certainly not always, but often enough that it's worth the time to implement and try. – D.W. Dec 3 '15 at 23:21
• My advice would be to pick very small matrices (e.g., at most 4x4 or 6x6 or somesuch). Heuristically, if the algorithm is incorrect, often a small counterexample can be found: no guarantees, of course. – D.W. Dec 4 '15 at 5:03
• We prefer ideas and pseudocode instead of source code. Not everyone here necessarily is conversant in C, nor do we particularly want to read code. We want you to describe your algorithm precisely. For instance Yves asked what you mean by "I traverse from all the corners of the matrix", but you never answered. Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. Thank you! – D.W. Dec 4 '15 at 17:24

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.

• This is the most compact configuration I could find. It occurs by chance with probability 2^-46. – Yves Daoust Dec 5 '15 at 0:46

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.

• Your suspicion can be enforced by the following argument: assume that the array is filled with K separate 3x2 rectangles of zeroes; each can accommodate a 2x2 block in two ways. Hence, the number of equivalent solutions is 2^K and enumerating all solutions can be exponential. – Yves Daoust Dec 5 '15 at 9:12
• You can improve your answer by giving full citations (Author, year, title) for the references. Links break. – Raphael Dec 5 '15 at 9:16

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.

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

• I didn't see you answer while posting mine. We are essentially using the same pattern. – Yves Daoust Dec 4 '15 at 23:33

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.

• Sorry for the problem not being clear. I am traversing an entire row (horizontally) first, before moving up or down in the matrix. In the example you provided, the algorithm gives an answer of 2, which we would encounter while moving from top-left. The top left corners of the encountered blocks would be (0,1) and (2,1). – Abhigyan Mehra Dec 4 '15 at 4:26
• @AbhigyanMehra: this is still insufficient. What is meant by "moving up or down" ? In what column ? – Yves Daoust Dec 4 '15 at 7:52
• @YvesDaoust Updated the post with clarifications. Thanks! – Abhigyan Mehra Dec 4 '15 at 20:30