Suppose that the n^2 cells of an nxn array are labeled with the integers 1, ..., n^2, going left-to-right and top-to-bottom.  Then 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.