What is a better algorithm for finding routes that traverse all vertices in a graph?

Question

So I have the following problem:

Given a grid of x by y dimensions, calculate the number of routes through it that start in one corner (let's say top left) and end in another (bottom right) and pass through every vertex.

So my current method just brute forces it by just trying every possible path and counting the ones that reach the finish and traverse every node. While it works, it's O(n^2) and gets unbelievably slow extremely quickly. I'm not sure how to do it combinatorially because of the requirement that the path traverse every vertex.

I've looked up more complex algorithms, and Hierholzer's algorithm for calculating Eulerian paths seems somewhat related but not perfect because nodes cannot be traversed more than once for this.

As it is, my program works, but badly, and I would like to make it more efficient. Are there better algorithms I could be using?

Edit Thanks for the answers so far. Just to clarify, all nodes in the 2d grid are connected by n/e/s/w

Also, the grid does not have to be a square

Answer 1

There is not much you can do, because it's Hamiltonian path problem, which is NP-complete.

However, you may actually search for something else and add some restrictions to the problem you are trying to solve...

EDIT:

As @JanDvorak noted, your specific restriction is that your are using square grid. My findings so far:

If x is even, than there is no way to go through all vertices starting from top left corner and end in bottom right. Proof:

Lets count directed movements along axes, e.g. up is -1, down is 1, left is -1, right -1. So, having x by x grid, your total movement would be 2*x. At each vertex (except the last one!) your are selecting only one direction. So, if there is even number of vertices you need to go through, your total movement would be even and vice versa for odd. If x is even, than there is odd number of vertices, but total movement is stil even => you are not able to find any way.