# How many ways are there to traverse a 3 by 3 grid such that you start at (0,0) and end at (2,2)?

How many ways are there to traverse an $n$ by $n$ grid such that you start at $(0,0)$ and end at $(n-1,n-1)$ given these conditions:

1)You can traverse each branch at most one time.

2)You can pass through each node at most one time.

3)You can move north, south, east, and west.

I'm familiar with a similar question where you can only move north and east, but the question becomes significantly more challenging when you add these other directions. I initially tried doing this using combinatorics and then by induction, both to no avail. I then focused on the 3 by 3 grid ($n=1,2$ are simple) and started to break the 3 by 3 grid down into smaller and smaller grids and counted the ways to get from the new point on the smaller grids to $(2,2)$ and added. I got 2 paths for a 1 by 1 grid, 12 ways for a 2 by 2 grid, and 152 paths for a 3 by 3 grid (not entirely sure if this is correct, but I think the process is a valid one).

I was unable to generalize (or validate my solution for $n=1,2,3$) this problem for an $n$ by $n$ grid. How would you do this?

This sequence, the number of self-avoiding walks between opposite corners of an $n×n$ grid, is OEIS A007764. Although there is no easy formula, one of the links there details Knuth's method of computing these numbers for any graph and its specialisation to grid graphs, which I would encourage you to read.