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.