Project Euler Problem 380

Solution

Answer: 6.3202e25093

For an $m\times n$ maze, the condition

“there is exactly one path from the top-left square to any other square”

means the maze is a spanning tree of the $m\times n$ grid graph.

So the problem asks for the number of spanning trees of the rectangular grid graph $G_{m,n}$.

By the Matrix-Tree Theorem, the number of spanning trees of a graph equals any cofactor of its Laplacian matrix.

For rectangular grid graphs, this determinant can be diagonalized explicitly using discrete Fourier modes, giving the classical closed form:

$$C(m,n) = \frac1{mn} \prod_{x=0}^{m-1} \prod_{y=0}^{n-1} !{}^{\prime} \left( 4 -2\cos\frac{\pi x}{m} -2\cos\frac{\pi y}{n} \right),$$

where the prime means the term $(x,y)=(0,0)$ is omitted.

This formula matches the examples:

$$C(2,2)=4, \qquad C(3,4)=2415,$$

and

$$C(9,12)\approx 2.5720\times 10^{46}.$$

A clean Python implementation is:

import math

def maze_count(m, n):
    log10_value = 0.0

    for x in range(m):
        for y in range(n):
            if x == 0 and y == 0:
                continue

            term = (
                4
                - 2 * math.cos(math.pi * x / m)
                - 2 * math.cos(math.pi * y / n)
            )

            log10_value += math.log10(term)

    # divide by mn
    log10_value -= math.log10(m * n)

    exponent = int(math.floor(log10_value))
    mantissa = 10 ** (log10_value - exponent)

    return mantissa, exponent

# verification
print(maze_count(3, 4))   # 2.415e3  -> 2415
print(maze_count(9, 12))  # 2.5720e46

# target
print(maze_count(100, 500))

For $(m,n)=(100,500)$, this gives

$$C(100,500) \approx 6.320236505\ldots \times 10^{25093}.$$

Rounded to 5 significant digits:

Answer: 6.3202e25093