So I asked a question on stack overflow and they suggested I migrate over here. I'm writing a program to solve the following problem:
Given a grid of x by y dimensions, calculate the number of paths through it that start in one corner (let's say top right) and end in another (bottom right) and pass through every vertex exactly once
I've just been brute forcing it but it gets slow quickly and people on StackOverflow said I didn't even need to bother with traversal, and that this was just a math problem. Does anyone have any insight into how I could solve it this way?
Best Answer
There's the paper "The number of Hamiltonian paths in a rectangular grid", that gives generating functions for $m \times n$ grids with $m \leq 5$. It seems like a difficult problem otherwise.