I don't think 3 is possible. Consider one corner, say top left.
To stick at an absolute difference of 3 then the row has to be the three numbers above and the column the three numbers below (or the other way round). Anything else would result in an absolute difference of 4 somewhere.
So youve eliminated 7 numbers in a row, with the corners at least 1 higher and 1 lower than the top left number
Your fourth corner now either has to be at least 4 higher than your top left number or 4 lower. In either case, it will create an absolute difference of at least 5 on one side
It's not possible to build a hypothetical grid with a max of 3.
You can first show that 1 and 16 would need to be in opposite corners: a single path from 1 to 16 requires at least (16-1)/3 = exactly 5 horizontal/vertical steps (1-4-7-10-13-16). But since it's a grid, multiple paths using different numbers are required, so at least 6 steps would be necessary (i.e. opposite corners).
The path between 2 and 16 requires at least (16-2)/3 = 4.7, i.e. 5 steps, so 2 must be next to 1. In the same way, 15 must be next to 16. That means 4 steps between 2 and 15, which averages (15-2)/4= 3.25 > 3.
16! is quite big, but we get quite strong additional restrictions. Next number not only can't repeat, but it has at least one (often two) adjacent numbers that restrict it more. An almost-brute-force (backtracing) https://pastebin.com/Cm8aVK1L generates all solution for score 4, and verifies there is no score-3 solution very quickly.
There is also no score 2 solution on 3x3 and score 4 solution on 5x5.
I spinned it looking for score 5 solutions on 6x6, but it looks like this one is already too big to get answer in the time needed to write this post.
BTW, one obvious score N on NxN grid is just numbers 1 to N^2 in order. The differences on one axis is 1, and N on the other axis.
I feel like there should be an easy argument why there is no N-1 scores, but can't see anything.
1
u/Efficient_Gear_4623 21h ago
I think bob can get max of 4 if alice plays correctly