[seqfan] Re: Alternating Vertical and Horizontal Moves In Grid

[David Wilson]

It seems fairly clear to me that starting anywhere gives:

a(n) = 1, if n = 1
n^2-n+2 if n even
n^2-2n+4 if n odd > 1

and starting in the corner is

a(n) = 1, if n = 1
n^2-n+2 if n even
n^2-2n+3 if n odd > 1

It would probably not be too hard to establish that these are lower 
bounds. For example, in

http://ilex.iit.cnr.it/resta/Leroy2.pdf

the figures for sides 4, 6, 8, 10 and 12 are spiral paths. Indeed, if 
you turn the pictures for sides 2(not shown), 4, 6, 8 and 10 upside 
down, you get the lower right corners of the pictures for sides 4, 6, 8, 
10 and 12, respectively, and that extending the side n path to the side 
n+2 path introduces 2 unvisited squares. This can be massaged into a 
proof that the 2n side square has at most n-2 unvisited squares, giving 
a path of at least n^2-n+2 squares.

The difficult part is proving you can do no better. I suspect you can 
show that the optimal path must have a minimal number of bends, and that 
each bend must have an associated unvisited square.

In the images, the odd-side squares have more erratic paths, but I am 
guessing a pattern might be established for them as well.