I created a simple game, and I want to calculate approximately how many possible moves there are on a board of N x N squares. The rules are as follows:
- The player starts on the top left corner
- Every turn, the player can move to any horizontally or vertically adjacent square that has not been visited before
- The game ends when the player can no longer move
This might seem difficult, but it's really simple. Here's a two samples game 1, game 2
My question is: How can I calculate the total amount of games on any given grid?
I tried simulating it, but it takes way too long because it grows so quickly. Here is what I have now:
N - Possible Games
1 - 0
2 - 2
3 - 20
4 - 548
5 - 40440
6 - 8442742
I left my computer running for almost an hour to calculate 7 but I still didn't have a number, but based on how fast it grows I expect it to be around 4.8 billion. And I expect 8 to be around 7.6 trillion. However, I have no proof of this, I just noticed that if you calculate the percentual differences between the numbers, and then calculate the percentual differences between those, they end up being approximately 2.75
not a very rigorous proof
Is there anything I can look into that is related to this? I have no idea where to begin calculating this.