We'll prove first that $n$ cannot be odd. First, we see that a certain point we may choose to make a move with two squares that contain two odd numbers, two even numbers, or one odd and one even number. It isn't hard to see that in the three cases, regardless of addition/subtraction of an even or odd number to both squares, the sum of all numbers in the grid conserves its parity. Hence, if $n$ is odd, the sum of all numbers at the beginning is odd. Since we cannot change the parity of this sum by doing any number of moves, we cannot get the desired arrangement, in which the sum is $0$. Now we'll show it is possible to get to the desired grid of zeros by doing at least $\frac{3n^2}{4}$ moves whenever $n$ is even. We'll prove first this is indeed the minimum amount of move. First, none of the squares contain numbers that are zeros at the begining, then each square must be involved in at least one move, so we need at least $\frac{n^2}{2}$ moves. Next, we realize it is not possible to turn both numbers into zeros if they haven't been involved in a move before. Hence, with $\frac{n^2}{2}$ moves we can only get, at most, half of the numbers to turn to $0$. Hence, by the initial argument, the rest of the numbers must be involved in a movement, so we need $\frac{n^2}{4}$ more movements, i.e. $\frac{3n^2}{4}$ total at least. Finally, this is possible by using the following algorithm: Divide the grid in $\frac{n^2}{4}$ smaller independent square grids of $2 \times 2$. Each grid will contain the numbers $i$, top left corner; $i + 1$, top right corner; $i + n$, bottom left corner; $i + n + 1$, bottom right corner. Now, to each grid we do the following. The first move, we select the two squares on the left column and we subtract $i$ to both, so we have $0$ on the top square, and $n$ on the bottom square. Next, we choose the two squares on the right column and we subtract $i + 1$ to both, so we get $0$ on the top square and $n$ on the bottom square. Finally, we choose the two squares on the bottom row and subtract $n$ from both and we're done. This takes $3$ moves per small square grid, since there are $\frac{n^2}{4}$ of these, we'll make a total of $\frac{3n^2}{4}$ moves, q.e.d. As a side note. Would it be possible to argue that this the minimum number of moves for a $2 \times 2$ grid is $3$ (not hard to prove), and then saying that there are $\frac{n^2}{4}$ of those grids on the $n \times n$ grid, hence the minimum? Or this is not enough? I always get confused with this kind of problems.

Quote: As a side note. Would it be possible to argue that this the minimum number of moves for a $2 \times 2$ grid is $3$ (not hard to prove), and then saying that there are $\frac{n^2}{4}$ of those grids on the $n \times n$ grid, hence the minimum? Or this is not enough? I always get confused with this kind of problems. not neccessary,for example there might be a move involving $2$ numbers belonging to $2$ different $2\times2$ squares that might reduce each of those squares into needing only $2$more moves to get all $4$ $0$s hence, resulting in needing $5$ moves for $2$ of the $2\times2$ squares.Of course this is obviously false, but we cannot say the same to bigger $m\times n$ rectangles

Assume we have a sequence of moves which takes all squares to zero. Notice that each square must be involved in at least one move, since all of the initial numbers are non-zero. Call a square faithful if it was involved in exactly one move, and unfaithful otherwise. Additionally, call a move faithful if it involves a faithful square, and unfaithful otherwise. Notice that two faithful squares cannot be brought to zero using the same move, as all the initial numbers are different. Hence, each faithful move involves one faithful square, and one unfaithful square. Let $k$ be the number of faithful moves performed. By the previous observation, this is equal to the number of faithful squares. Let $n(S)$ be the number of moves that affect a square $S$. Then the number of moves $m$ satisfies: $$m = \frac{1}{2}\sum_{S} n(S) \geq \frac{k + 2(n^2 - k)}{2} = n^2 - \frac{k}{2}$$ As all $n^2 - k$ unfaithful squares were involved in at least two moves. Now, for each square $S$, let $f(S)$ be the number of faithful moves it was involved in, then $f(S) = 1$ if whenever $S$ is faithful. Now, consider an unfaithful square that initially contains the number $r$, we will prove that it was involved in at least one unfaithful move. Assume otherwise, then there must be a subset of its neighbors whose initial numbers add up to $r$. As the possible neighbors of $r$ are $r - 1, r + 1, r - n$ and $r + n$, this is only possible if $(r - 1) + (r - n) = r$, which implies $r = n + 1$. However, in this case, $r - 1$ is not a neighbor of $r$. Thus, the number $m$ of moves performed satisfies: $$m = \frac{1}{2}\sum_{S}n(S) \geq \frac{1}{2}\left(k + \sum_{S \text{ unfaithful}} (f(S) + 1)\right) = \frac{1}{2}\left(n^2 + \sum_{S \text{ unfaithful}} f(S)\right) = \frac{1}{2}(n^2 + k)$$ Where the last equality follows from the fact that each faithful move involves exactly one unfaithful squares. Thus $m \geq \max\left(n^2 - \frac{k}{2}, \frac{n^2 + k}{2}\right)$. Hence $m$ must be greater than or equal to the average of these two numbers, which is exactly $\frac{3n^2}{4}$

Consider a graph $G$ with vertices corresponding to each square, such that two vertices are adjacent if and only if a move was made which involves them both. Consider a connected component in this graph, it must have at least two vertices as every number is initially nonzero. Additionally, it may not have exactly two vertices, since all the squares initially have different numbers in them. Assume that is has exactly three vertices, then clearly one of them has degree two, while the other two have degree one. Thus, the number which corresponds to the vertex with degree two must be equal to the sum of two of its neighbors, which is easily shown to be impossible. Thus each connected component in $G$ has at least $4$ vertices, and thus $G$ has at most $\frac{n^2}{4}$ connected components. Let $C_1, C_2, \dots, C_m$ be $G$'s connected components and let $v_i, e_i$ be the number of vertices and edges in $C_i$, respectively. Then $e_i \geq v_i - 1$ for each $i$ and thus the total number of edges $e$ of $G$ satisfies: $$e \geq (v_1 - 1) + (v_2 - 1) + \dots + (v_m - 1) = v_1 + v_2 + \dots + v_m - m = n^2 - m \geq \frac{3n^2}{4}$$ And we are done, as the number of edges in $G$ is equal to the number of moves performed.