[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]
# [Python 2](https://docs.python.org/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!](https://tio.run/##NU@xbsMgFNz5iqd2gZZGdbpFIVtUZU06JKKoIjImpDZYQOT4613A6YLe3bs73vVjvDi7nBr2PbWyO9cSNG1Zq@yqMxYbaJwHA8aCxy3W5CU9/F2Q14qYBnReOPzgaBZQnsZ/VTb/JM0TPGWKCBpUxOHWYU25IIQaQpBjj48HeqGaBrpb7UDaGrKOO5xpm@m3qgTaFMg5v6/Zdc2Oay42pw0zGzYW0wGSZFvOvtJtvk/hPRGlBt3PWM/4PtcaSupxBnc6w3GGlwJOMxjpDA8ZBiFyBee5FsgzL61WSDFlb53yMqrpGb7kr4J4UUne3yJCpuudjxDGgJCXA7A8LkKsjV14JWtMEEqum08NYzJFBxJS3ll50N7UCOU32XhrQsSd7HESUfBuWIS@NRETQkrzxJST5WPRGqsCJiLnf6pYjpI2DMoj1PsUAg3O2WSqYIk@oPoD "Python 2 – 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](/questions/tagged/code-golf "show questions tagged 'code-golf'"), I apologize for the inefficiency, but efficiency would require more thought and FAR more bytes.
[This](https://tio.run/##dVHBbgIhFDyXr3ixF2ipsT0a8WYar9qDhpAGs29X7C5sALPu11tg7bHZhGXemxneQD/Gs7Mf93uFNdS04a1o0bIlgdp5MGAseNrShr2kRS4Ue31PzSdTQ5N7jj7KPHO4TNs/YtZ/J84MZrnEFA8Yabh26RCpGOOGLT3Gq7dgiBOt7k6VhoGfecMD3y63oG0FmS8dzWWby2/vxThprJTythJmJQ4rqdbHtbisxVhEe0iUTUlw4Zs8J9IdUyUR3024mfBtSjgU18MEbnyC4wTPBRwnMPIJ7jMMSuUozstGES@8tg0SFGivHXod8f4MX/oHIZ4x0ftrJMR0vfMRwhgI8XoAkbfzECtj5x51RRkhSVVuJSZRdKAh@Z3QQ@NNRUhek0y2JkTa6Z4mEgfvhnnoWxMpY6wkT5Uysn40WmMxUKay/yfGMpS2YUBPSO@TSX7@5M3uCygf@ef/Cw) 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.
[Answer]
# Python3, 1288 bytes
Long, but crunches the test cases in under a second.
```
R=range
E=enumerate
M=[(1,0),(-1,0),(0,-1),(0,1)]
def D(b):
 for x,j in E(b):
  for y,_ in E(j):
   for X in R(x,len(b)):
    for Y in R(y,len(b[0])):yield[(u,i)for u in R(x,X+1)for i in R(y,Y+1)]
def r(b):
 S={(x,y)for x,j in E(b)for y,_ in E(j)if _ not in['0']}
 W={*S}
 while S:
  x,y=[(x,y)for x,y in S if b[x][y]!='-'][0];S=S-{(x,y)};d,s={x:[y]},[(x,y)]
  V=b[x][y]
  q=[(x,y)]
  while q:
   x,y=q.pop(0)
   F=1
   for X,Y in M:
    J,K=x+X,y+Y
    if(J,K)in S and(b[J][K]==V or'-'==b[J][K]):F=0;q+=[(J,K)];S=S-{(J,K)};d={**d,J:sorted(d.get(J,[])+[K])};s=s+[(J,K)]
   if all(b==d[min(d)]for b in d.values()):yield s
def Z(B,s,i):
 B=eval(str(B))
 for x,y in s:B[x][y]=i
 return B
V=lambda W,c,S,U:(W==-1 or c+1<W)and all(C>c for C,u in S if u==U)
def f(b):
 q,S=[(b,0)],[(0,b)]
 L=[i for i in D(b) if i]
 W=-1
 while q:
  B,c=q.pop()
  if all(not({*i}-{'-','0'})for i in B):W=c if W==-1 else min(W,c);continue
  H=[*r(B)]
  for i in H:
   U=Z(B,i,'-')
   if V(W,c,S,U):
    q+=[(U,c+1)];S+=[(c,U)]
    if len({sum(B[x][y]!='-'for x,y in j)for j in H})==1:break
  U=Z(B,max([i for i in L if len(T:={B[x][y]for x,y in i})<3 and{'-'}!=T and'0'not in T and(len(T)==1 or'-'in T)],key=lambda X:sum(B[x][y]not in{'-','0'}for x,y in X)),'-')
  if V(W,c,S,U):q+=[(U,c+1)];S+=[(c,U)]
 return W
```
[Try it online!](https://tio.run/##dVRLc9pIED6vfkXHe2DGDC4JsJ0VmT2QR7mcxyHExl6tyiWkIRlHSKARu1AUv93peQhITEqH7unur7vn6x7N1/W3sui9nFdPT595lRRfhfeWi2I5E1VSC@8jj0jAfMpIxwqfdQIjAhp7mZjCGzKhoQfTsoIVewRZwFtrMaY1e7CmR2Mytjtt@UxWLBcFhlqH8dxbz9p6Ij9G51qKPIvIkkmqQ5YN@K4dGINsMPftpqXKNjDiG4xb019a@6UtOYUHKMoaz1HLb8VbD8Z8czpC@f83mQsY6f4wDzKxz7bW8BEgeBKt4mgdv@CtTivGlgcjPurYwttBxhTfrEL0b5mFx5jsljsQ6gu@t9t6C8OHLrg4m5dz4lN9fseDHX/M8PTR8nbN3vNV@46t2/fmLKcETdS0lxQZ0ngdR@9jzm@hrLBHzp2Fhu@4P1i0sQENaBrXOjaOFJxm7DpUZVWLjGRnX0WNviimbY3dDhRXbYf0TFlI8pxMOM@imSxIRmPd60R3mp39l@RLoUgzTlBmTv@QIVM4V7zIkAuMIaquyJDSZp0MyyocWra49KAS9bIqYOjd8jyZTbIExixlI3YTkjHnnQDvCGk7eDWmeHfT0eu/U5PtNVvuZrbk/IaaFqZ2VRZshDRMcMNjnJPPJvpSH3gkYbdies81VsZ6QTqBdziuIUvdtPSwHBe4VGRzKredDdLOcLe2@4Ud0nDMUx1p2xa5EqB5w@vQQVoWtSyWAnNd8ehUcxK7B2XQV2b0N1wTKBlmp24Et8TR4R6Vme4NS/XTGIz0IUVf7BYF9DPbqOWMDA@W@ID6R9OweTlXW8p5EE4qkXz3mtqzZEUOOfrQJP0S8o3LeZBObumrnl5KTcj2Bf@ideTFvj4wR2LgupZdV23HoXwX62bgd@FBxxa6I/ig2B2lDTM/E/NbTtxujZ9UABxOTk68AMyHsqs/I3vQc7K/kzpWdQ9ANthKBKDWs0G9XRD60AF9gHPvAuAS4CXAXwCB7wUI7UKAsD4E5xbYd0CdzX2od91ndVvxub6P2WNN0vOf73l4V53C6D5@x/R9zB5rkl64pL4J938rTfDlM6YNXZ7hGcmzVSzD@r3W5cOkTKqMKNzwP9zEInmm5rmsyf59TWVei4p8KgvBQDl369@iRXHSnjevZFGTKdmnCyj@dp6bu2iGP9VcpDLJoRaqhjRR4khk73iC/nHz@XHzxXHzJZqffgA)
]