# In how many ways can a rectangular maze be traversed?

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

• Have you tried to interpret this question in graph theory? – fantasie Dec 15 '18 at 10:24
• 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? – fantasie Dec 15 '18 at 10:33
• 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. – Haoran Chen Dec 15 '18 at 10:39

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!