While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time algorithms exist for enumerating all such paths/cycles? Perhaps for certain kinds of k-ary n-cube graphs? I hope this question isn't too open-ended...


Update - Is the problem of iterating Hamiltonian path/circuits known to be NP-complete for the N-cube? 



Special cases for efficient enumeration of Hamiltonian paths on grid graphs?
There are certainly special graphs that are always Hamiltonian (if every vertex of a graph of n vertices has degree at least n/2, say) and these have efficient algorithms associated with them.


For instance, [this paper](http://www.math.cmu.edu/~af1p/Texfiles/5out.pdf) proves the graph of a random 5-outregular digraph is Hamiltonian and there is an algorithm that finds a Hamiltonian cycle in polynomial time.


