Matrices Generated Using Rectangles

Question

Input is an r by c matrix of non-negative integers (you may input r and c as other parameters if this helps with golf). This may be inputted as a 2D array or, if you prefer, a 1D array (though taking in r this time is necessary). Strings separated by spaces to distinguish rows and newlines to distinguish columns are also fine (below, the test cases have multiple spaces to distinguish rows for clarity -- you do not have to do this).

Consider a matrix of zeros. A move consists of replacing a rectangle of numbers with a rectangle of some positive integer (not zero). For example, these are all valid first moves:

0 0 0 0
0 2 0 0
0 0 0 0
0 0 0 0

0 3 0 0
0 3 0 0
0 3 0 0
0 3 0 0

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

These are not valid first moves:

0 0 0 0
0 2 0 0
0 0 0 0
0 2 0 0

0 1 0 0
0 2 0 0
0 0 0 0
0 0 0 0

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Make golfed code to answer the following the question:

Given an r by c matrix, what is the smallest possible number of turns taken to construct this?

Test Cases:

1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4
1 2 3 4
> 4

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
> 15

3 3 3 3 3 3
3 2 2 2 2 3
3 2 1 1 2 3
3 2 1 1 2 3
3 2 2 2 2 3
3 3 3 3 3 3
> 3

1 1 1 1 1 1
1 2 2 2 2 1
1 2 0 0 2 1
1 2 0 0 2 1
1 2 2 2 2 1
1 1 1 1 1 1
> 8

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
> 0

1 1 1 1
1 3 3 1
2 3 3 2
2 2 2 4
> 4

Answer 1

Python 2, 333 bytes

lambda g,l=len:min(i for i in r(l(g)*l(g[0])+1)if g in o(l(g[0]),l(g),[[0]*l(g[0])for _ in" "*l(g)],set(sum(g,[])),i))
o=lambda w,h,g,s,I:I and sum([o(w,h,n,s,I-1)for n in[[[x<=j<=X<[]>Y>=i>=y and S or E for j,E in e(R)]for i,R in e(g)]for x in r(w)for X in r(x,w)for y in r(h)for Y in r(y,h)for S in s]],[])or[g]
r=range
e=enumerate

Try it online!

This only works in theory, because in practice, it takes way too long if you have more than about 5 elements in the grid.

Since this is code-golf, I apologize for the inefficiency, but efficiency would require more thought and FAR more bytes.

This code does the same thing at the cost of 5 bytes, but short-circuits, meaning that a larger grid with a small answer may finish somewhat earlier... the difference in viable search space is negligible, but just in case you wanted to test it a bit more.

The reason this is so slow is because it looks from \$0\$ up to \$W\times H\$, generating every possible \$W\times H\$ grid that can be achieved with the elements of the grid with that many steps being used.