Minimum cost block diagonalisation Consider binary block diagonal matrices which have square blocks of 1s on the main diagonal, and are 0 everywhere else. Let's call such matrices "valid" matrices.

For example, here are some valid 4x4 matrices:

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


Note that an alternative way of describing such matrices is that there is a chain of square 1 blocks from the top-left to the bottom-right, touching corner to corner, and everywhere else is 0.

For contrast, here are some invalid 4x4 matrices:

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


You will be given an n by n binary matrix as input – what is the minimum number of 0 bits you'll need to set to 1 in order to get a valid matrix?

You may write a function or program taking in any convenient string, list or matrix format representing an n by n matrix of 0s and 1s (as long as it isn't preprocessed). Rows must be clearly separated in some way, so formats like a 1D array of bits are not allowed.

This is code-golf, so the goal is to minimise the number of bytes in your program.

Examples

For example, if the input is

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


then the answer is 5, since you can set five 0 bits to 1 to get:

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


and this is the minimum number required. However, if the input was

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


then the answer is 24, since the only valid 5x5 matrix where the top-right is 1 is the matrix of all 1s.

Test cases

Tests are represented here as a 2D array of integers.

[[0]] -&gt; 1
[[1]] -&gt; 0
[[0,1],[0,0]] -&gt; 3
[[1,0],[0,0]] -&gt; 1
[[0,0,0],[0,1,0],[0,0,0]] -&gt; 2
[[0,1,0],[0,0,0],[0,1,0]] -&gt; 7
[[0,1,0],[1,0,0],[0,0,1]] -&gt; 2
[[1,1,1],[1,1,1],[1,1,1]] -&gt; 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -&gt; 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -&gt; 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -&gt; 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -&gt; 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -&gt; 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -&gt; 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -&gt; 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -&gt; 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -&gt; 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -&gt; 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -&gt; 14


Notes


Related challenge: Print a Block-Diagonal Matrix
Inspiration: Freedom Factory, Google Code Jam 2016 Problem 2D
MATL, 46 43 bytes

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG&gt;zvX&lt;


Input is a 2D array with semicolon as row separator. For example, the input for the last test case is

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]


Try it online! Or verify all test cases (code slightly modified to take all inputs; the results appear after a few seconds)

Explanation

Let the input be an N×N matrix. The code first computes all (N+1)-tuples of block sizes that produce the appropriate matrix size. For example, for N=4 the tuples are 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. For each tuple it builds the block-diagonal matrix with those block sizes. It then checks if the matrix covers all the 1 entries in the input, and if so takes note of the number of 1 entries that were not present in the input. The final result is the minimum of all the obtained numbers.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each 
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G&gt;   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X&lt;   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display