Count distinct rectangular grid mazes with acyclical paths for given size

Question

I was trying to solve the following problem:

An mn maze is an mn rectangular grid with walls placed between grid cells such that there is exactly one path from the top-left square to any other square. The following are examples of a 912 maze and a 1520 maze:

Let C(m,n) be the number of distinct mn mazes. Mazes which can be formed by rotation and reflection from another maze are considered distinct.

It can be verified that C(1,1) = 1, C(2,2) = 4, C(3,4) = 2415, and C(9,12) = 2.5720e46 (in scientific notation rounded to 5 significant digits).
Find C(100,500)

Now, there is an explicit formula which gives the right result, and it is perfectly computable. However, as I understand, the solutions to Project Euler problems should be more like clever algorithms and not explicit formula computations. Trying to formulate the solution as a recursion, I could only arrive at a linear system with number of variables growing exponentially with the size of the maze (more precisely, if one tries to write a recursion for the number of mxn mazes with m held fixed, one arrives at a linear system such that the number of its variables grows exponentially with m: one of the variables is the number of mxn mazes with the property given in the declaration of problem 380, while the other variables are numbers of mxn mazes with more than one connected component which touch the boundary of the maze in some specific "configuration" - and the number of such "configurations" seems to grow exponentially with m. So, while this approach is feasible with m=2,3,4 etc, it does not seem to work with m=100).

I thought also to reduce the problem to subproblems which can be solved more easily, then reusing the subproblems solutions when constructing a solution to larger subproblems(the dynamic programming approach), but here I stumbled upon the fact that subproblems seem to involve mazes of irregular shapes, and again, the number of such mazes is exponential in m,n.

If someone knows of a feasible approach (m=100, n=500) other than using explicit formulas or some ad hoc theorems, and can hint where to look, for me it would be quite interesting.

Answer 1

This is basically a spanning tree counting problem. Specifically, it is counting the number of spanning trees in a grid graph.

Counting Spanning Trees in a Grid Graph

From the "Counting spanning trees" section of the Wikipedia entry:

The number t(G) of spanning trees of a connected graph is a well-studied invariant. In some cases, it is easy to calculate t(G) directly. For example, if G is itself a tree, then t(G)=1, while if G is the cycle graph C_n with n vertices, then t(G)=n. For any graph G, the number t(G) can be calculated using Kirchhoff's matrix-tree theorem...

Related Algorithms

Here are a few papers or posts related to counting the number of spanning trees in grid graphs:

• "Counting Spanning Trees in Grid Graphs", Melissa Desjarlais and Robert Molina Department of Mathematics and Computer Science, Alma College, August 17, 2012? (publish date uncertain)
• "Counting the number of spanning trees in a graph - A spectral approach", from Univ. of Maryland class notes for CMSC858W: Algorithms for Biosequence Analysis, April 29th, 2010
• "Automatic Generation of Generating Functions for Counting the Number of Spanning Trees for Grid Graphs (and more general creatures) of Fixed (but arbitrary!) Width", by Shalosh B. Ekhad and Doron Zeilberger

The latter by Ekhad and Zeilberger provided the following, with answers that matched up with the problem-at-hand:

If you want to see explicit expressions (as rational functions in z) for the formal power series whose coefficient of zn in its Maclaurin expansion (with respect to z) would give you the number of spanning trees of the m by n grid graph (the Cartesian product of a path of m vertices and a path of length n) for m=2 to m=6, the the input gives the output.

Specifically, see the output.

Sidenote: Without the provided solution values that suggest otherwise, a valid interpretation could be that the external structure of the maze is important. Two or more mazes with identical paths would be different and distinct in this case, as there could be 3 options for entering and exiting a maze on a corner, where the top left corner would be open at top, top left corner open on left, or open on both left and top, and similar for a corner exit. If trying to represent these maze possibilities as a tree, two nodes may converge on entry rather than just diverging from start to finish, and there would be one or more additional nodes for exit possibilities. This would increase the value of C(m,n).

Answer 2

The insight here comes from the question (emphasis mine)

A .. maze is a rectangular grid with walls placed between grid cells such that there is exactly one path from the top-left square to any other square.

If you think of the dual of the maze, i.e. the spaces one can occupy, it is clear that a maze must form a graph. Not just any graph either, for there to be a singular path the graph must not contain any cycles which makes it a tree. This reduction to a combinatorics problem suggests an algorithm. In the spirit of Project Euler, the rest is left as an exercise to the reader.