First of all, we solve a related problem that has appeared in IMO shortlist in 1988. Lemma 1. Consider a $n\times n$ table filled with numbers $1$ through $n^2$. Then there are two adjacent squares whose numbers differ by at least $n$. Solution. Let $k$ be the smallest integer such that the set of assigned numbers for some row or column is a subset of $\{1,2,\ldots ,k\}$. One way to interpret $k$ is to write \[k= \min \left( \min_{\text{cols}} \max_{\text{rows}} a_{ij}, \min_{\text{rows}} \max_{\text{cols}} a_{ij}\right),\]where $a_{ij}$ are entries of our table. We may assume that number $k$ is written in row $r$ and column $c$ and that other numbers in row $r$ are all from $\{1,2,\ldots ,k-1\}$. By the minimality of $k$, every column except possibly column $c$, contains a square with assigned number at least $k+1$. Thus in every column, except possibly column $c$, one square is at most $k-1$ and others are at least $k+1$. Therefore, by "continuity'' argument, in each column, except possibly column $c$, there is a pair of adjacent squares $(a_i, b_i)$ such that $a_{i} \leq k-1$ and $b_{i} \geq k+1$. If some square of column $c$ is at least $k+1$, then column $c$ contains a pair of adjacent squares $(a,b)$ such that $a \leq k$ and $b \geq k+1$. Otherwise, all numbers in $c$ are less than or equal to $k$, so there will be a pair of adjacent squares $(a,b)$ such that $a \leq k-1$ and $b = k$. In any of the above cases, we find that that there are $n$ pairs of adjacent squares $(a_i, b_i)$ placed in different columns and there exist numbers $A< B$ such that \[\max \{a_1,a_2,\ldots,a_n\}\leq A \text{ and } B\leq \min \{b_1,b_2,\ldots,b_n\}.\]In the first case $A=k$, $B=k+1$ and in the second case $A= k-1$, $B=k$. Then \[\sum_{i=1}^{n} b_i \geq B+(B+1)+\cdots+(B+n-1)=\left(B+\frac{n-1}{2}\right)n,\]and \[\sum_{i=1}^{n} a_i \leq A+(A-1)+\cdots+(A-n+1)=\left(A-\frac{n-1}{2}\right)n.\]Thus $\sum_{i=1}^{n}(b_i-a_i)\geq n^2$, and we have $b_j-a_j\geq n$ for some $j$. Returning back to the problem, consider pairs of adjacent squares $(a_i, b_i)$ and numbers $A$ and $B$ defined in Lemma 1. From the condition of the problem, we obtain that $b_i - a_i = n$ for all $i \in [1,n]$. It follows that these pairs are exactly \[\left(k-(n-1), k+1\right), \ldots, \left(k-1, k+(n-1)\right)\]and the last of of them is either $(n-k, k)$ or $(k, n+k)$. There are no more pairs of numbers $(u,v)$ such that $u \leq A$ and $v \geq B$ and $v-u = n$. Hence in each of the columns there is exactly one pair of adjacent squares $(u,v)$ such that $u \leq A$ and $v \geq B$ and $v-u=n$. Let us call such pairs of adjacent squares $\textit{special}$. Consider a special pair $(a^*, b^*)$ in the column adjacent to the column $c$. Note that $b^* \geq k+1$ and it does not lie in the row $c$. Denote by $x$ and $y$ the numbers in column $c$ that are adjacent to $a^*$ and $b^*$, respectively. Clearly, $x$ and $y$ are not in the set $\{k-(n-1), \ldots, k-1\}$, because these numbers belong to special pairs and lie in all columns but $c$. Similarly, $x$ and $y$ are not in the set $\{k+1, \ldots, k+ (n-1)\}$. Since $y \geq b^*-n \geq k-(n-1)$, it follows that $y \geq n+k$. If $y > n+k$, then $x>k$ and therefore $x > n+k$. This contradicts the fact that $a^* < k$ and $x > n+k$ are adjacent squares. It follows that $y=n+k$, $x=k$, and $b^*-a^*=y-x =n$. Therefore $(a^*, b^*, x, y)$ form a $2\times 2$ square of adjacent cells such that the diagonally opposite pairs sum to the same number.

There are 2 mistakes: $\sum a_i \ge ...$ AND $a_i-b_i =n \forall i=1,2,3\ldots, n$ I think

Sorry, just the first, the second is right.

Solved with tapir1729, brian6liu, JNEW. The result is clear for $n=2$, so suppose $n\ge 3$. Call a penguin a collection of $n$ cells such that each one is in a different column, or each one is in a different row. Now, consider adding the numbers $1$ through $n^2$ sequentially to the grid in increasing order, and stop when the first penguin forms (WLOG the penguin consists of one square in each column). Note that, at this stage, every column still has at least one empty square, or else a penguin must've formed earlier. So, as every column has a filled square and an empty square, there exists an empty square in each column which borders a filled square. Denoting the last number entered as $m$, note that every unfilled square must have a number $>m$. So, if there exist more than $n$ unfilled squares which border filled squares, then we will have a pair of adjacent cells where one value is $>m+n$ and the other $\le m$, which is a contradiction. So, there exist exactly $n$ unfilled squares bordering filled squares - one per column. This tells us that each column consists of a "filled section" followed by an "unfilled section." Furthermore, if an edge of a filled section is filled with a value $\le m-n$, then difference condition will be violated. So, the edges of the filled sections are filled with a permutation of $[m-n+1,m]$. With this, note that the only way to fill the edges of the unfilled sections without violating the condition is to fill the cell vertically adjacent to $c\in [m-n+1,m]$ with $c+n$. Now, consider the column $C_i$ (numbering left to right, WLOG $i<n$) which contains $m$ at position $(i,1)$ and an adjacent column $C_{i+1}$. If the cell $(i+1,1)$ is unfilled, then the filled section of $C_{i+1}$ consists of $n-1$ squares, since $(i+1,1)$ borders a filled cell and hence must be the edge of the unfilled section in $C_{i+1}$ by uniqueness. However, this means $C_i$ has $n-1>1$ unfilled cells which border filled cells in $C_{i+1}$, which is a contradiction. So, $(i+1,1)$ is filled. If $(i+1,2)$ is filled as well, then it must have value $c<m$. However, $(i,2)$ will eventually be occupied by $m+n\implies m+n-c>n$, which violates the difference condition. So, $(i+1,2)$ is unfilled as well. As they are both edges of their respective unfilled sections, $(i,2)$, $(i+1,2)$ will eventually be filled with numbers $n$ larger than $(i,1)$, $(i+1,2)$ respectively, and hence the $2\times 2$ formed by $[i,i+1]\times [1,2]$ satisfies the problem condition, as desired.

