Keep the grid differences below $x$

Question

Inspired by Keep the chessboard differences below eight

Given an $n\times m$ grid of squares, what is the smallest possible integer bound $x$ for which it is possible to fill the squares with the integers $1,\ldots,nm$ so that each two squares with a common edge have an absolute difference of $x$ or less? And what is the best strategy of finding such a grid?

Answer 1

You can do it with $x=\min(n,m)$. Put $1$ in the upper left and fill each diagonal starting at the bottom and going up and right in order. A $4 \times 5$ example is below:

$$\begin{array}{|r|r|r|r|r|}\hline \phantom{00}1 & \phantom{00}3 & \phantom{00}6 & \phantom010 & \phantom014\\\hline 2 & 5 & 9 & 13 & 17\\\hline 4 & 8 & 12 & 16 & 19\\\hline 7 & 11 & 15 & 18 & 20\\\hline \end{array}$$

To see this is the best possible, it is easier to do the $x \times x$ square as you (may) get to use smaller numbers for this part of the grid. Now follow the proof in the linked question to see that $x-1$ is not possible.