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.)

  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Jan 13 '12 at 2:22
  • 3
    $\begingroup$ How is this an "edit"? It's now a completely different question... plus, now @Brian's comment makes absolutely no sense. $\endgroup$ – mjqxxxx Jan 13 '12 at 12:54
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Jan 13 '12 at 13:10
  • $\begingroup$ I've answered the new question; I didn't see the original one. $\endgroup$ – David Bevan Jan 13 '12 at 13:15
  • $\begingroup$ 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? $\endgroup$ – Raphael Jan 13 '12 at 22:16

No closed formula is known for the number of Hamiltonian paths or cycles on a rectangular lattice.

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).

Here are a few papers that contain research related to this question: 1981, 1990, 1994, 1997 and 2007.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.