Click here if you want a spoiler to another problem

Put the numbers in increasing order. Numbered and labelled will be used interchangeably in this solution. Call an unlabelled neighbour cell a cell that is not labelled but is adjacent to (share an edge with) a labelled cell Case 1: At some point, all rows are neither full or empty. Consider the first instance it occurs. Let $r_i$ be the number of numbered cells in row $i$. This implies every row has a neighbour unlabelled cell. Since the difference between two cells is at most $n$, we can have at most $n$ neighbour cells, so every row has exactly one neighbouring unlabelled cell. This implies $|r_i-r_{i+1}|\le 1$. Furthermore, in a row, at least one of the two side squares must have been labelled. In the row with one labelled cell, an edge square must be labelled. Furthermore, if the numbered cells in one row is not continuous, exactly one cell is not labelled. If there is one row where that happens, then that row has $n-1$ labelled squares, and rows next to it has $n-1$ labelled squares as well, where the neighbouring square can be in the same horizontal position, or moved one square to the left or right. Since one row has one square, it must be the top row, and the second row is continuous, and the last row has 1 square. In particular, $r_i=n+1-i \forall i\ge 2$. Its shape looks like this (1 denotes a numbered square; 0 denotes an unnumbered square): \begin{tabular}{c|c|c|c|c} 1 & 0 & 1 & 1 & 1 \\\hline 0 & 1 & 1 & 1 & 1 \\\hline 0 & 0 & 1 & 1 & 1 \\\hline 0 & 0 & 0 & 1 & 1 \\\hline 0 & 0 & 0 & 0 & 1 \end{tabular} This is actually impossible because the last labelled number is the number on the row with one element, leading to $n+1$ neighbours. Therefore, all rows are continuous. WLOG, they all start from the left edge. Subcase 1: No row has $n-1$ labelled squares. This is easy; call the number on the rightmost square on row $i$ $x_i$, then it's not hard to see that the two numbers to the right of that square must be $x_i+n, x_i+2n$ respectively. Since two rows satisfy $|r_i-r_{i+1}|\le 1$, we are done. Subcase 2: One row has $n-1$ labelled squares. Note if we "unlabel" the last number put, the number of unlabelled neighbour cells is still at most $n$, and every row still has one unlabelled neighbour. This implies that row(s) adjacent to the row with largest number also have one labelled square. Since $|r_i-r_j|\le i-j$, there exists $r_i=n-1, r_j=1$, it follows that $|i-j|\ge n-2$. There cannot exist three rows with 1 cell, so the last cell is in a corner. The configuration has to look like this: \begin{tabular}{c|c|c|c|c} 1 & 1 & 1 & 1 & 0 \\\hline 1 & 1 & 1 & 0 & 0 \\\hline 1 & 1 & 0 & 0 & 0 \\\hline 1 & 0 & 0 & 0 & 0 \\\hline 1 & 0 & 0 & 0 & 0 \end{tabular} Notice the last two rows both have one cell, so repeating the same argument would suffice. Case 2: When one row is full, another row is still empty. We note all columns are not full and nonempty and repeat the same argument.

We fill up the numbers in increasing order until the first time all the rows are not empty nor full, and/or all the columns are not empty nor full. WLOG suppose it is the latter. Let $k$ be the last number filled, and suppose this is in square $S$ in column $C.$ It must occupy the only filled square in its column. WLOG suppose it is at the bottom. At this point, there are at most $n$ currently unfilled squares adjacent to a filled square. We see that exactly one of these must occur in every column. So each column must consist of a sequence of consecutive filled cells followed by a sequence of consecutive unfilled cells, or vice versa. The ends of the filled cells must be filled with a permutation of $k-n+1, k-n+2, \dots k,$ and must each be vertically adjacent to an unfilled cell that will later be occupied by a number exactly $n$ more, There is a column $D$ adjacent to $C.$ If the square $T$ adjacent to $S$ in $D$ is unfilled, then that is the one square in $D$ adjacent to a filled square, so all squares above $T$ are filled, but now there are $n-1$ unfilled squares in $C$ adjacent to filled squares which is impossible. So $T$ is filled. If the square $T'$ right above $T$ is filled, it is filled with a number $< k,$ so it forces a contradiction with the square $S'$ right above $S$ and adjacent to $T',$ which will soon be occupied by $k+n.$ So $T'$ is currently unfilled and will later be occupied by a number exactly $n$ more than the one in $T.$ and we can see after we fill in all the squares, $T'TSS'$ will work.