  Suppose that the $n^2$ vertices of the grid graph $P_n^2$ are labeled, such
that the set of their labels is $\{1,2,\ldots,n^2\}$. The labeling induces a
walk on $P_n^2$, beginning with the vertex whose label is $1$, proceeding to
the vertex whose label is $2$, etc., until all vertices are visited. The
question of the maximal possible length of such a walk, denoted by $M(P_n^2)$,
when the distance between consecutive vertices is the Manhattan distance, was
studied by McNeil, who, based on empirical evidence, conjectured that
$M(P_n^2)=n^3-3$, if $n$ is even, and $n^3-n-1$, otherwise. In this work we
study the more general case of $P_m\times P_n$ and capture $M(P_m\times P_n)$,
up to an additive factor of $1$. This holds, in particular, for the values
conjectured by McNeil.
