Snake Game Combinatorics

Question

I am doing an algorithmic analysis of the video game snake. It would be helpful to know the total amount of game positions in a $10\times10$ board or an approximation of it.

There is another question on this site that uses a $5\times5$ board and a snake of length $3$ and can solve this problem, but what I have realized is that since the snake is not allowed to overlap itself, it gets much more complicated to compute its possibilities after length $4$, and I need to know all the way up to length $100$ on a $10\times10$ board.

Does anyone know how to do this?

Thanks

Answer 1

I do not think anyone is going to have an exact answer, but here is an upper bound.

There are $100$ positions for the snake's head, at most $4$ possibilities for the body segment next to the head, and at most $3$ for each subsequent body part. Therefore, there are at most $400\cdot 3^{k-2}$ possibilities for a snake of length $k$. Summing from $k=2$ to $100$ gives $$\#\text{ snake positions}\le 400(3^{99}-1)/2.$$I suppose you should multiply that by $100$ to account for the position of the food piece.