2
$\begingroup$

A square grid of size $n\times m$ is given, where each tile can either be a floor tile or a wall tile.

One corner tile represents the entrance, and the opposite corner tile of that is called the exit.
These two tiles cannot be a wall tile and are classified as a floor tile.

A grid configuration is a valid maze if both properties hold:

  • Entrance and exit tiles are connected. That is, one should be able to move from the entrance to the exit tile by only moving up, down, left or right at each step, walking over floor tiles.

  • No floor tile is fully enclosed by wall tiles. That is, starting at any floor tile, one should be able to visit every other floor tile by moving only in those four directions, on floor tiles.

Let there be only one unique entrance-exit configuration, so one can assume that the entrance tile is at the bottom left corner and that the exit tile is at the upper right corner

How many valid mazes are there for a grid of size $n\times m$? ($n,m\ge2$)

That is, how can we find $N(n,m)$ - number of valid mazes as descrbed above?


Trivially, we have a simple bound;

$$N(n,m)\le \sum_{k=0}^{nm-2-(n+m-3)}\binom{nm-2}{k}\lt2^{nm-2}$$

Since the grid has $(nm-2)$ tiles that can either be a wall or floor, and at least $(n+m-3)$ of those tiles must be floor tiles, or we would not have a connected path from entrance to exit.

But I'm not sure how to count all of the invalid mazes that have unreachable floor tiles.

I've tried observing cases split into sets each with cases with $k$ walls to see how many invalid cases I can count depending on $k$ and $m,n$, but wasn't able to find a general pattern, nor was sure about it as I kept noticing I was missing cases or counting some more than once as I was not sure how to do it properly.

$\endgroup$
  • 1
    $\begingroup$ I doubt that you can get a closed form. I don't see an obvious recursion or summation that would allow you to compute the count algebraically. Not seeing a theoretical approach, I would write a program to get the counts for relatively small grids. Perhaps the data will reveal a pattern. $\endgroup$ – quasi Mar 6 '18 at 18:47
1
$\begingroup$

Trivially, $N(n,1)=1$, for all positive integers $n$.

For $m > 1$, some results are known . . .

  • For $N(n,2)$, a generating function is known:

$\qquad\qquad$https://oeis.org/A048739

  • For $N(n,3)$, a generating function is known:

$\qquad\qquad$https://oeis.org/A163003

  • For $N(n,4)$, data is known for $1 \le n \le 18$:

$\qquad\qquad$https://oeis.org/A163004

  • For $N(n,5)$, data is known for $1 \le n \le 17$:

$\qquad\qquad$https://oeis.org/A163005

  • For $N(n,6)$, data is known for $1 \le n \le 12$:

$\qquad\qquad$https://oeis.org/A163006

It's fairly clear that for $m > 3$, only limited data is known, with no suggestion of a formula, recursion, or generating function.

$\endgroup$
  • $\begingroup$ Note that the $N(n,7)$ oeis sequence you linked is for connected columns, not opposite corners. I noticed it when I compared entry $(7,7)$ from there to the same entry in N(n,n). $\endgroup$ – Vepir Mar 20 '18 at 14:09
  • $\begingroup$ Yes, I see. I'll edit out that entry. Thanks. $\endgroup$ – quasi Mar 20 '18 at 14:12

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.