4

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:

enter image description here

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.

John Donn
  • 1,718
  • 2
  • 19
  • 45
  • Similar question: http://stackoverflow.com/q/38502/178651 – Gary S. Weaver Feb 26 '13 at 15:48
  • well, apart from the fact that both questions talk about mazes, they are not actually similar: I don't need to generate mazes, I need to count them. Unless you suggest that there is a direct connection between the two.. – John Donn Feb 28 '13 at 11:18
  • 1
    imho, an explicit formula computation is a very clever solution. – yurib Feb 28 '13 at 15:25

4 Answers4

5

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:

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

Gary S. Weaver
  • 7,966
  • 4
  • 37
  • 61
  • the problem to count mazes by iterating over them is that they are just too many for the 100x500 case. – John Donn Mar 01 '13 at 08:16
  • I don't think that is correct, unless you are talking about the time to process them. And, the question said nothing about a time limit. – Gary S. Weaver Mar 01 '13 at 13:53
  • Just to see what I mean- for counting itself, in Ruby, you could use: http://www.ruby-doc.org/core-2.0/Bignum.html and here is a C implementation: http://gmplib.org/ but you can't just count if they have to be distinct unless you are just counting spanning trees. – Gary S. Weaver Mar 01 '13 at 17:24
  • I am not against you contributing to SO, but would you please putting some header to split out your text? Your post is so long it takes 3 pages worth of scrolling, and all I see is a wall of text. – nhahtdh Mar 01 '13 at 18:06
  • 1
    @GaryS.Weaver: Yes, **a lot** better. – nhahtdh Mar 01 '13 at 19:13
  • thank you for your (edited) answer; the reference "Counting Spanning Trees in Grid Graphs" seems similar to the linear recursion I referred to in my question, the second reference you cite seems to me, if I'm right, irrelevant, the third cites the correct theorem to use in this case (which is not Cayley's theorem, but Kirchhoff's theorem). The fourth (Zeilberger's) is probably the most relevant if I could only understand it.. However, I doubt that it would provide the answer for the 100x500 case (as asked in the problem: a definite number of such and such precision in scientific notation). – John Donn Mar 06 '13 at 11:14
  • thank you again for the reference to Zeilberger's article, I upvote your answer for that. – John Donn Mar 06 '13 at 11:22
  • @Giovanni-Rossi Cleaned it up some more. Thanks! – Gary S. Weaver Mar 06 '13 at 14:39
4

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.

Hooked
  • 84,485
  • 43
  • 192
  • 261
  • thank you, I am aware of this reduction, the problem is what to do after.. Now, there is a general theorem about spanning trees in a graph, but it does not seem to give a computationally feasible way to compute the number sought.. Thus I look for another way to compute it without using more specific results from combinatorics (there is, as I said, a nice formula in this case which gives a solution). – John Donn Mar 01 '13 at 08:10
1

SPOILER AHEAD

I was wrong, stating in one of the comments that "Now, there is a general theorem about spanning trees in a graph, but it does not seem to give a computationally feasible way to compute the number sought". The "general theorem", being the Matrix-Tree theorem, attributed to Kirchhoff, and referred to in one of the answers here, gives the result not only as the product of the nonzero eigenvalues of the graph Laplacian divided by the order of the graph, but also as the absolute value of any cofactor of the Laplacian, which in this case is the absolute value of the determinant of a 49999x49999 matrix. But, although the matrix is very sparse, it still looked to me out of reach.

However, the reference

http://arxiv.org/pdf/0712.0681.pdf

("Determinants of block tridiagonal matrices", by Luca Guido Molinari), permitted to reduce the problem to the evaluation of the determinant of an integer 100x100 dense matrix, having very large integers as its entries.

Further, the reference

http://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf

by Erwin H. Bareiss (usually one just speaks of "Bareiss algorithm", but the recursion which I used and which is referred to as formula (8) in the reference, seems to be due to Charles Dodgson, a.k.a. Lewis Carroll :) ), perimitted me then to evaluate this last determinant and thus to obtain the answer to the original problem.

John Donn
  • 1,718
  • 2
  • 19
  • 45
0

I would say that finding a explicit formula is a correct way to solve an Euler problem. It will be fast, it can be scaled. Just go for it :)

Jakob
  • 751
  • 4
  • 17
  • Unless it's still hard to compute. Take the binomial coefficient as an example. – Richard Pump Feb 25 '13 at 11:41
  • 2
    -1: The OP says he already knows the formula and he's looking for something else, so your answer is not at all helpful. – IVlad Feb 25 '13 at 11:47
  • 2
    He also says that as he understands it, an explicit formula is not something to aim for on projectEuler. Which is not true since an explicit formula can solve many problems faster than algorithms. Finding an explicit formula can be hard by itself. My point was that he should not feel he has failed just becasue he found a explcit formula. – Jakob Feb 25 '13 at 20:17
  • I did not mean to imply that I have found the formula myself :) – John Donn Feb 26 '13 at 12:11