3x3 grid, how many different ways can you navigate this grid so that you touch upon every square of the grid exactly once?

Question

Consider a 3x3 grid of squares. You control a piece that can navigate through the grid by either moving up, down, left or right. If your piece starts in the top left corner of the grid, how many different ways can you navigate this grid so that you touch upon every square of the grid exactly once?

I think I could brute-force this by drawing out all scenarios, but I am not sure how to do this mathematically. I could code it out and use DFS as well but I want to learn how to do it via hand mathematically.

Thank you.

Answer 1

There are $8$ paths. There are $2$ paths (RD and DR) that reach the center square in $2$ moves. If you choose either of those starts, the rest of the path is forced. That accounts for $2$ paths.

Otherwise, there are $2$ ways (RR and DD) to end in an adjacent corner after $2$ moves. If you find yourself in an adjacent corner after two moves, your next move, of course, is forced because there are only two squares directly connected to a corner square. Thus, your start is either RRD or DDR.

If you start RRD and your next move is L, the rest of your path is forced. Similarly, if you start DDR and your next move is U, the rest of your path is forced. That accounts for $2$ more paths.

Finally, if you start RRDD, you have remaining a $2 \times 2$ block and your next move is forced to be L. You can traverse the rest of the $2 \times 2$ block either clockwise or counterclockwise, accounting for $2$ more paths. Similarly, there are $2$ paths that begin DDRR.

There are, therefore, a total of $8$ paths.

You can simplify the presentation of the proof a bit by just counting paths that begin R and then (by symmetry) multiplying by $2$.

Answer 2

You can solve easly this particular problem by observing these 3 things about a $N$x$N$ grid at any state of it:

$1$: If 2 states can be obtained by rotaition/reflexion of each other then they have the same number of paths (this is why you can go either way at first and then multiply by 2).

$2$: If the remaining squares form a contigous fraction of the perimeter of the grid there are as many paths as endpoints you can reach in one move (0,1 or 2).

$3$: $2$ implies that the 2x2 grid has 2 paths at any start.

Then you do this:

1. You go down, now you can go either down or right.
2. You go right, $2$ implies one path, you are back at the start.
3. You go down down right (obbligated) now you can go either up or right.
4. You go right, $3$ implies 2 paths, you go back.
5. You go up (obbligated), $2$ implies one path. So by moving down at first move you have 4 paths, $1$ implies 8 total paths.