Is the Geometry/Topology of Mazes a thing?

[DaveC426913]

TL;DR Summary

Is there a mathematical subdiscipline of the study of mazes?

Some say you can escape a maze by placing your hand on one wall and tracing out the entire maze to escape.
But that only works if you manage to put your hand on an outside wall - a wall that is integral to the perimeter wall.
Some mazes have walls that are entirely interior - islands of walls. Put your hands on one of these and you will go around in a circle until/unless you realize you're retracing your steps.

My brother traversed a hedge maze the other day, and claimed he used the trick to find the exit, but I have my doubts it was a valid traversal.
He says he started at the single entrance/exit and traced his way all the way around to the same to escape.
I say, if a maze has a single entrance/exit, then the goal of solving such a maze is not to "find the exit", since that's literally trivial; the goal is (usually) to find the central courtyard (where the proverbial piece of cheese is waiting for the rat to find it).

Indeed, the maze solved has such a central courtyard:

And he would not have found it by placing his hand on an outside wall.

The above maze has quite a few "islands", and I have realized that that is equivalent to saying the maze has multiple routes.
An island is ... mazologically ... the same as saying there are two possible paths.

I have realized that you could instantly see what kind of maze you have if you could sort of use it as a mold - pour a fluid into it (like thick jell-O) that, when set, you can pick up out of the maze by its entrance and exit. All dead ends would hang down, leaving you holding a valid path from one end to the other. Multiple paths would manifest as closed loops; the "islands" being the voids within the loops.

I also digitized the maze

to make an estimate on how likely one could find the exit if dropped into the maze (in the dark) at a random location.

I decided every coordinate has no more than four meaningful directions one might choose (the four diagonals of every coord). A "4" indicates you are guaranteed to hit an outside wall, no matter which direction you move to find a wall. A "0" indicates you are guaranteed to hit an island.

By summing all diagonal moves that end up on an outside wall (206) - and dividing by the total possibilities (15x15*x4 = 900), I arrived at a solvability index for this maze of 22.9%. Thus, randomly dropped in, and then randomly picking a direction, you have a 22.9% chance of reaching the exit.

*you count the paths, not the hedges: a 16x16 hedge maze gets you 15x15 rows of paths
I am making all this up on my own (and possibly reinventing the wheel) because I have yet find the subdiscipline of math that defines this ... mazology. Suggestions?

 

[FactChecker]

Some mazes have walls that are entirely interior - islands of walls. Put your hands on one of these and you will go around in a circle until/unless you realize you're retracing your steps.

Doesn't that mean that there is no solution to escape from that location? In that case, the method works to tell you that there is no escape.

I have yet find the subdiscipline of math that defines this ... mazology. Suggestions?

Suppose the maze is represented by lines (edges) that represent direct connections in the maze between vertices which are the junctions of paths or terminal points, including a vertex for the exterior. Then it is a graph theory problem. There is a way to represent such connections in a matrix form. The matrix is called an adjacency matrix. It can be raised to powers, n, that represent n-step paths along the adjacency connections.
See, for instance, this youtube video.
Suppose the adjacency matrix is $A$, the initial vertex is I, and the outside vertex is J. If the (I,J) element of $A^n$ is non-zero, then there is an escape path of length n.

 

[DaveC426913]

Doesn't that mean that there is no solution to escape from that location? In that case, the method works to tell you that there is no escape.

Sorry, I was not clear: the trick is to put one hand on a chosen wall and never take it off that wall while you walk.

If a maze has zero "islands", that is the same as saying 'every wall is connected to the perimeter'*,
and all you have to do is follow the wall without taking your hand off it, and you are guaranteed to reach the exit.

*(it is also, incidentally, the same as saying 'this maze has no more than one path to the exit '**)
** though it is possible it might have zeroAnd yet, my point to my brother is that - were he dropped into the maze (one that has islands) at a random coordinate, and he attempted to use his trick - he may very likely not reach an exit ...

... unless he let's go of his wall to choose another wall (say, the opposite one). But even that is not guaranteed. He may just have latched onto another island. In a sufficiently large maze, he may never escape.

Suppose the maze is represented by lines (edges) that represent direct connections in the maze between vertices which are the junctions of paths or terminal points, including a vertex for the exterior. Then it is a graph theory problem. There is a way to represent such connections in a matrix form.

I suspected as much.

The matrix is called an adjacency matrix. It can be raised to powers, n, that represent n-step paths along the adjacency connections.

Yes, I am encountering them while reading about the Riemann Hypothesis, but I have never explored them, so I do not quite understand how they work.

See, for instance, this youtube video.
Suppose the adjacency matrix is $A$, the initial vertex is I, and the outside vertex is J. If the (I,J) element of $A^n$ is 1, then there is an escape path of length n.

I'll check it out.

 

[FactChecker]

I'll check it out.

The video I linked is misleading at time 0:42 when it concludes that $a_{AC} = 1$. That is not true in general for an adjacency matrix, which only =1 for direct, length 1 connections (although the example is bad because it actually has an A -> C edge.)
PS. I had to correct my original post to say $A^n$ is non-zero, rather than $A^n = 1$.

 

