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