Find the maximal minimum distance in a $n\times n$ square grid? It is dual to my last question. Find the minimal maximal distance in a n times n square grid?
Write $1,2,\dots,n^2$ into a $n\times n$ square grid. Define $d=\min\{|u-v| : u,v \text{ are adjacent}\}$ as the minimum distance of this grid. What is the maximal minimum distance?
And more generally, what about the case $a\times b$, instead of $n^2$?
 A: This is not a complete solution, but shows that the maximal minimum distance (maxmind) is bounded by
$$ \frac{n^2}2-\frac{n}2 \le \text{maxmind} \le \frac{n^2}2-\frac12.$$
The upper bound follows from the fact that each base square has at least 2 adjacent squares. So in case $n$ is odd, the number $\frac{n^2+1}2$ is on a base square that has at least $2$ adjacent elements, but the lowest possible adjacent number is $1$, giving a difference of at most $\frac{n^2-1}2$ to lower values. Similiarly the highest possible adjacent number is $n^2$, giving again at most a difference of $\frac{n^2-1}2$  to higher values. So any difference of $\frac{n^2+1}2$ to any adjacent number is at most $\frac{n^2-1}2$, this means $\text{maxmind} \le \frac{n^2-1}2$ for odd $n$.
For even $n$ the same argument works for the number $\frac{n^2}2$. Its difference to $1$ is $\frac{n^2}2-1$, to $n^2$ it is $\frac{n^2}2$ and to $n-1$ it is $\frac{n^2}2-1$. Since the base square it is on has 2 adjacent squares, at most one can be $n^2$, so the difference of $\frac{n^2}2$ to at least one adjacent number is at most $\frac{n^2}2-1 < \frac{n^2-1}2$. This concludes the proof for the upper bound.
For the lower bound, consider the following construction:
Put a chess board pattern on the grid, then put $1,2,3,\ldots$ on the black squares, in a way indicated by the picture below: Start in the top left, the continue a diagonal "bottom left to top right" direction for the following numbers, until you reach the last black base square with number $d$, then continue the same way with $d+1,d+2,\ldots,n^2$ on the white squares.

The above picture is showing the top left part of a possibly much bigger board, that's why the $5$ is missing, it is on the black square below the $d+3$.
On even $n$ there are an equal number of black and white squares on the board, so $d=\frac{n^2}2$ in this case. For odd $n$, the color that the 4 corners of the board have is on one more base square, so $d=\frac{n^2+1}2$ for odd $n$.
As usual for a chess board pattern, white squares are adjacent to black squares and vice versa. The order has been chosen such that "early" numbered black squares are adjacent to "early" numbered white squares, so the difference between them is "roughly" d. But as can be seen, the first black diagonal containes 1 square, but the first white diagonal  contains 2 squares etc. That continues until we encounter the long diagonal that connects the bottom left corner of the grid with the top right corner (the "minor diagonal"), then the process reverses.
Now I'm starting to hadwave a bit, because this is just looking at examples for odd and even $n$. It turns out that the minimal distance between adjacent base squares is reached between the minor diagonal (black) and the preceeding diagonal (white) for odd $n$, and the difference becomes $d-\frac{n+1}2=\frac{n^2-n}2$.
For even $n$ the minimal distance between adjacent base squares is reached between the diagonal preceeding the minor diagonal (black) and the one preceeding that (white) and the differenc is $d-\frac{n}2=\frac{n^2-n}2$.
I suggest you to make the construction on paper for $n=2,3,\ldots,7$ and this should become clear. This proves the lower bound.
As for the exact number, my gut feeling says it is exactly or near the lower bound, but again, that may be wrong.
