Find the minimal maximal distance in a $n\times n$ square grid?

Question

Write $1,2,\dots,n^2$ into a $n\times n$ square grid. If $u,v$ are adjacent, call $\max_{u,v}|u-v|$ the maximal distance of this grid. So what is the minimal maximal distance?

I feel like that it is $n$, the construction is to write $1,2,\dots,n^2$ in order, but I do not know how to prove it, and I cannot find any results on it either.

Answer 1

This is closely related to the so-called vertex isoperimetric problem on the grid graph.

If $A$ is a collection of squares in the grid $\partial A$ denote the set of those squares that are not in $A$ but are adjacent to a square in $A$ (we'll call this the boundary of $A$). The vertex isoperimetric problem in a graph seeks to minimize the size of the boundary $\partial A$ of a collection of vertices while fixing the size of $A$. It is well studied problem and well understood for grid graphs (I believe originally due to Bollobas and Leader), and indeed if $|A| = \lfloor \frac{n^2}{2}\rfloor$ then $|\partial A| \ge n$.

Now suppose we have a way of filling the squares such that $|u-v| < n$ for adjacent entries $u$ and $v$. If we let $A_k$ denote the the collection of squares with labels at lost $k$ then $|A_k| = k$, and since $\partial A_k$ must be filled with entries of size at most $k+n-1$ we have that $|\partial A_k| < n$. But this violates the above when $k = \lfloor \frac{n^2}{2}\rfloor$.

Answer 2

No proof but a confirmation of $n$ being the smallest maximum distance:

The following MiniZinc model does not find smaller distances for small dimensions
(for $n \gt 5$ the solution search takes quite a while).

include "globals.mzn";

int: n = 5;
set of int: N = 1..n;
set of int: N2 = 1..n*n;

array[N, N] of var N2: a;  %  the 2d array
array[N2] of var N: row;   %  rows of array cells
array[N2] of var N: col;   %  columns of array cells
var N2: dist;

%  every 2d cell entry is unique
constraint 
  all_different([a[r,c] | r in N, c in N]);
  
%  assign rows and columns
constraint
  forall(r in N, c in N) (
    (row[a[r,c]] == r) /\
    (col[a[r,c]] == c)
  );
  
predicate adjacent(int: i, int: j) =
  ((row[i] == row[j]) /\ (abs(col[i] - col[j]) == 1)) \/
  ((col[i] == col[j]) /\ (abs(row[i] - row[j]) == 1));
  
constraint
  dist == max([i - j | i in N2, j in N2 where (i > j) /\ adjacent(i, j)]);
  
solve minimize dist;

output 
["min dist = \(dist)\n"] ++
[if c == 1 then "\n" else "" endif ++ show_int(3, a[r,c]) | r in N, c in N];