How to arrange numbers on grid to satisfy a minimum condition?

Question

Take an $N \times M$ rectangular grid and arrange the integers from $1$ to $ N M$ so that all grid point gets an assignment without repetition, and let the integer number on location (grid point) $n,m$ be denoted by $k_{nm}$ with $1\le k_{nm}\le NM$. Calculate the differences between the neighbors: $|k_{n,m}-k_{n,m+1}|$, $|k_{n,m-1}-k_{n,m}|$, $|k_{n,m}-k_{n+1,m+1}|$, etc., and let the smallest difference among all the neighboring locations be $d^*$; obviously $d^*\ge 1$.

Which arrangement will maximize $d^*$?

---

Following the suggestion of @Steven here is his solution for the case $N=1$ that is a grid $1\times M$:

$$M=2K \qquad \text {and} \quad d^*=K-1\\ \mathbf b_1 = [1, K+1, 2, K+2, 3, K+3,4,...,2K-2, K-2, 2K-1, K-1, 2K]\\ k=1,2,..,K\\ a_{2k-1} = k; \\ a_{2k}= K+k$$ or $$M=2K-1 \qquad \text {and} \quad d^*=K-1\\ \mathbf b_1 = [1, K+1, 2, K+2, 3, K+3,4,...,2K-2, K-1, 2K-1, K]\\ k=1,2,..,K\\ a_{2k-1} = k; \\ a_{2k}= K+k$$

This can be easily extended for arbitrary $N\times M$ without changing $d^*$ by adding $M$ to each element in the row $\mathbf b_1 $ to get $\mathbf b_2$, do this for $i=1,2,..N-1;j=1,2,..M:$ $\mathbf b_{i+1}(j)=\mathbf b_i(j)+M$. Repeating this $N$ times will produce an $N\times M$ grid with $d^*=K-1.$

Here it is an $8\times 8$ grid:

$$\begin{matrix} 1 & 5 & 2 & 6 & 3 & 7 & 4 & 8\\ 9 & 13 & 10 & 14 & 11 & 15 & 12 & 16\\ 17 & 21 & 18 & 22 & 19 & 23 & 20 & 24\\ 25 & 29 & 26 & 30 & 27 & 31 & 28 & 32\\ 33 & 37 & 34 & 38 & 35 & 39 & 36 & 40\\ 41 & 45 & 42 & 46 & 43 & 47 & 44 & 48\\ 49 & 53 & 50 & 54 & 51 & 55 & 52 & 56\\ 57 & 61 & 58 & 62 & 59 & 63 & 60 & 64 \end{matrix}$$

Then my question is if this construction can be improved on?

Answer 1

Here's a variation of my previous, erroneous answer (thanks to @nickgard and @hyportnex for pointing out that I missed the fact that neighbors include diagonals):

If I'm not mistaken, the value of $d^\ast$ in your $8\times8$ example is $3$.

This can improved, e.g. by starting with a pattern of non-neighboring fields moving their way up:

\begin{matrix} . & . & 15 & . & . & . & 16 & .\\ 12 & . & . & . & 14 & . & . & .\\ . & . & 11 & . & . & . & 13 & .\\ 8 & . & . & . & 10 & . & . & .\\ . & . & 7 & . & . & . & 9 & .\\ 4 & . & . & . & 6 & . & . & .\\ . & . & 3 & . & . & . & 5 & .\\ 1 & . & . & . & 2 & . & . & .\\ \end{matrix}

Then, continue in a similar manner with the remaining numbers:

\begin{matrix} 46 & 62 & 15 & 31 & 48 & 64 & 16 & 32\\ 12 & 28 & 45 & 61 & 14 & 30 & 47 & 63\\ 42 & 58 & 11 & 27 & 44 & 60 & 13 & 29\\ 8 & 24 & 41 & 57 & 10 & 26 & 43 & 59\\ 38 & 54 & 7 & 23 & 40 & 56 & 9 & 25\\ 4 & 20 & 37 & 53 & 6 & 22 & 39 & 55\\ 34 & 50 & 3 & 19 & 36 & 52 & 5 & 21\\ 1 & 17 & 33 & 49 & 2 & 18 & 35 & 51\\ \end{matrix}

Now, the smallest difference between neighbors is $d^\ast=13$.

Answer 2

Here's an $8 \times 8$ arrangement with $d^*=15$, obtained via integer linear programming:

37 18 57  7 49 16  1 17 
53  3 38 23 64 31 47 32 
34 19 54  8 46 14 62 15 
50  2 39 24 61 29 45 30 
35 20 55  9 44 12 60 11 
51  5 40 25 59 27 43 28 
36 21 56 10 42  6 63 13 
52  4 41 26 58 22 48 33