Suppose that the $n^2$ cells of an $n\times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.  Is it possible to relabel the array so that the labels of adjacent cells (horizontally or vertically) differ by less than $n$?

I suspect the answer is "no" but do not have a proof.  I made up this problem while contemplating a similar Putnam Competition problem (1981, A-2).  In this problem, adjacent cells are horizontal, vertical, or diagonal neighbors.