1

If you have grid, 20x20, starting from top left and making your way to the bottom right, without ever entering the same node more than once in one path, what is the most possible number of unique paths you could have?

Example: If you have a 2x2 grid, you only have two possible unique routes without re-entering a node you have already been in.

A 3x3 grid, this number increases significantly. Is there anyway to calculate the total possible routes? I have heard of self-avoiding walk, which talks about problems like this, but I could not find any theorem or algorithm to calculate this number.

Jwags
  • 129

1 Answers1

1

You were on the right track with self-avoiding walks. The particular walks you're interested in are the more specific self-avoiding rook walks. Wolfram mathworld gives a short table of such rook walks for $m\times n$ rectangles. Furthermore, the last person to ask a similar question got an answer which linked to this OEIS sequence of the first 27 such square rook walk counts. To answer your question directly, the number of self-avoiding rook walks on a $20\times20$ grid is this:

1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844

and I'm not aware of a good way to calculate it.

Hidayet
  • 156