4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Your number of paths for a 2×2 grid is correct, but that for a 3×3 grid is wrong: there are 184 paths, not 152.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.