title: What is a better algorithm for finding routes that traverse all vertices in a graph?
body: <p>So I have the following problem:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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?</p>
  
  <p><strong>Edit</strong> Thanks for the answers so far. Just to clarify, all nodes in the 2d grid are connected by n/e/s/w</p>
  
  <p>Also, the grid does not have to be a square</p>