Counting the number of paths through a grid graph traversing all vertices exactly once

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?

-
I think it would be useful to state of parity checking case in question. – hate-engine Jan 10 '13 at 0:27
Your title seems to imply that in the body you're using the term "route" to denote a path that contains each vertex at most once? I hadn't come across that usage before. – joriki Jan 10 '13 at 0:30
@joriki Not sure what the proper term is, but I edited it to "path." – CharmQuark Jan 10 '13 at 0:32
No, you introduced a new unexplained discrepancy between the title and the body. – joriki Jan 10 '13 at 0:37
Augh, nitpicking! It's clear we want the number of Hamiltonian paths. – Lopsy Jan 10 '13 at 0:44

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.

-

Here's an 'educational' video that tries to answer a similar question:

http://youtu.be/Q4gTV4r0zRs

Also, I think this is an excellent computer science question (ie math is not ready for such hard problems, lol).

Here is your question being used as a programming challenge. My guess is a good computer science answer involves a (depth-first) brute-force search with clever pruning along the way.

-