h3. Soluţie
Întâi, să considerăm un exemplu. Pentru o cerinţă de forma:

<tex> 3 \ 2 \ 3 </tex>
<tex> 2 \ 3 \ 3 </tex>
<tex> 1 \ 2 \ 1 </tex>

 
table{width: 90px; text-align: center}.
| <tex> 3 </tex> | <tex> 2 </tex> | <tex> 3 </tex> |
| <tex> 2 </tex> | <tex> 3 </tex> | <tex> 3 </tex> |
| <tex> 1 </tex> | <tex> 2 </tex> | <tex> 1 </tex> |

una din soluţii este:

<tex> 1 \ 1 \ 0 \ 1 </tex>
<tex> 1 \ 0 \ 1 \ 1 </tex>
<tex> 0 \ 1 \ 1 \ 0 </tex>
<tex> 0 \ 0 \ 0 \ 0 </tex>

 
table{width: 90px; text-align: center}.
| <tex> 1 </tex> | <tex> 1 </tex> | <tex> 0 </tex> | <tex> 1 </tex> |
| <tex> 1 </tex> | <tex> 0 </tex> | <tex> 1 </tex> | <tex> 1 </tex> |
| <tex> 0 </tex> | <tex> 1 </tex> | <tex> 1 </tex> | <tex> 0 </tex> |
| <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> | <tex> 0 </tex> |

Fie <tex> A </tex> o matrice soluţie a problemei noastre. Vom numerota rândurile matricii de la $0$ la $N - 1$ şi coloanele de la $0$ la $M - 1$. Matricea de intrare <tex> S </tex> reprezintă de fapt sumele din fiecare pătrat de câte $2 x 2$ elemente. Facem observaţia că dacă ştim într-un pătrat de $2 x 2$ valorile pentru trei dintre celule, atunci valoarea din a patra celulă este unic determinată pentru că ştim suma elementelor din pătrat. Vedem astfel, că dacă ştim valorile elementelor din prima linie a matricii <tex> A </tex> şi din prima coloană, restul valorilor sunt unic determinate.
Pentru a rezolva problema vom presupune <tex> A[0][0] </tex> cunoscut (de fapt, mai întâi vom rezolva problema presupunând că <tex> A[0][0] = 1 </tex>, iar dacă nu obţinem nicio soluţie vom încerca cu <tex> A[0][0] = 0 </tex>). Vom nota celulele <tex> A[0][1] </tex>, <tex> A[0][2]</tex>, … <tex> A[0][M - 1] </tex> cu <tex> x_{1} </tex>, <tex> x_{2} </tex>, … <tex> x_{M-1} </tex> iar celulele <tex> A[1][0] </tex>, <tex> A[2][0] </tex>, … <tex> A[N - 1][0] </tex> cu <tex> y_{1} </tex>, <tex> y_{2} </tex>, … <tex> y_{N-1} </tex>.

table{width: 90px; text-align: center}. | <tex> A[0][0] </tex> | <tex> x_{1} </tex> | <tex> x_{2} </tex> | <tex> ... </tex> | <tex> x_{M-1} </tex>|

table{width: 90px; text-align: center}.
| <tex> A[0][0] </tex> | <tex> x_{1} </tex> | <tex> x_{2} </tex> | <tex> ... </tex> | <tex> x_{M-1} </tex> |

| <tex> y_{1} </tex> | <tex> 1 </tex> | <tex> 1 </tex> | ... | <tex> 1 </tex> |
| <tex> y_{2} </tex> | <tex> 0 </tex> | <tex> 1 </tex> | ... | <tex> 0 </tex> |
| ... | ... | ... | ... | ... |
| <tex> y_{N-1} </tex> | <tex> 0 </tex> | <tex> 1 </tex> | ... | <tex> 1 </tex> |

Acum, pentru fiecare celulă putem demonstra prin inducţie că <tex> A[i][j] = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>. Unde <tex> b[i][j] </tex> sunt nişte constante ce sunt calculate în funcţie de matricea primită la intrare.
Este uşor de observat că dacă:
<tex> A[i-1][j] = (-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j] </tex>,
<tex> A[i-1][j-1] = (-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1] </tex>,
<tex> A[i][j-1] = (-1)^i x_{j-1} + (-1)^{(j-1)} y_{i} + b[i][j-1] </tex>,
atunci
<tex> A[i][j] = S[i-1][j-1] – A[i-1][j] – A[i][j-1] – A[i-1][j-1] = S[i-1][j-1] – ((-1)^{(i-1)} x_{j} + (-1)^j y_{i-1} + b[i-1][j]) – ((-1)^{(i-1)} x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i-1][j-1]) – ((-1)^i x_{j-1} + (-1)^{(j-1)} y_{i-1} + b[i][j-1]) = (-1)^i x_{j} - (-1)^j y_{i-1} + (-1)^i x_{j-1} + (-1)^j y_{i-1} - (-1)^i x_{j-1} + (-1)^j y_{i} + S[i-1][j-1] – b[i-1][j] – b[i][j-1] – b[i-1][j-1] = (-1)^i x_{j} + (-1)^j y_{i} + b[i][j] </tex>.
De aici concluzionăm că <tex> b[i][j] = S[i-1][j-1] – b[i-1][j] – b[i][j-1] – b[i-1][j-1] (*)</tex>.