Place the integers $\displaystyle 1,2,3, \ldots, n^2$(without duplication) on an $\displaystyle n \times n$ chessboard, with one integer per square. Show that there exist two adjacent entries such that their difference is at least $\displaystyle n+1$. (Adjacent means horizontally, vertically or diagonally adjacent.)
I tried using "extreme principle" but that doesn't lead me anywhere. Any ideas?