Minimizing chunks in a matrix

Question

Suppose I have the following matrix:

The matrix can be broken down into chunks such that each chunk must, for all rows, have the same number of columns where the value is marked true for that row.

For example, the following chunk is valid:

This means that rows do not have to be contiguous.

Columns do not have to be contiguous either, as the following is a valid chunk:

However, the following is invalid:

That said, what is an algorithm that can be used to select chunks such that the minimal number of chunks will be used when finding all the chunks?

Given the example, above, the proper solution is (items with the same color represent a valid chunk):

In the above example, three is the minimal number of chunks that this can be broken down into.

Note that the following is also a valid solution:

There's not a preference to the solutions, really, just to get the least number of chunks.

I thought of counting using adjacent cells, but that doesn't account for the fact that the column values don't have to be contiguous.

I believe the key lies in finding the chunks with the largest area given the constraints, removing those items, and then repeating.

Taking that approach, the solution is:

But how to traverse the matrix and find the largest area is eluding me.

Also note, that if you want to reshuffle the rows and/or columns during the operations, that's a valid operation (in order to find the largest area), but I'd imagine you can only do it after you remove the largest areas from the matrix (after one area is found and moving onto the next).

Answer 1

You are doing circuit minimization on a truth table. For 4x4 truth tables, you can use a K map. The Quine-McCluskey algorithm is a generalization that can handle larger truth tables.

Keep in mind the problem is NP-Hard, so depending on the size of your truth tables, this problem can quickly grow to a size that is intractable.