Is the Geometry/Topology of Mazes a thing?

  • #1
DaveC426913
Gold Member
21,358
4,816
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:
1655076149732.png

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
1655077278329.png

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.
1655078904737.png


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?
 
Last edited:

Answers and Replies

  • #2
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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.
 
Last edited:
  • #3
DaveC426913
Gold Member
21,358
4,816
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 zero


And 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.
 
Last edited:
  • #4
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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##.
 
  • #5
DaveC426913
Gold Member
21,358
4,816
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 A1xA1=A2.
 
  • #6
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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.
 
  • Like
Likes DaveC426913
  • #7
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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 A1xA1=A2.
That is just how ##A^2## is defined. ##A^2 = A## x ##A##
 
  • #8
DaveC426913
Gold Member
21,358
4,816
... 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.
 
  • #9
DaveC426913
Gold Member
21,358
4,816
Ah, so someone has walked this road before me. This is exactly what I was envisioning:
1655084960954.png


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.

 
  • #10
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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.
 
  • #11
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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.
 
  • #12
DaveC426913
Gold Member
21,358
4,816
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.
 
Last edited:
  • #14
14,168
8,148
As an aside, no discussion of mazes is complete without a reference to Labyrinth:

 
  • Like
Likes DaveC426913
  • #15
DaveC426913
Gold Member
21,358
4,816
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:

1655090690846.png
 
  • #16
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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.
 
  • #17
DaveC426913
Gold Member
21,358
4,816
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?
 
  • #18
FactChecker
Science Advisor
Homework Helper
Gold Member
7,581
3,311
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.
 
  • #19
pbuk
Science Advisor
Homework Helper
Gold Member
4,026
2,360
  • Like
Likes FactChecker

Suggested for: Is the Geometry/Topology of Mazes a thing?

Replies
38
Views
1K
Replies
1
Views
542
  • Last Post
Replies
2
Views
525
  • Last Post
Replies
1
Views
475
Replies
1
Views
341
Replies
10
Views
680
  • Last Post
Replies
8
Views
320
Replies
7
Views
683
Replies
8
Views
721
Top