# Visit all houses in $m \times n$ town

Suppose a town is an $m \times n$ grid of houses, how many ways is there to visit every house exactly once, if one is only allowed to visit one of the (max 4) neighbouring houses in 1 step?

How many if one requires the starting and ending path to be a house on the edge of town?

And how many if one is allowed to visit any of 8 neighbouring houses? (Path should not cross itself.)

-
If I understand this correctly, you’re essentially asking whether there is a finite set of non-deterministic finite state automata from which every possible non-deterministic finite state automaton can be built. –  Brian M. Scott Jan 13 '12 at 2:22
How is this an "edit"? It's now a completely different question... plus, now @Brian's comment makes absolutely no sense. –  mjqxxxx Jan 13 '12 at 12:54
@mjqxxxx: Thanks for the heads-up. I’ll leave my previous comment up for a bit, in case the original question gets rolled back, but this is a bit disconcerting, to say the least. –  Brian M. Scott Jan 13 '12 at 13:10
I've answered the new question; I didn't see the original one. –  David Bevan Jan 13 '12 at 13:15
Original question appeared on cstheory.SE. Maybe the user had another question on their mind and instead of asking a new one, they recycled the one moved to cstheory.SE? –  Raphael Jan 13 '12 at 22:16

The following entries in OEIS are relevant to your questions: A003763 (cycles on $2n\times 2n$ lattice), A120443 (paths on $n \times n$ lattice), A140519 (king tours on $n \times n$ board) and A140521 (directed king tours on $n \times n$ board).