title: Minimizing chunks in a matrix
body: <p>Suppose I have the following matrix:</p>
  
  <p><img src="https://i.stack.imgur.com/s6rLb.png" alt="Original matrix"></p>
  
  <p>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.</p>
  
  <p>For example, the following chunk is valid:</p>
  
  <p><img src="https://i.stack.imgur.com/Wa1Df.png" alt="Valid chunk example 1"></p>
  
  <p>This means that rows do not have to be contiguous.</p>
  
  <p>Columns do not have to be contiguous either, as the following is a valid chunk:</p>
  
  <p><img src="https://i.stack.imgur.com/sxcRv.png" alt="Valid chunk example 2"></p>
  
  <p>However, the following is invalid:</p>
  
  <p><img src="https://i.stack.imgur.com/ohaqz.png" alt="Invalid chunk example"></p>
  
  <p>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?</p>
  
  <p>Given the example, above, the proper solution is (items with the same color represent a valid chunk):</p>
  
  <p><img src="https://i.stack.imgur.com/xY56M.png" alt="Solution to chunking problem 1"></p>
  
  <p>In the above example, three is the minimal number of chunks that this can be broken down into.</p>
  
  <p>Note that the following is also a valid solution:</p>
  
  <p><img src="https://i.stack.imgur.com/5c2dr.png" alt="Solution to chunking problem 2"></p>
  
  <p>There's not a preference to the solutions, really, just to get the least number of chunks.</p>
  
  <p>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.</p>
  
  <p>I believe the key lies in finding the chunks with the largest area given the constraints, removing those items, and then repeating.</p>
  
  <p>Taking that approach, the solution is:</p>
  
  <p><img src="https://i.stack.imgur.com/ZegYb.png" alt="Solution to chunking problem 3"></p>
  
  <p>But how to traverse the matrix and find the largest area is eluding me.</p>
  
  <p>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).</p>