The Second Dumbest Way to Solve a Maze

You’re probably familiar with The Dumbest Way To Solve A Maze: a method involving the simulation of gas diffusion through the maze’s hallways. I’d like to introduce what is likely the second dumbest way to solve a maze. While this method isn’t inherently dumb (in fact, it involves math that is far from ‘dumb’), it’s so impractical for actual use that it’s simply ‘dumb’ to apply it to maze-solving.

The Riemann mapping theorem

The Riemann mapping theorem states that for a non-empty, simply connected open subset $U \subset \mathbb {C}$ there exists a biholomorphic function $f\colon U \to \mathbb D$, where $\mathbb D$ is the open unit disk. We call this function Riemann mapping ¹.

For those of you who slept over Complex Analysis classes in elementary school, here’s a simplified consequence of the theorem: if you have have a set $U$ in the plane with no holes, you can map that set onto a disk $\mathbb D$. And when I say map, I mean that disk can be a complete map of the set $U$: each point in $U$ corresponds uniquely to a point in $\mathbb D$, and vice versa.

Think of a map of the world. We use a piece of paper to represent the planet Earth, and when we point to a location on the map, we’re referring to a specific place on Earth. It is same with sets $U$ and $\mathbb D$. If we pick a point in $U$ (red dot on illustration above), Riemann map gives us a corresponding point in $\mathbb D$ (illustrated with violet dot), and therefore we can think of $U$ as a map of $\mathbb D$. But it works other way around² (because $f$ is biholomorphic), and we can understand $\mathbb D$ as a map of $U$.

In contrast to all (flat paper) maps of the world, Riemann map is perfect in sense that it it does’t “tear” space, which means that “close” points in $U$ are “close” in $\mathbb D$. Compare this to common Mercator projection maps, where Alaska and eastern Siberia, geographically close, are on opposite sides of paper.

Note that it is important that the set $U$ is simply connected (does not have holes). On the illustration above, left and middle sets are simply connected, while the right set is not.

Schwarz–Christoffel mapping

For mathematicians, the Riemann map is all they need. However, for those who actually compute something, the Riemann mapping theorem is useless. It provides information that some function exists, but it doesn’t give the algorithm to compute that function. This is where a Schwarz–Christoffel mapping comes into play. It is a formula (and hence an algorithm) that describes (inverse of) the Riemann mapping for plane polygons.

Let $U$ be the interior of plane polygon with vertices $w_1$, … $w_n$ and interior angles $\alpha_1\pi$, … , $\alpha_n\pi$. Then any holomorphic map $g$ from $\mathbb D$ to $U$ is given by

$$g(z) = A+ C\int\limits^z_0 \prod\limits_{i=1}^n\left(1- \frac{\xi}{z_i}\right)^{\alpha_i-1} \mathrm d \xi$$

where $A$ and $C$ are complex constants, and $w_i = g(z_i)$ for $1\le i\le n$.

Above formula maybe looks simple to college kids that just finished Numerical Methods course, but the formula is just one of steps. First, points $z_i$ have to be found, which is done by solving a system of equations. Also, additional numerical methods (ike the Newton method) are needed for computing inverse of $g$. Fortunately, these days we have software packages that can do all this for us.

More about Schwarz–Christoffel mapping and its computation can be found in the book Schwarz–Christoffel Mapping (Driscoll and Trefethen, Cambridge University Press, 2002). One of the authors of this book is also the creator of the open-source MATLAB library sc-toolbox which is arguably the most comprehensive software package for working with SC mappings.

Maze solving

So, how does all of this help us solve a maze? The procedure is straightforward, assuming we know how to calculate Schwarz–Christoffel mapping and its inverse:

1. Let $U$ be the interior of the simply connected maze. Pick start and end points $A$ and $B$ in $U$ (marked below as red dots).
2. Find the Schwarz–Christoffel mapping $g\colon \mathbb D \to U$.
3. Find $g^{-1}(A)$ and $g^{-1}(B)$ (blue dots).
4. Since $g^{-1}(A)$ and $g^{-1}(B)$ are in the disc $\mathbb D$, we can join them by straight line $l$ while staying in the $\mathbb D$. This effectively solves the maze on its map.
5. Find $g[l]$, which is a continuous path from $A$ to $B$ and solution to the maze.

We didn’t need $f$ to be a holomorphic function, a homeomorphism (bijective continuous function with continuous inverse function) is enough. But, it is generally hard to construct homeomorphism, and SC formula give us relatively straightforward algorithm.

Is This Practically Possible?

For sufficiently simple mazes, it is possible. However, for more complex mazes (pun intended), a computer using 64-bit floating-point numbers would fail to produce a result.

How complex is complex? I am not sure, but the maze from the video would be solvable using this technique. However, a x10 larger maze would probably be too big for this method. The book mentioned above describes the challenges that arise with elongated sets (like mazes) and advanced methods for overcoming those challenges³.