Ponder This Challenge - October 2025 - Counting Mazes

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  The numerical solutions are:

  1.148e1174
  1.609e61571
  

  Obtaining those solutions via brute-force counting is obviously unfeasible, but there are some beautiful tricks that can be applied. First, mazes as they are defined here are nondirected trees in a graph where the vertices represent cells, and there is an edge between two adjacent cells. This is a classical method to generate mazes: construct the graph, then run Kruskal's or Prim's algorithm on it (adding weights to the graph enables one to control the shape of the generated maze). However, in this problem we don't want to generate a maze, rather to count all mazes, hence count all spanning trees of the graph.

  A beautiful theorem of basic graph theory is Kirchhoff's matrix tree theorem, which reduces the enumeration of spanning trees in a general (directed/non-directed) graph to the computation of the determinant of the graph's Laplacian matrix. This is further simplified if one knows the eigenvalues of the matrix; there is at least one zero eigenvalue, and if the rest of the eigenvalues for the $n\times n$ matrix are $\lambda_1,\ldots,\lambda_{n-1}$ then the number of spanning trees is $\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}$.

  Directly applying the matrix tree theorem in this specific case is tricky, as the numbers were chosen so the resulting matrix is quite large. However, for the specific graph in question we can simply matters considerebly, since it can be seen as a product of two simple lines graphs. Let us denote by $C_n$ the graph with vertices $V=\{1,2,\ldots,n\}$ and edges $E=\{(k,k+1)\ |\ 1\le k<n\}$. Then the graph for the $n\times m$ grid is $C_{n,m}=C_n\square C_m$ where $\square$ denotes the "box product" of graphs, where the vertices of $G_1\square G_2=$ are $V_1\times V_2$ and the edges are $\{(a,u),(b,v)\ | \ ((a,b)\in E_1\wedge u=v)\vee (a=b\wedge(u,v)\in E_2\}$ (conceptually, the box product of graphs corresponds to the notion of trversing both graphs at the same time, taking a step in only one of the graphs each time).

  For box products $G_1\square G_2$, if $\lambda_1\ldots,\lambda_n$ and $\tau_1\ldots,\tau_m$ are the eigenvalues of both graph laplacians, then the eigenvalues of the laplacian of $G_1\square G_2$ are $\{\lambda_i+\tau_j\ |\ 1\le i\le n, 1\le j\le m\}$. Hence, the problem is reduced for finding the eigenvalues of the line graph $C_n$, and it can be shown using Chebyshev polynomials that these eigenvalues are of the form $4\sin^2\left(\frac{k\pi}{2n}\right)$ for $1\le k \le n-1$. This leads us to the formula solving the puzzle for general $n,m$:

  $T(n,m) = \frac{1}{nm}\prod_{k=0}^{n-1}\prod_{h=0}^{m-1}\left(4\sin^2\left(\frac{k\pi}{2n}\right)+4\sin^2\left(\frac{h\pi}{2m}\right)\right)$

  This can be slighty simplified by noting that for $h=0$ we have $\prod_{k=0}^{n-1}4\sin^2\left(\frac{k\pi}{2n}\right)=n$ (since this is the product of eigenvalues for $C_n$, which has only one spanning tree) and similarily for $k=0$, so the formula simplifies to

  $T(n,m) = \prod_{k=1}^{n-1}\prod_{h=1}^{m-1}\left(4\sin^2\left(\frac{k\pi}{2n}\right)+4\sin^2\left(\frac{h\pi}{2m}\right)\right)$

  See "The Discrete Laplacian of a Rectangular Grid " by T. Edwards for further details.

  Computing the product in practice can cause numeric problems; the usual approach in such situations is computing the logarithm of the expression (trasnforming the product into a sum) and exponentiating the result.

Solvers

• *Lazar Ilic (30/9/2025 2:26 PM IDT)
• *Daniel Chong Jyh Tar (30/9/2025 2:39 PM IDT)
• *Nadir S. (30/9/2025 2:48 PM IDT)
• *Ganor Tamir & Shouky Dan (30/9/2025 2:52 PM IDT)
• *Dan Dima (30/9/2025 3:53 PM IDT)
• *Paul Revenant (30/9/2025 4:01 PM IDT)
• *Christoph Schmidt (30/9/2025 4:40 PM IDT)
• *Prashant Wankhede (30/9/2025 5:31 PM IDT)
• *Bertram Felgenhauer (30/9/2025 6:25 PM IDT)
• *Paul Lupascu (30/9/2025 6:37 PM IDT)
• *Hugo Pfoertner (30/9/2025 7:02 PM IDT)
• *Jiri Spitalsky (30/9/2025 8:57 PM IDT)
• *Alex Fleischer (30/9/2025 9:46 PM IDT)
• *Stephen Ebert (30/9/2025 11:18 PM IDT)
• *Sanandan Swaminathan (1/10/2025 1:53 AM IDT)
• *Hakan Summakoğlu (1/10/2025 2:18 AM IDT)
• *Alper Halbutogullari (1/10/2025 2:48 AM IDT)
• *Guangxi Liu (1/10/2025 3:41 AM IDT)
• *Gary M. Gerken (1/10/2025 6:01 AM IDT)
• *Shirish Chinchalkar (1/10/2025 6:12 AM IDT)
• *Martin Thorne (1/10/2025 6:51 AM IDT)
• *Reda Kebbaj (1/10/2025 2:26 PM IDT)
• *Juergen Koehl (1/10/2025 4:35 PM IDT)
• *Fakih Karademir (1/10/2025 11:48 PM IDT)
• *Abraham AJ Arshad (2/10/2025 9:09 AM IDT)
• *Florian Sikora (2/10/2025 12:05 PM IDT)
• *Daniel Bitin (2/10/2025 12:38 PM IDT)
• *Latchezar Christov (2/10/2025 3:16 PM IDT)
• *Reiner Martin (3/10/2025 12:20 AM IDT)
• *Stéphane Higueret (3/10/2025 5:41 PM IDT)
• *Dominik Reichl (3/10/2025 8:54 PM IDT)
• *Sebastian Arellano-Rubach (4/10/2025 6:50 AM IDT)
• *Peyo (4/10/2025 7:11 AM IDT)
• *King Pig (4/10/2025 11:28 AM IDT)
• Lorenz Reichel (4/10/2025 2:29 PM IDT)
• *Justin Snopek (4/10/2025 3:08 PM IDT)
• *Tim Walters (4/10/2025 7:43 PM IDT)
• Alex Izvalov (4/10/2025 8:00 PM IDT)
• *Khaled Alam (5/10/2025 5:59 AM IDT)
• Fabio Michele Negroni (5/10/2025 10:59 AM IDT)
• *Amos Guler (5/10/2025 5:19 PM IDT)
• Gumpina Rama Krishna Chaitanya (6/10/2025 7:18 AM IDT)
• *Loukas Sidiropoulos (6/10/2025 12:00 PM IDT)
• *Ankit Chakraborty (6/10/2025 2:30 PM IDT)
• *Sergey Batalov (7/10/2025 4:31 AM IDT)
• *Dieter Beckerle (7/10/2025 6:21 PM IDT)
• *Lavanya Kannan (8/10/2025 6:39 PM IDT)
• *Jordan Payette (9/10/2025 2:10 AM IDT)
• *Ignasi Guillén-Mola (9/10/2025 3:50 PM IDT)
• *Marco Bellocchi (9/10/2025 4:58 PM IDT)
• *Menshikov Maxim (9/10/2025 10:47 PM IDT)
• *Anant Chebiam (10/10/2025 10:19 AM IDT)
• *Kang Jin Cho (12/10/2025 11:23 AM IDT)
• *Rudy Cortembert (12/10/2025 12:30 PM IDT)
• *Giorgos Kalogeropoulos (12/10/2025 4:32 PM IDT)
• *Charles Pombet (12/10/2025 5:14 PM IDT)
• *Michael Liepelt (15/10/2025 4:34 PM IDT)
• *Manish Kumar (16/10/2025 11:29 AM IDT)
• *Arthur Vause (16/10/2025 3:04 PM IDT)
• *Bert Dobbelaere (17/10/2025 12:05 AM IDT)
• *Hansraj Nahata (17/10/2025 1:37 AM IDT)
• *Amrit Pritam Sarangi (18/10/2025 2:42 PM IDT)
• *Erik Hostens (18/10/2025 2:46 PM IDT)
• *Jan Fricke (19/10/2025 3:16 PM IDT)
• *Hans-Peter Schrei (19/10/2025 3:34 PM IDT)
• *Nirmal Govindaraj (19/10/2025 7:26 PM IDT)
• *Kevin Cao (21/10/2025 1:11 AM IDT)
• *Dillon Davis (21/10/2025 12:13 PM IDT)
• *David Greer (21/10/2025 2:13 PM IDT)
• *Danyil Vorobiov (22/10/2025 5:22 PM IDT)
• *Danylo Maksymov (22/10/2025 6:09 PM IDT)
• *Justin Mazenauer (23/10/2025 2:47 PM IDT)
• *Giovanni Basso (23/10/2025 8:28 PM IDT)
• *Chris Shannon (25/10/2025 7:31 AM IDT)
• *Hubert Puszklewicz (26/10/2025 9:02 PM IDT)
• *Nyles Heise (27/10/2025 6:08 AM IDT)
• *Alexander Bielik (27/10/2025 12:00 PM IDT)
• *Roman Melamud (27/10/2025 6:07 PM IDT)
• *Ahmet Yuksel & Nihal Pala (28/10/2025 11:47 AM IDT)
• *David F.H. Dunkley (29/10/2025 2:35 PM IDT)
• *Mathias Schenker (29/10/2025 7:51 PM IDT)
• Ruan Schoeman (30/10/2025 10:35 AM IDT)
• *Robert Berec (30/10/2025 3:49 PM IDT)
• *Gürkan Koray Akpınar (31/10/2025 12:06 AM IDT)
• *Jackson La Vallee (2/11/2025 4:55 AM IDT)
• *Ayusha Appaji Hongekar (3/11/2025 11:02 AM IDT)
• *Bipra Bhanu Mohanty (3/11/2025 11:06 PM IDT)
• *Anant Asati (4/11/2025 9:46 AM IDT)
• Zoltan Haindrich (4/11/2025 2:54 PM IDT)
• *Radu-Alexandru Todor (5/11/2025 2:03 AM IDT)
• *Li Li (5/11/2025 4:40 AM IDT)
• *Punit Ketan Ranawat (5/11/2025 2:31 PM IDT)
• Pari Soni (5/11/2025 3:44 PM IDT)
• *Daniel Copeland (5/11/2025 5:43 PM IDT)
• *Evan Semet (5/11/2025 8:31 PM IDT)
• *Ruchir Sujit Barhate (6/11/2025 11:55 PM IDT)
• Motty Porat (7/11/2025 1:11 AM IDT)
• *Satyadev Suvesh (7/11/2025 3:45 PM IDT)