Le Monde puzzle [#940]

A sudoku-like Le Monde mathematical puzzle:

On a 3×3 grid, all integers from 1 to 9 are present. Considering all differences between adjacent entries, the value of the grid is the minimum difference. What is the maximum possible value?

In a completely uninspired approach considering random permutations on {1,..,9}, the grid value can be computed as

neigh=c(1,2,4,5,7,8,1,4,2,5,3,6)
nigh=c(2,3,5,6,8,9,4,7,5,8,6,9)
perm=sample(9)
val<-function(perm){
min(abs(perm[neigh]-perm[nigh]))}

which produces a value of 3 for the maximal value. For a 4×4 grid

neigh=c(1:3,5:7,9:11,13:15,1+4*(0:2),2+4*(0:2),3+4*(0:2),4*(1:3))
nigh=c(2:4,6:8,10:12,14:16,1+4*(1:3),2+4*(1:3),3+4*(1:3),4*(2:4))
perm=sample(16)
val<-function(perm){
min(abs(perm[neigh]-perm[nigh]))}

the code returns 5. For the representation

[,1] [,2] [,3] [,4]
[1,] 8 13 3 11
[2,] 15 4 12 5
[3,] 9 14 6 16
[4,] 2 7 1 10