Numbers $1,2,\ldots,n^2$ are placed in some order on an $n\times n$ board. An "ascending sequence" is an increasing sequence of numbers such that any two consecutive numbers in the sequence are in adjacent (side or corner-sharing) cells. What is the minimum possible length of the longest ascending sequence? (The minimum is taken over all the ways of placing the $n^2$ numbers.)
If "adjacent" only means side-sharing cells, this minimum can be as low as $2$, by putting the lower half of the number on the black chessboard cells and the upper half on the white chessboard cells:
$$1\text { }15\text { }3\text { }13$$ $$16\text { }2\text { }14\text { }4$$ $$5\text { }11\text { }7\text { }9$$ $$12\text { }6\text { }10\text { }8$$
But when "adjacent" means side or corner-sharing, this example has a long ascending sequence $1,2,3,4,7,8,9,10,11,14,15,16$.
Hint: For even $n$, label the board squares with $A,B,C$ and $D$ as shown:
Place the numbers $1,2,\dots, n^2/4$ in the $A$ squares, the numbers between $n^2/4+1$ and $n^2/2$ in the $B$ squares, the numbers $n^2/2+1$ to $3n^4/4$ in the $C$ squares, and the remaining high numbers in the $D$ squares. This ensures every ascending path has length at most four. Is it possible to label the board without an ascending path of length three?