3
$\begingroup$

Say the maze consists of $M\times N$ cells and the visitor may enter a cell from another cell which shares a common side. The visitor starts from the top left cell and ends at the bottom right cell, visiting each cell exactly once. This is possible when $M,N$ are not both even. Question is, how many routes are there? Anybody has considered this problem before?

For example, the following routes are for $4\times 3$ maze and $5\times 5$ maze respectively. enter image description here

More generally, if the visitor starts from a given cell and ends at another given cell for which a qualifying route exists, then how many such routes are there?

Improve this question
$\endgroup$
  • $\begingroup$ Have you tried to interpret this question in graph theory? $\endgroup$ – fantasie Dec 15 '18 at 10:24
  • $\begingroup$ Besides, why this is possible when M and N are not both even? I mean, if there is a dead end in the maze, how can you visit that end cell only once? $\endgroup$ – fantasie Dec 15 '18 at 10:33
  • $\begingroup$ There is no dead end. From any cell, the visitor can visit an adjacent cell. I tried to think about this problem in graph theory but have no idea so far. $\endgroup$ – Haoran Chen Dec 15 '18 at 10:39
3
$\begingroup$

There are many different functions $f(m,n)$ for telling the number of Hamiltonian paths going from $LL$ (lower left) to $UR$ (upper right) depending on what values $m$ and $n$ take. For example, for $m=3,\ n>1,\ f(3,n)=2^{(n-2)}$. For $m=4$ and so on, they get pretty complicated. Read it if you want to know more!

Improve this answer
$\endgroup$

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.