Can the numbers $1,2,...,n^2$ be written in the cells of an $n\times n$ board in such a way that any two consecutive numbers are in adjacent cells (sharing a side), and all perfect squares are in the same column?
Note: The original problem comes from All-Russian Mathematical Olympiad 1995 (fourth round, question 8) for the special case where $n=11$.
By counting the number of cells in the left and right side of that column we know that for an odd number $n$, there's not an arrangement satisfying those conditions. So we only have to consider the case where $n$ is even.
For $n=4k+2$ we can make explicit construction, but writing it down clearly may be difficult. For $n=4k$, it seems that there's no arrangement. However, I have no idea how to prove it.
Can someone solve the case completely where $n$ is even?