This is a bit difficult to explain as I'm not a mathematician and don't know the correct terms, but I'll try my best. Any tips on improvement are welcome.
I did find this question but the requirements are different and it traverses the vertexes instead of the tiles.
I have a grid where I can travel from any tile to adjacent tiles, but a maximum of only one time and I want to know how many possible paths there are on the grid with a minimum length of one and a maximum length of the number of tiles.
So here are the rules listed:
- The grid is a rectangle (let's assume a 5x5 grid for this post)
- You can start at any tile in the grid
- You can travel to any surrounding tiles horizontally, vertically or diagonally with a maximum distance of 1
- No tile can be used more than once in the same path
I tried to calculate the amount of paths by the following:
- Number of tiles =
5 x 5 = 25 - Number of maximum travel possibilities =
8 - Number of minimum travel possibilities =
1 - Number of options decreases with each step, but each step is a new path as well
N - 1 - $$(25 - 1) ^ {(8 - 1 - 1)} = 191102976$$
However, I have no clue how to verify if I'm correct (I'm probably very wrong) here. In an attempt to approach it deterministically I started writing a program in C# to count it, but it has been a while and my pc's memory is getting full and the counter is at 163 million and still counting. (EDIT: My PC ran out of memory at 2533725588 paths and needed to process at least 117 million more).
What is the correct approach to calculate the number of paths here?
Here are a few grid examples:
