5
$\begingroup$

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

  • 0
    Original question appeared on [cstheory.SE](http://cstheory.stacke$x$change.com/questions/9730/two-questions-on-finite-state-machines). Maybe the user had another question on their mind and instead of asking a new one, they recycled the one moved to cstheory.SE?2012-01-13

1 Answers 1

3

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.