Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
3  
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
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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