Is the Geometry/Topology of Mazes a thing?

  • B
  • Thread starter DaveC426913
  • Start date
In summary, the conversation discusses various methods for escaping a maze, including the trick of placing one's hand on a wall and following it to the exit. However, this only works if the maze has an outside wall that is integral to the perimeter, and not all mazes have this. Some mazes have interior walls that create "islands", making it difficult to escape without retracing one's steps. The conversation also mentions using graph theory and adjacency matrices to analyze and solve mazes.
  • #1
DaveC426913
Gold Member
22,473
6,141
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:
  • Like
Likes mfb
Mathematics news on Phys.org
  • #2
DaveC426913 said:
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.
DaveC426913 said:
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
FactChecker said:
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.

FactChecker said:
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.

FactChecker said:
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.

FactChecker said:
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
DaveC426913 said:
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
FactChecker said:
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
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
DaveC426913 said:
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
FactChecker said:
... 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.

FactChecker said:
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
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
DaveC426913 said:
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
DaveC426913 said:
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
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:
  • #13
  • #14
As an aside, no discussion of mazes is complete without a reference to Labyrinth:

 
  • Like
Likes DaveC426913
  • #15
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
DaveC426913 said:
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
FactChecker said:
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
DaveC426913 said:
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
  • Like
Likes FactChecker

1. What is the difference between geometry and topology when it comes to mazes?

Geometry refers to the physical shape and dimensions of an object, while topology is concerned with the properties that are preserved when an object is stretched or deformed. In the context of mazes, geometry would refer to the physical layout of the walls and corridors, while topology would focus on the connectivity and paths within the maze.

2. Can the geometry or topology of a maze affect the difficulty of solving it?

Yes, the geometry and topology of a maze can greatly impact its level of difficulty. A maze with a more complex geometry, such as multiple levels or overlapping pathways, can be more challenging to navigate. Similarly, a maze with a more intricate topology, such as dead ends or loops, can also make it harder to solve.

3. How do mathematicians use geometry and topology to study mazes?

Mathematicians use various tools and techniques from geometry and topology to analyze and classify different types of mazes. For example, they may use graph theory to study the connectivity of a maze, or use topological methods to determine the number of possible paths within a maze.

4. Are there any real-world applications for studying the geometry and topology of mazes?

Yes, there are several real-world applications for studying mazes from a geometric and topological perspective. For example, understanding the structure of mazes can help in designing more efficient transportation networks or optimizing the layout of buildings. It can also have applications in computer science and game design.

5. Can the geometry and topology of mazes be used to create new types of puzzles or games?

Absolutely! The study of mazes from a geometric and topological standpoint has led to the creation of various puzzles and games, such as Rubik's Cubes and the popular video game "Minecraft". By manipulating the geometry and topology of a maze, new and challenging puzzles and games can be created.

Similar threads

Replies
32
Views
889
Replies
9
Views
2K
Replies
3
Views
1K
  • Sci-Fi Writing and World Building
Replies
10
Views
1K
Replies
8
Views
1K
Replies
16
Views
837
  • General Engineering
Replies
4
Views
2K
Replies
10
Views
938
Replies
3
Views
2K
  • Mechanics
Replies
10
Views
1K
Back
Top