[DaveC426913]

The video I linked is misleading at time 0:42 when it concludes that $a_{AC} = 1$. That is not true in general for an adjacency matrix, which only =1 for direct, length 1 connections

I actually sort of wondered that myself, Glad to see my instincts are working.

Update: Nope. I'm lost by 0:53. No idea how A¹xA¹=A².

 

[FactChecker]

Suppose that $A$ is an NxN adjacency matrix, that the starting point is at vertex m and that the outside is at vertex n. Define the path matrix $P=A+A^2+A^3+A^4+...+A^N$. It should be clear that any two vertices that are connected by a path will be connected by a path of length N or less, since every vertex could be visited by then and it is never necessary for a shortest path to visit the same vertex twice. There is a path out if P(m,n) is nonzero.

 

[FactChecker]

I actually sort of wondered that myself, Glad to see my instincts are working.

Update: Nope. I'm lost by 0:53. No idea how A¹xA¹=A².

That is just how $A^2$ is defined. $A^2 = A$ x $A$

 

[DaveC426913]

... that the starting point is at vertex m and that the outside is at vertex n.

Nope. Lost. I would have to do some reading to even get past this.

That is just how $A^2$ is defined. $A^2 = A$ x $A$

Yes, but I don't even know how they get the numbers they got (e. where those 2's come from).This thread doesn't have to turn into a primer for Dave on matrices. If that is the math that does describe mazes, then I probably have some reading to do on my own. But I'm not sure that runs the gamut of analysis of my mazes. I'm not even sure I know how matrices would apply to a maze in a way that is useful to me.

 

[DaveC426913]

Ah, so someone has walked this road before me. This is exactly what I was envisioning:

BC is a dead-end and the graph shows it falling off the shortest path.
DEF is two paths on either side of an "island", and in the graph, it manifests as a closed loop.

 

[FactChecker]

Yes, but I don't even know how they get the numbers they got (e. where those 2's come from).
This thread doesn't have to turn into a primer for Dave on matrices. If that is the math that does describe mazes, then I probably have some reading to do on my own.

Yes, it's just matrix multiplication.

 

[FactChecker]

Ah, so someone has walked this road before me. This is exactly what I was envisioning:
View attachment 302757

BC is a dead-end and the graph shows it falling off the shortest path.
DEF is two paths on either side of an "island", and in the graph, it manifests as a closed loop.

It certainly is impressive how much simpler the graph is.

 

[DaveC426913]

An adjacency matrix has a diagonal of zeros. Unless there's a self loop. A self loop results in vertex n being 1 step away from itself, which shows as a 1 in the n:n cell of the matrix.

When they're symmetrical about that diagonal axis it's because they are undirected (so steps go both ways: a>b and b>a).

Yes? OK, I think I'm getting a glimpse.

But I think I have to start with examples of real world applications, like prices of pies or something.

 

[DaveC426913]

I see a real-world adjacent matrix here, with the dupes and trivials removed.
https://carolyndaut.com/2017/02/07/adjacency-matrix-decoded/
Is this the kind of example that might be operated upon with, say, multiplication?
I'm still looking for a better real-world example.

 

[jedishrfu]

As an aside, no discussion of mazes is complete without a reference to Labyrinth:

 

[DaveC426913]

Great film. Weirdly, it is the dress - near the end - that I will always remember.

I haven't brought up labyrinths because, technically, they are trivial.
Historically, a labyrinth has a single path and no dead-ends:

 

[FactChecker]

I see a real-world adjacent matrix here, with the dupes and trivials removed.
https://carolyndaut.com/2017/02/07/adjacency-matrix-decoded/
Is this the kind of example that might be operated upon with, say, multiplication?
I'm still looking for a better real-world example.

I don't think that is a good example. It has some vague definitions like "close to". A graph theory adjacency matrix is fairly straightforward. Each row represents a vertex and each column represents the same vertices in the same order. You just go across each row and place a 1 in each column where there is a direct connection (edge) to the vertex of that column. You can do normal matrix calculations with it and get some useful results. Large problems are not easy to solve manually and these adjacency matrices can automate the solving of large problems. You might not find small examples that are "real-world" because the examples are tiny. In the real world, it is usually easier to deal with small problems in other ways. But large problems are a different story.

 

[DaveC426913]

You might not find small examples that are "real-world" because the examples are tiny. In the real world, it is usually easier to deal with small problems in other ways. But large problems are a different story.

My maze example is relatively small, I think. Too small to make matrices useful? Is it possibly overkill?

 

[FactChecker]

My maze example is relatively small, I think. Too small to make matrices useful? Is it possibly overkill?

That's a good question. There might be a lot of vertices in that small example. I wonder how large the matrix would be and how well the approach of your post #9 would work.

PS. I realized that part of my post #2 was wrong. Following an interior wall may just lead in a circle. If that happens, try the other wall. In that case, is the other wall guaranteed to find a solution if there is one? I think that is true but I am not sure how to prove it.

 

[pbuk]

I remember an interesting chapter or two on mazes in the late Martin Gardner's excellent books - this and other references at https://mathworld.wolfram.com/Maze.html