Traversing the infinite square grid

Question

Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark the ending square as visited?

If $a_n=n$ or if $a_n=n^2$?

Allowing diagonal moves as well, is there a general algorithm, given $a_n$, to check if a path exists?

Note: I am asking if given $a_n$, there exists an infinite sequence of directions, $d_n\in(N,S,W,E)$, such that for all $(x,y)\in Z^2$, there exists a finite integer $k(x,y)$, such that starting at the unit square with center $(0.5,0.5)$, marked as visited, we have after moving sequentially $a_i$ steps in direction $d_i$, for $i=1,2,3,...,k$, visited $k+1$ different unit squares, and are situated at $(x+0.5,y+0.5)$.

Answer 1

It's possible for $a_n=n$ and probably most stepsizes without modular or growth obstructions.

We have covered some subset of an mxm square, are situated at the boundary, and want to visit a cell (x,y) in our square. Choose one of the x,y axes and move far away along it, (but not upon it), until stepsize s>>m and distance is some d from the axis. Then take either 1,2, or 4 more steps along the axis. Then alternately move away, and towards the axis, 2*d steps, until we land on it. Then by moving away and towards (x,y), n times, we can reach every point of the form j-1-3n on the axis, by just moving one more step towards (x,y) where j is our current coordinate, which we could shift to anything modulo 3 when we chose one of the 1,2,4 steps. And if 3n-n>m, we dont use any other squares within the the mxm square, to visit (x,y), and emerge on the opposit side. And since s>>m, if we take one more step we are at a boundary of a new square.

WLOG suppose we are at $(0,0)$, with stepsize $s(0)$, and want to visit $(x,y)$, $0\leq x\leq m$, $0\leq y \leq m$, The full path we take consist of these moves. We move south for $k$ squares (or $j(k)$ steps), then alternate west,east, $x$ times, now we are at $(x,-k)$ with stepsize $s(j(k)+2x)$. Then we alternate south, east, $n$ times, now we are at $(x,n-k)$ with stepsize $s(j(k)+2x+2n)$, select $n$ and $k$ such that $y=s(j(k)+2x+2n)+n-k$ and $s(j(k)+2x+2n)>m$. Then take two steps north, we are now at $(x,y+s(j(k)+2x+2n)+1)$. Move 1 step east, you are now at a corner of a square bounding all visited squares, define the new m to be the side of this new square, let (0,0) your position, pick a new point (x,y) and repeat.

PS. I asked a question about the less trivial 1-D version here: https://math.stackexchange.com/questions/111377/self-avoiding-walk-on-mathbbz

Answer 2

For a one dimensional lattice, the solution with $a_n = n$ is trivial: starting from $0$, we proceed to $1, -1, 2, -2, \ldots$. After $2n$ steps, we have covered $[-n, n]$ without stepping anywhere outside of that region.

I'm not sure exactly what is meant by “traversing an infinite grid”, but I can think of two reasonable things one could ask for algorithmically: cover an $N \times N$ region for an arbitrary $N$ while hitting any number of spaces outside, or cover exactly an $N \times N$ region in $N^2$ steps.

The first method is accomplished by mimicking the one dimensional version. Suppose we want to cover the square with corners $(1,1)$ and $(N, N)$. Assume we start at $(0, 1)$, and move strictly horizontally, alternating east then west, to cover the squares $(-N + 1, 1)$ to $(N, 1)$, ending on the latter with a step of length $2N-1$. We then move east to $(3N, 1)$, then south $(3N, -2N)$, and back north to $(3N, 2)$. Now we proceed horizontally again, but perhaps not the obvious way. If we jumped back west into our desired square immediately, we would miss the spaces $(N-2, 2), (N-1, 2)$ and $(N, 2)$, and we may never see them again. So instead we go east, then jump back and forth until we have covered $(1, 2)$ to $(3N, 2)$, as well as $(5N + 3, 2)$ to $(8N+1, 2)$, ending at $(1,2)$ with a step of length $8N$. From here I suppose you see what to do: travel east, then south, then north, and repeat the sequence EWEW... ending at square $(N, 3)$. During leg $k$, we only hit squares in the horizontal line $y=k$, as well as one square at a negative $y$ value, which will never be reached again (consider the successive lengths of the steps south).

The second method cannot be done with $a_n = n$, since we will go outside the box sometime by step $N+1$. It may be possible instead with the set of $\lfloor \sqrt{n} \rfloor$ steps, though the order will have to be altered. For example, the sequence $(3,3,3,2,3,2,2,3,1,3,2,1,1,2,3)$ taken from the set $(\lfloor \sqrt{1} \rfloor, \ldots \lfloor \sqrt{15} \rfloor$ suffices to cover a $4 \times 4$ square, starting in one corner. From the southwest corner, travel $(N3, E3, S3, W2, N3, S2, E2, W3, N1, E3, W2, E1, S1, N2, S3)$ and you will finish one square west of the southeast corner.

Answer 3

[Sorry, I firstly misunderstood the question] Why not? Enumerate all squares. Assume that we have already visited some finite number of squares and are now placed in the boundary square (that is, one of its coordinates is either maximal or minimal between all visited squares). Say, in the upper square. Consider the square with minimal number, which is not visited yet. Our local goal is to visit it. For this we go to the up far-far away, then to the right, then to the down, and then to the left. So we have visited next square. Then go to the left and we are no in the leftmost square and number in it is also maximal.

I think, details are fairly simple at least in the case $a_n=n$. Indeed, if we go up by $+n$, $+(n+1)$, $+(n+2)$, \dots, $+(n+k)$ we increase y-coordinate by $n+\dots+(n+k)$. We could replace $+s$ to $-s$, then we would get $2s$ less sum. So, by choosing $k$ and $s$ (we may use not only one $s$, but say 2 or three different values of $s$, but do not choose two consecutive $s$) we may get all sufficiently large $y$-coordinates, making at most 2 or 3 down jumps. Moreover, even if $k$ is fixed we may get almost all coordinates of corresponding parity. Then we have the same freedom going to the right, then going down, and to the left. Choose parities and jumps to "opposite" directions for going to the necessary point.

For $a_n=n^2$ it should not be much harder.