# Traversing the infinite square grid

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board.

At move $n$ one must take $a_n$ steps in one of the directions, north,south, east or west. And every square we walk over is marked as visited, we are not allowed to walk over a visited square twice.

Is there a sequence of directions, such that we can visit every square of the board exactly once if $a_n=n$?

Is there such a sequence if we are allowed to walk in diagonal directions aswell?

Is there a general algorithm to check, given $a_n$, if a path exists?

Is there a path in any of the above cases for $a_n=n^2$?

#### Solutions Collecting From Web of "Traversing the infinite square grid"

If your $a_n$ are increasing, this is always impossible.

Suppose (by symmetry) that you start by going south. Sooner or later you will have to move north. However, after your first north move, you’ll have drawn an U shape of width $a_i$ on the grid, and there will be no way for you later to enter the interior of the U from the north and get back up again without having an $a_j$ available that is at most $a_i-2$.

This argument also almost shows that it is impossible with a merely non-decreasing sequence of $a_n$’s.

Things appear to be more murky if diagonal moves (like bishops in chess) are allowed.