17 ms·
Physicists have created the most fiendishly difficult maze
- russellbeattie 2y agoPart 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.
- smokel 2y ago10PRINTCHR$(INT(RND(1)+0.5)+109); 20GOTO10
- deleted 2y ago[deleted]
- ianbicking 2y agoKind 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.
- Someone 2y agoYou 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)
- tedunangst 2y agoThat doesn't do anything to assist solving, though. Once you're in the moat, it's the same problem.
- bee_rider 2y agoAlthough, 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.
- bee_rider 2y agoI 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.
- andrew_eu 2y agoSuper interesting question. 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. [1] https://archive.bridgesmathart.org/2001/bridges2001-213.pdf https://archive.bridgesmathart.org/2001/bridges2001-213.pdf
- bee_rider 2y agoAh, 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.
- IIAOPSW 2y agoYou 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.
- UI_at_80x24 2y agoWhen 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.
- deleted 2y ago[deleted]
- bee_rider 2y agoSlightly 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.
- UI_at_80x24 2y agoNope I checked. I was wrong a couple of times but it was rare.
- bee_rider 2y agoMaybe in an alternate life you are a real wizard at designing PCBs.
- ordu 2y ago> I wonder if it was a special gift I could have developed. Seems that you managed to train your neural networks to do a parallel search. Probably visual cortex neurons. GPU acceleration rocks.
- qup 2y agoI 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.
- leptons 2y agoI 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.
- bee_rider 2y agoSpeaking of burning men, how do maze organizers typically handle fire safety?
- leptons 2y agoFire extinguishers?
- anyfoo 2y agoI 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.
- klyrs 2y agoPanic
- bell-cot 2y agoUnless 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.
- ballenf 2y agoPart of the difficulty seems to be the style of jagged edges, making it hard to visually parse.
- hoseja 2y agoAnd then you see it's just an artefact of constructing the maze from connected triangles.
- croemer 2y agoTIL that one can say "very extremely rarely" in English > Quasicrystals are a form of matter only found very extremely rarely in nature.
- deleted 2y ago[deleted]
- its_ethan 2y agoJust 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. ;)
- IIAOPSW 2y agoMildly 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.
- ilikecakeandpie 2y agoI 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?
- reaperman 2y agoOnly 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.
- krapp 2y agoAlso 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.
- hoseja 2y agoWhy doesn't Sisyphos simply stop pushing the stone?
- anigbrowl 2y agoYou are in a maze of twisty little passages, all alike.
- deleted 2y ago[deleted]
- washedup 2y agoNo, thanks :)
- leni536 2y agoIt 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. [1] https://imgur.com/a/3paGJOk https://imgur.com/a/3paGJOk I discovered a somewhat similar fractal-maze when playing around with the dragon curve[2], maybe I should publish that. [2] https://en.wikipedia.org/wiki/Dragon_curve https://en.wikipedia.org/wiki/Dragon_curve
- jouless 2y agothe 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.
- leni536 2y agohuh, yes, that indeed looks like a much better maze.
- ChicagoDave 2y agoI 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.
- nvy 2y agoAll mazes are trivial if you adhere to the "keep one hand on the wall" trick.
- kazinator 2y agoYou can make easy mazes harder with extra distracting visual clutter: E.g. this: +-- -+----+----+----+----+ | | | | | | | | | +-- -+-- -+----+----+-- -+ | | | | | | | | | | +-- -+----+-- -+----+----+ | | | | | | | | | +-- -+----+-- -+-- -+-- -+ | | | | | | | | | | +-- -+-- -+-- -+----+----+ | | | | | | | | | | +----+----+----+----+ + Is just this, with extra wall material in each cell, reducing the aperture of the passages: + +----+----+----+----+ | | | | | | + + +----+----+ + | | | | | | | | + +----+ +----+----+ | | | | | | + +----+ + + + | | | | | | | | + + + +----+----+ | | | | | | | | +----+----+----+----+ +
- ssl-3 2y agoI solved the first one in my head in less time than it took for me to recognize that the second one was the same maze.
- deleted 2y ago[deleted]
- illiac786 2y agoSimply reading the words “is just this with extra wall material in each cell” is probably faster though.
- ssl-3 2y agoNo? 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.)
- tetris11 2y agoWhere is the code for generating these mazes? 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: https://github.com/joshcol9232/tiling https://github.com/joshcol9232/tiling