IBM Ponder This #330 · October 2025

Counting Mazes

We deal with mazes which are composed of an $n\times m$ grid of rectangular cells, where each cell is connected to its four direct neighbors. For each pair of neighbors, either there is a wall between them or not. The maze is constructed in such a manner such that for every two cells in the maze, there is excactly one path between them - in particular, one path from the beginning to the end.

Under these constraints, it can be seen there are exactly 192 mazes of size $3\times 3$ (we count mazes as distinct even if they are the same up to rotation/reflection). The number of mazes grow exponentially with length; for a size of $10\times 15$ as in the picture, the number of mazes is already $1.289\cdot {10}^{66}$, which can be stylized as "1.289e66"

Your goal: Find the number of $42\times 57$ mazes. Give your result styled as above, in the form of a floating-point number with four digits of precision followed by an exact exponent.

A Bonus "*" will be given for finding the number of $342\times 357$ mazes. Give your result in the same format as above.

Solution

Best opened after a real attempt

To be added.