How many ways to have a perfect game of snake?

It looks like this problem is hard.

First, let's phrase the question in terms which u̶s̶e̶ ̶b̶i̶g̶g̶e̶r̶ ̶w̶o̶r̶d̶s̶ will bring up more relevant google hits.

Recall a Hamiltonian Path is a path in a graph which touches every vertex exactly once. A Hamiltonian Cycle is a hamiltonian path which loops back on itself.

In terms of snake, a hamiltonian path is a way to lie the snake on the board in a perfect way, while a hamiltonian cycle is a way to allow you to play indefinitely (since the tail of the snake and the head of the snake will always be next to each other, so you can take another step).

A ($m \times n$) Grid Graph is exactly what you think it is. Below is a $4\times7$ grid graph:

So, if you want the number of ways to lay a snake on a board perfectly, you want the number of hamiltonian paths in a grid graph. If you want the number of ways to play snake and wind up with a perfect position, you want the number of hamiltonian cycles.

(Here is a relevant (and fun) youtube video if I've been to fast with why hamiltonian cycles are the right thing to count)

With our updated, google-able terminology, let's see what the mathematics community has to offer:

1. A hamiltonian cycle exists iff $m$ or $n$ is even (or it's the 1x1 grid, which isn't a very interesting game of snake)

2. A hamiltonian path always exists

3. There's not much more that we know.

Here is a paper ("The number of Hamiltonian paths in a rectangular grid" by Karen Collins and Lucia Krompart) which gives answers in the form of generating functions for $m = 1,2,3,4,5$. We can use these generating functions to get answers for any $n \times m$ grid for $m = 1,2,3,4,5$, though I admit I haven't read the paper, so I'm not sure what the generating functions look like.

I'm confident that this problem can be solved, but it looks like some new techniques will have to be applied in order to fully understand the issue.

Edit:

Here's some more information, this OEIS sequence is the number of hamiltonian cycles on a $2n \times 2n$ grid (reduced by symmetry). It came from this MO post, which also tells us the asymptotics of the number of perfect snake games on a $n \times n$ grid: it grows like $\tau^{n^2}$ where $1.429 < \tau < 1.530$.

As for rectangular grids (instead of square grids), the best I've found is this paper ("Enumeration of Hamiltonian Circuits in Rectangular Grids", by Robert Stoyan and Volker Strehl), which gives an efficient algorithm for computing specific examples (and shows a really cool looking connection to formal language theory!) and gives some explicit computations at the end.

Finding a general closed formula seems to be out of the question, but I'm still feeling pretty confident a 2-variable generating function will exist (though at this point I feel pretty sure it will be gross...)

I hope this helps ^_^