# Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Question arises from considering cache oblivious algorithms.

What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring squares? What about minimizing the expected maximum difference between two squares, chosen uniformly? [Joining the edges of the grid to form a torus]

We can do better than just filling in row by row, for instance the Morton layout (for $k = 2^n$), as illustrated below for $k = 16$

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

Is there a better layout? I'm sure someone must have thought about this before, but can't seem to find anything relevant.

-
could you define "neighbouring" more precisely? –  Suvrit Feb 23 '12 at 1:39
What is "the expected maximum difference between two" random cells in your example? –  Joseph O'Rourke Feb 23 '12 at 2:30
Note that for $k=2^n$, the "filling in row by row" yields exactly the same average difference as for the Morton layout, viz. $(k+1)/2$. (assuming you mean horizontal and vertical neighbors only). So after all, I'd think there is no better arrangement than "filling in row by row" for the non-torus case. –  Wolfgang Feb 23 '12 at 18:54
Solve it by brute force programs from 2 by 2 to 4 by 4, maybe higher, and see what you have. For the torus insist on 1 at upper left, such further restrictions as cut down on essentially identical answers. Any cyclic permutation of rows, or of columns, changes nothing in that problem. –  Will Jagy Feb 23 '12 at 23:12

This is not an answer but too long for a comment. It is a heuristical argument that $\frac{k+1}2$ should be best possible.
It is easy to see that for an optimal arrangement, $1$ and $k^2$ must both occupy corners. Supposing opposite corners, consider the (monotone) lattice paths between them. Each path covers $2(k-1)$ of the differences we are looking for, so the average difference of those is at least $\frac{k^2-1}{2(k-1)}=\frac{k+1}2$ for each such path (equal if the numbers on the path are strictly increasing, greater otherwise).
This is not a proof because summing over all those paths, the differences are not counted equally often. But maybe it can be made into a proof. Problem: if the corners of $1$ and $k^2$ are not opposite, such an argument won't work.
The torus case seems harder, it looks like optimal constuctions may be different for even and odd $k$.
For the torus, the filling in by rows also yields the same average $\frac{k^2-1}k$ as, for $k=2^n$, the Morton layout! –  Wolfgang Feb 24 '12 at 17:42