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?