I got the following as an interview question:
Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the number of Hamiltonian paths from upper left to lower left: a path such that every vertex is visited only once, and (this follows from the first statement) such that each edge is used at most once.
The grid world is a 4x10 matrix (4 rows and 10 columns).
Is it really this hard?
Matrix method for counting Hamiltonian cycles
And:
Number of Hamiltonian Paths from Lower Left to Upper Right
These papers seem dated--94, 97--but are they really asking a question that qualifies for publishing in a combinatorical journal?
Then I ran into this: SO question: number of Hamiltonian paths
And am thinking dynamic programming, or divide and conquer...but it is really not clear how one would go about doing this. Is there a way to solve this problem in reasonable time?