Mildly off topic, but I sometimes re-imagine the myth of the Minotaur as a parable about how the only bars which can't be bent by brute force are the ones made of computational hardness.
Why did they build a maze for the Minotaur with a possible escape route rather than just an ordinary prison? Why leave the possibility of escape open?
Well see, the Minotaur was arbitrarily strong. No material could build a wall strong enough that he couldn't bash through nor a door that he couldn't break down. But, he wouldn't try and break down anything if there was obviously a path right there he could use to go around it normally. By putting him in a maze, he will always keep trying the next path thinking it might be the exit, never attempting to break any wall. The puzzle is harder than any material they could have used to build a prison, as it cannot be bent by the Minotaurs brute force.
Computation (eg cryptography) can be "unbreakable" in a way that bank vaults and deposit boxes can't.
>Why did they build a maze for the Minotaur with a possible escape route rather than just an ordinary prison? Why leave the possibility of escape open?
Because it was not a maze, the Minotaur lived in the center of a labyrinth. A labyrinth is a continuous path that leads to the center. The objective was to send people into it so they would end up in the Minotaur's lair and be devoured. The reason the monster stayed was that he had everything he needed there, especially food.
That's a really interesting distinction between the words, but sources from Wikipedia indicate that the minotaur was trapped in a maze:
> Although early Cretan coins occasionally exhibit branching (multicursal) patterns, the single-path (unicursal) seven-course "Classical" design without branching or dead ends became associated with the Labyrinth on coins as early as 430 BC, and similar non-branching patterns became widely used as visual representations of the Labyrinth – even though both logic and literary descriptions make it clear that the Minotaur was trapped in a complex branching maze.
The ancient textual and pictorial tradition are in contradiction to each other here, which probably cannot be resolved. Ariadne's thread suggests a branching labyrinth, but in ancient pictures we actually only find unicursal labyrinths.
Maybe they just found it hard to draw a branching labyrinth? It’s easy for us with Wikipedia and all, but if you’d potentially never seen a branching labyrinth then a non-branching labyrinth is a lot easier to draw.
It’s especially hard for modern people to conceive of a world before the printing press where information wasn’t easy accessible.
The challenge may have also been artistic. I don’t know if those artists would have been up for a branching labyrinth. I have seen how medievals
drew cats and they do not look right.
They overlap in meaning to the extent that I would use either interpretation for either word. For instance in England there are chalk figures called miz-mazes (https://en.wikipedia.org/wiki/Mizmaze) which are non-branching.
Ok, but surely if there are no branches, but only a single path, there would be no way to get lost? The only way would be if you forgot which direction you were facing?
You could have side-paths that quickly go nowhere, but without any hints as to which ones do or don't. That way, backtracking towards the main path is pretty trivial and leads to a constant forward progression.
I like mazes and I saw that distinction be made before, but I am not sure how universally accepted it is? Other than English how many languages even have two different words? I spent some time now on Google Translate and the only language I find (not that I tried ALL) is Finnish. Modern Greek for instance uses the same word (assuming Google is correct), so did people on Crete, whatever their language was, even have two different words?
But Google Translate is correct about Dutch. It was just not one of the languages I tried before. I do not think it is a particularly difficult case for translation.
The reason I checked was in my native Swedish there is only one word (labyrint).
Was it really always two different things even in English? I looked the words up in Gutenberg's public domain Webster's Unabridged Dictionary (1890?) a labyrinth there was "an ornamental maze" ... "Labyrinth, originally; the name of an edifice or excavation, carries the idea of design, and construction in a
permanent form, while maze is used of anything confused or confusing,
whether fixed or shifting. We speak of the labyrinth of the ear, or of the
mind, and of a labyrinth of difficulties; but of the mazes of the
dance, the mazes of political intrigue, or of the mind being in a
maze." And from the definition of maze: "A confusing and baffling network, as of paths or passages; an intricacy; a labyrinth". Did the meaning drift a bit since then or was it only in mathematics that the words began to be used in the way that they are often used now for branching vs non-branching mazes?
In common use the terms are interchangeable. Differentiating between them is essentially jargon, but it's not wrong. Inflamable famously means something is both flammable and not flammable depending on who you ask. Words not only have multiple definitions, they sometimes have multiple incompatible definitions.
I don't think you're right. I won't pretend to be an expert on any of this, but as a speaker of modern Greek I can confidently say that λαβύρινθος (labyrinth) is the only word in Greek to describe both your definition of a labyrinth and a maze.
For example, this Wikipedia article[1] on labyrinth in Greek, which has the picture [2] of a maze and calls it a labyrinth.
It’s kind of hard to describe why we feel this is so irrefutable, but one of my favorite thought exercises is doing exactly that.
My algorithms prof once took us on a fun journey describing the median-of-medians variation of the SELECT algorithm, and had us play around with different partition sizes to see its effect on asymptotic running time. Turns out if you choose any other value than 5, you get superlinear running time.
This is probably the most random display of fatuousness I’ve encountered from mathematics. There should be absolutely no reason the number 5 - not 3, not 4 - has anything to do with recursively selecting a median, and yet here we are.
It makes me wonder. Maybe there are computational rules similar to gravity or conservation of energy, but similar to physical machines, there seem to be computational ones that can be built defy them.
You're asking one of the questions that was an early skepticism of quantum computing. Namely, until very recently there was a line of thought that while you could draw machines on paper which break certain computational limits by leveraging quantum mechanics (or other physics), just like with perpetual motion machines before them, all of these designs would be doomed to fail because they would violate a fundamental principle to how the universe works. In other, the line of thought was exactly like you said, that computational rules were similar to gravity or energy conservation and thus couldn't really be broken.
Presently this line of thought is dead because quantum computers have demonstrated doing something that can't be done classically. So we know there's no theoretical reason not to have a quantum computer. But the thought that the laws of the universe might be underpinned by computation is still very much alive. Its just all qubits at the bottom rather than classical bits.
There's a cliche in the field. "Information is physical". Roughly it means, information only exists encoded on some form of physical medium, and all physical systems are reducible to the information encoded as the state. Physical things are information, information is a physical thing. Information is physical.
It ain't cryptography, though, it's just a a shortest path algorithm on a graph, which has wide and obvious applications for trade networks. Most computational problems we consider now were outside the scope of the easily expressible terms at hand.
This is a great observation! I just hesitate to romanticize the applicability of modern concepts to classical situations.
This is really cool! I just don't think this implies a sense of general computation as opposed to puzzle-solving. I think there's a crucial difference here. There's just a lot of computational understanding that only comes up when you introduce combinatorics generally out of reach of casual classical conversation.
I know it's a myth, but what would stop the Minotaur from just going full Juggernaut and smashing through all the walls should the Minotaur realize the paths are too difficult to traverse?
Only the mythical head-canon of the Minotaur’s psychology. Whereas I tended to believe that the Minotaur had everything it wanted to a reasonable degree of comfort as long as it continued to be fed.
Also the Minotaur just might not be strong enough, depending on what the labyrinth is made of, given that its purpose in the myth is to keep the Minotaur trapped. He's half man, half bull, which makes him a lot stronger than a human but AFAIK bulls can't just bust through stone walls.
I think with a good sense of smell he would find the exit too easily, but you're on to something here: perhaps the Minotaur would suspect there's no entrance had there been no occasional human entering the labyrinth from time to time!
I think with a good sense of smell he would find the exit too easily
I thought about this as well, after my first remark. I think this issue could be solved by building a secondary labyrinth of ventilation ducts to channel the fresh air into the dead ends, in a way that entices the Minotaur in very confusing ways. The ducts could even have baffles that open and close, just like real ventilation systems in houses with zone-control airflow.
The ventilation ducts could also work to confuse and terrify any humans who were sent into the labyrinth. They’d carry sounds allowing the human to hear the heavy breathing and bellowing of the Minotaur in ways that make it sound like he’s always just around the corner!
Hades has total control over the (physical) rules of the underworld[1]. Hades can make the stone roll back for arbitrary reasons. But keeping hope alive in Sisyphus is the harder problem. Hades can essentially force Sisyphus to keep trying by making it arbitrarily painful to stop trying, but then hope is no longer his motivation. Hades could reset Sisyphus' memory such that hope remains, but then this loses the profundity of an eternal punishment.
The more interesting case is that Sisyphus can contemplate the nature of the system, and reason toward an out that involved undermining Hades power over the Underworld. If he could pause and do experiments, discover the limits of the enchantment, and work around them, that would be ideal. However such an option would also be an excellent way for Hades to extend and deepen the severity of the punishment. A god's arbitrary power is arbitrarily powerful, after all.
This might be an allegory for a mind looking for an exit from the maze of increasingly complex thoughts, and eventually falling into the hands of madness.
The first solution was immediately plain. I did not think about it. I did not read about it. I just looked at it because my eyes were drawn to it, and and the solution was simply present for me.
I did think about the second one (the allegedly-simpler one) for a very brief moment.
And then, I read the words.
But it took me longer to read and parse "is just this with extra wall material in each cell" than either of those two maze-interpretation events consumed.
(I do not think that I am a particularly slow reader.)
It seems cognitively unusual to be faster at subitizing, so to speak, the path through the maze in which the cell exits are camouflaged, than the plain maze. It would have to be confirmed by proper experiment, with the subject is shown a decent number of mazes of both types, and hits a key as soon as they see the path (plus whatever refinement are deemed appropriate by experimenters experienced in this area).
Yep, just came here to say this. I was going to run their maze through a photoshop filter to remove the extra garbage to see what difference it makes. (but eh, we know it would)
Kind of an aside to the purpose of the maze, but I noticed their maze has no designated exit. You just have to escape the maze from an interior starting point, adding to the challenge because there are many false exits. You can't start from both ends, nor is there a sense that you are getting "closer" to the exit.
I don't think I've seen this maze building technique, even though it seems simple.
You can turn any such maze into one with a single exit by surrounding it with a small “moat” with a single exit. For large mazes, I don’t think the price you pay for it is too large, as it only adds O(\√#cells) of area to the maze, and I think any good measure for complexity of a maze scales by #cells (if you don’t scale by #cells, you can make a maze harder by glueing multiple ones together, and the trivial maze where there only one straight line will get harder by making it longer)
Although, it still seems like a slightly different type of maze somehow. You could have many different long paths that go all the way out to your moat. Not that this is an illegitimate type of maze or anything, it is just slightly unusual.
I suspect the bit about the maze difficulty is just some throwaway bit of description that the journalist got caught up on.
But does anyone know a good metric for maze difficulty? Or what the study of maze difficult would really look like? The classic maze solving algorithm (right hand rule/DFS) is deterministic anyway.
I didn't, but found this [1] 2001 paper without much difficulty. Getting much out of it is more difficult. As I understand it, the complexity measure they propose is somewhat related to the difference of arctans of turns to take "forward" vs turns to take "backward", summed up for every fork and scaled with some length measurement. There are definitely plenty of other complexity measure though (e.g. number of forks, number of incorrect paths, etc) -- correlating that to practical difficulty is less straightforward.
Ah, I’m glad that somebody at least tried to come up with a measure that sort of… matches the human eyeball intuition of what a difficult maze is, even if it is mathematically a bit funky.
Micromouse is primarily a robotics competition but they care about their algorithms greatly. It's a rectilinear maze and concerned about turning accuracy and acceleration etc, but there should be plenty of more abstract stuff in that space about most effective maze solving algorithms.
> But does anyone know a good metric for maze difficulty?
I think there are a bunch of problem-definition details that would need to be hammered out first, ex:
1. Is this solving the maze with perfect knowledge of its layout--a bird's eye view from above--or does it require gradual exploration to fill out the contours?
2. If it requires exploration, how far can you see? Do you need to actually spend a move to enter a square to know whether it is a dead end, or can you tell from N squares away? Is the viewer constrained by trigonometry, where they can only uncover partial knowledge about nearby rooms and small geometric quirks can have a big effect on exploration progress? Is there a distance limit to vision?
3. If it requires exploration, is there a cost to backtracking, or--like DFS--can you simply teleport between all places you've already been without a cost?
4. Is a "difficulty" rating across mazes based on a single algorithm, or the best-possible choice for that particular maze from a set, or does it represent the average expected effort expended by a particular population of different people/algorithms?
Right; I didn’t do any of that because I’m more curious if somebody has already done it. Generally with CS stuff I find there’s somebody who’s already poked around the maze a bit and found a neat path to explore. :)
Well, usually we measure the difficulty of a problem by the run-time complexity of a solution to the problem. If the approach is deterministic, we'd usually care for the complexity of the best solution for the worst-case kind of problem; but it could as well be an expected run-time for a probabilistic approach.
Interestingly, you don't always actually have to _have_ an actual solution - it can be possible to determine run-time bounds (that tell you how hard your problem is at least) just on theoretical grounds. This could be, e.g., by comparing it in complexity to another problem that has already been studied and whose complexity is thus known.
That’s algorithmic complexity/“difficulty”, and somewhat assumes that we only care about computers solving the maze.
Since solving mazes is however (also) something to be enjoyed by humans, it’s possible that perceived maze difficulty could be dependent on factors that wouldn’t really matter for a straightforward algorithm. For example, a very “jagged” maze could feel more difficult for humans because it’s harder to follow with your gaze, while an optimal maze solution finding algorithm wouldn’t be impacted.
In cases like this, formulating difficulty can be more of an art than an optimization problem.
EDIT: See also andrew_eu’s reply (which I only saw now), where multiple “interesting” notions of “difficulty” are proposed.
EDIT: Relatedly, humans use heuristics a lot. And there are many NP-hard problems where we can solve lots of “reasonable” points in the problem space in reasonable time (computers or humans alike), at the risk of having to time out, maybe try with another approach, and eventually just give up. Traveling salesmen are actually traveling the country after all. So worst case is not always a good measure for games. But I see you mentioned that already.
One rather significant yet under appreciated difference between human and computer path finding in general is that humans cannot BFS. The closest we can get is a sort of modified beam search. But there always will be a latency added when switching heads that computers simply do not have (módulo generally insignificant cache stuff, perhaps)
This has significant implications to search spaces that are very heavily branched with many deep dead ends but a relatively shallow goal.
The number of problems in general life matching that description is… huge.
You said yourself the algorithm is DFS. The obvious measure of difficult then is going to be the average number of branches b raised to the average depth d of the tree.
This is just another way of saying the size of the search space is (b^d), and DFS "walks the tree" until it finds the exit, which means on average its going to iterate half the entire search space before getting there. Furthermore, unless there is some other information available which correlates with the correct path at a given intersection, there's no possible way to do better than testing the possible branches sequentially (as in DFS) and therefore no way to improve on searching half the entire space.
You’re formulating the problem with a lot of implicit assumptions. That is ignoring a lot about how human visual perception works.
Look at a very simple maze, you will likely “intuitively” solve it immediately without performing an actual DFS. Implementing that as an actual computer algorithm would be insane since your algorithm would now rely on the computational needs of a human perception system, which decreases algorithmic efficiency by many orders of magnitude. But humans with their weird squishy brains have what they already have, and on the flip side are simply not optimized for algorithms on all but the smallest data structures. (You can very easily read even distorted text, but you have an extremely hard time balancing a simple red-black-tree in your head or even on paper.)
EDIT: Relatedly, humans use heuristics a lot. And there are many NP-hard problems where we can solve lots of “reasonable” points in the problem space in reasonable time (computers or humans alike), at the risk of having to time out, maybe try with another approach, and eventually just give up. Traveling salesmen are actually traveling the country after all. So worst case is not always a good measure for games.
Well now you're posing a different problem, namely one about mazes where the entire structure is visible at once from the top down and (likely) follows certain drawing conventions. This violates my caveat about there not being any information at the intersections which correlated with which branch to look at next. If you can see the whole maze at once, you very much have a hint.
Right; DFS is the solution to this one type of well-covered maze problem. But I think it is less interesting. I guess what I was trying to ask is, if there are other more interesting problem/solution pairs that could allow for more interesting types of difficulty.
I made the mistake of walking into a maze at Burning Man, and as I was walking in there were people begging us if we had seen the entrance recently. I didn't think much of it, until I understood just how "fiendishly" designed the maze was. It wasn't very large, maybe 150 foot square, 8 foot tall plywood sheets, so you couldn't just climb out. At the center of the maze was a ladder you would climb up to a platform where you could see the whole maze except the part under the 20 foot square platform you were standing on. And that was the tricky part. It seemed that when you went through the center part of the maze you would end up in an unexpected part of the maze, and even though we could see the maze from above, none of it made any sense to how we might get out. It took us about 30 minutes to get to the platform and another hour to get out. I will never go into another maze again.
Do you remember which year that was? I'm fairly sure I encountered that project, and I think I found some way to cheat my way out of it without actually solving the maze, though I can't recall the details.
Very true! I was here [1] a few weeks ago. I'd never done a real-life maze before and assumed it would be easy but with free-standing walls it was quite challenging. I think I explored every branch before reaching the centre.
With some discreet scratches on the plywood, a "mostly just follow the right-hand wall" rule works.*
Think of each free-standing section of wall as a node in a graph. The graph's edges connect free-standing wall sections which are adjacent. The task is to find (and circumnavigate) all the graph's nodes.
Yes, it could be very tedious to search this alternative representation of the maze for the exit node. Far more likely not - the description was "maybe 150 foot square", not "multi-acre corn maze".
*Assuming a two-dimensional maze, a finite number of free-standing wall sections, flat spacetime, and non-zero lower bound on the width of the maze's paths.
that's the way to go. one time got "lost" in a corn maze about 2/3rd way thru, going in circles, so just finally hopped a row, and followed the path out 30 seconds later. it's supposed to be fun, not stressful.
Unless someone is splashing gasoline around, fire will spread very slowly in an open-topped plywood maze. And heat/fumes/smoke will head skyward, not accumulate as they would for an indoor fire.
As an organizer, I'd be much more concerned about medical emergencies and inter-personal crime in the maze.
I don't know anything about mazers (or fire safety), but, assuming flammable materials like wood, how do they extinguish the fire before it takes over the whole structure?
I guess "professional" mazes may have sprinkler systems. Still, it seems that even in buildings that do, a lot of value is put into maintaining escape routes.
Outdoors, I guess you could use direction of sun as a guiding beacon, to decrease the confusion of which way you're pointed. 8ft tall walls in a desert will hide other landmarks I assume.
It looks like that only a small part of the actual maze is reachable from the starting point, which surely reduces the complexity somewhat[1]. But maybe the cutoff for the perimeter in the picture is not at the ideal point to show off the complexity.
the cycle has an inside and an outside, so only half of it is reachable. you could draw it with fat lines to remove the ambiguity. as you showed in your image though, you can get to most of the accessible parts only after you've escaped the maze. to make it a proper maze with one entrance and one exit you'd want to use the interior of the cycle as the maze and cut entrance and exit points, maybe the exit being at the farthest flood fill distance from the entrance.
When I was a kid I was really good at mazes. I would just stare at the maze, kinda zone out for a minute unfocusing on the entire thing, and eventually one path would look brighter to me somehow. I could never solve a maze by tracing my finger along a route, but if I 'un-focused' it would jump out of the page at me.
My mother has told me I would have them done within seconds, and I'd have a whole book before she'd finish putting the groceries away.
I've never thought much about it other then, 'I used to like doing mazes'; but I wonder if it was a special gift I could have developed.
Slightly silly question—did you actually check the validity of your solutions? It would be extremely funny, and certainly the type of thing I would have done as a kid, to just assume the path I’d found was the right one, haha.
I'd just relax and de-focus for a moment, keeping my eyes on a printed maze but not really looking at it. To me, the path never really looked any different visually -- it was just clearly and distinctly evident in ways that I cannot properly articulate.
Once the path revealed itself through no particular effort on my part, I could trace it out with a pencil or a crayon or whatever.
I could do this trace by starting from random points in the middle, drawing lines towards the outside, or start at one end or the other. It didn't really make a difference to me where I started the trace. To me, I was just tracing parts of a path that I knew to be correct -- it didn't matter at all to me what order I drew them in.
It was a rather unpopular trick. Other kids were sure that I was cheating (as if I had a catalog of solutions to all of the world's mazes in my head or something) or showing off (they may have been right about this last part).
Adults would proclaim (rather insistently) I must be doing it wrong somehow despite consistently and confidently, if unconventionally, arriving at the correct answer on the first try. They tended to make it very clear that they were unappreciative of this departure from normalcy.
I had a middle school friend who was a great artist, but also he drew mazes. "Brain mazes" he called them, because of the noodly look.
Anyway, I always wondered how he could do it. To me he was just drawing lines everywhere, but there would eventually be a complete maze with only one solution.
Maybe it was a memorized algo--like a party trick basically.
That's a fun name. I used to draw sort of noodly-ish mazes as a kid, too, though they didn't always have a unique path as there could be branch loops. Did they look at all like this 7 minute mouse drawing version? https://imgur.com/a/lat8S6N There's no fancy process to it, though. I can picture a much more impressive maze deserving of the "brain maze" name.
Just because you can say it, doesn't mean you should... that's a pretty clunky sentence in my opinion. Then again, it will only occur very extremely rarely in writing, so maybe it's OK.
The closest I've found is a paper they reference for generating arbitrary rhombic tilings in arbitrary numbers of dimensions, based on the de Bruijn grid method:
Part of me wants to write up a quick path finder script to do the maze to see how long it would take. The solution seems like a straight line though, so it could get lucky and zip to the middle.
I used to draw mazes as an artistic hobby. My mazes are way harder than any of these generated garbage piles. There are expert maze artists that also make vastly better mazes than this.
Why did they build a maze for the Minotaur with a possible escape route rather than just an ordinary prison? Why leave the possibility of escape open?
Well see, the Minotaur was arbitrarily strong. No material could build a wall strong enough that he couldn't bash through nor a door that he couldn't break down. But, he wouldn't try and break down anything if there was obviously a path right there he could use to go around it normally. By putting him in a maze, he will always keep trying the next path thinking it might be the exit, never attempting to break any wall. The puzzle is harder than any material they could have used to build a prison, as it cannot be bent by the Minotaurs brute force.
Computation (eg cryptography) can be "unbreakable" in a way that bank vaults and deposit boxes can't.