[HN Gopher] Can water solve a maze? [video]
___________________________________________________________________
Can water solve a maze? [video]
Author : gronky_
Score : 323 points
Date : 2023-04-01 15:40 UTC (2 days ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| jjbinx007 wrote:
| I've often wondered, is this vaguely analogous to the quantum
| wave function and what's happening when particles try all
| possible paths?
| _Nat_ wrote:
| Related links:
|
| https://en.wikipedia.org/wiki/Pilot_wave_theory
|
| https://en.wikipedia.org/wiki/De_Broglie%E2%80%93Bohm_theory
|
| https://en.wikipedia.org/wiki/Hydrodynamic_quantum_analogs
| jjbinx007 wrote:
| Thank you
| grupthink wrote:
| A computer is a computer, and our universe is a computer. So,
| it's possible we're living in a simulation but not one that was
| intentionally constructed by a higher life form, but rather, a
| simulation that emerged from nature (e.g. electrons whizzing
| along the surface of silica rock on a desolate planet). Our
| universe could recursively be computers all the way down.
| AltruisticGapHN wrote:
| The simulation theory simply postpones the hard problem of
| consciousness. It's like a magician trick, pulling wool over
| the eyes, moving your attention away from the real problem long
| enough, so that you stop thinking about it.
| User23 wrote:
| The simulation theory is literally a species of creationism,
| which I find quite amusing.
| munchbunny wrote:
| How so? By "hard problem" do you mean defining what
| consciousness is?
| quickthrower2 wrote:
| Even without consciousness, the existence of the universe
| faces the same causality issues.
| docandrew wrote:
| All the talk of simulations, multiverses, etc is IMO
| expending a lot of effort to avoid facing the possibility
| of a Creator - the "uncaused cause" or something existing
| outside of time and space.
| programmer_dude wrote:
| The presence of a creator does not change anything. Who
| created the creator?
| docandrew wrote:
| That's the point - something completely beyond our
| notions of causality or the arrow of time has to be at
| the foundation of it.
| NayamAmarshe wrote:
| The creator remains without a creation. The notion that
| most schools of thought have is, the creator is unborn
| and born at the same time and has always existed. Creator
| does not have a point of creation, not even death because
| those rules only apply to the materialistic universe.
| programmer_dude wrote:
| That's quite a cop out. Excuse me if I don't take your
| word for it.
| EventH- wrote:
| It isn't a cop out because the creator in the conclusion
| of this type of argument (e.g. Aquinas' third way) is not
| just another contingent being like other things, but
| rather a being whose existence is necessary in itself.
| bryanrasmussen wrote:
| >it's possible we're living in a simulation but not one that
| was intentionally constructed by a higher life form,
|
| what about a simulation constructed by us. the conceit of The
| Invisibles comics.
| NayamAmarshe wrote:
| A computer is always imperfect though, compared to the
| universe, which is very stable and extremely perfect to the
| last detail. I don't think we can even compare since the scale
| and the domain is so vast.
| codetrotter wrote:
| If a tree is standing in a forest, but no one is there to
| watch it. Does the tree get rendered every frame?
| ndsipa_pomu wrote:
| No, it doesn't.
| NayamAmarshe wrote:
| Depends on the programmer.
| yazaddaruvala wrote:
| Depends on the hardware being targeted.
| polishdude20 wrote:
| Depends on the deadline
| archerx wrote:
| Yes, it does.
| archerx wrote:
| If it is a simulation, what is it simulating? There would have
| to be a "real" reference to compare against?
| jasamer wrote:
| I don't think a simulation needs to simulate anything real.
| Eg. if I have a program that runs Conway's game of life, that
| would be also be a simulation, but there's nothing "real" it
| references against.
|
| In other words, the universe simulating ours might work
| completely differently, and some beings there are just
| testing how different laws of physics (i.e. ours) work out.
| archerx wrote:
| The definition of simulation is:
|
| imitation of a situation or process. "simulation of blood
| flowing through arteries and veins"
|
| I love the game of life but I don't really consider it a
| simulation, it's a toy that with the right parameters could
| simulate something.
| wruza wrote:
| _some beings there are just testing how different laws of
| physics (i.e. ours) work out_
|
| Or there is a practical use like energy extraction. Or they
| live (if that even applies) in a universe that generates
| what our closest concepts of are e.g. time and energy, and
| they have to spend them massively in simulations to
| survive. Or their laws of nature tend to overcommunicate
| (dilute) them into a single being, so they simulate
| everything we see for islands of "themselves" to remain
| distinct. They split themselves endlessly with perception
| because that's the trick in their situation.
|
| One of my nightmares is to wake up from this and realize
| you woken up from a mild depression into a horror of a true
| existence, and this isn't even a final level. Makes sense,
| since if god is infinite, why shouldn't he be infinitely
| suffering. Why would he (you) create all this if not to
| escape from null-reality.
| zamadatix wrote:
| If I launch a random cellular automaton there isn't as much a
| real reference I'm trying to compare it to as just seeing
| what cool things it does. Maybe I can coax it into something
| comparable if I want, e.g. pick rule 110 and set it up to run
| ChatGPT and write this comment, but the only "realness"
| requirement is it follow what logic allows not it has a real
| reference it's supposed to emulate and be compared to.
| archerx wrote:
| I wouldn't call that a simulation though, it's just a
| looping process with rules. A simulation implies imitation,
| so if it's not imitating anything is it a simulation?
| grupthink wrote:
| It would be simulating causality. If you had a water maze
| that was large enough - with enough gates, switches, and
| circuits - then it would be turing complete and simulate
| its own universe. But the more likely scenario is that it
| doesn't compile into anything. The point is, given enough
| time, and space (it's going to be one large maze) it's
| capable of applying the same rules of causality, and
| calculating the same math across all universes. That
| said, if your quarks and neutrinos blip in and out of
| existence, you can blame it on the turbulent water
| maze(s) higher in our simulation stack. :)
| quickthrower2 wrote:
| Factorio running inside minecraft running inside roblox.
| archerx wrote:
| Turtles all the way down...
| DavidPiper wrote:
| > [2:39] ... Actually a maze becomes very easy to solve if you
| colour the two parts separately.
|
| Breezing through that example like he didn't just blow my mind,
| wow. It makes so much intuitive sense.
| lupire wrote:
| Unless you are the maze constructor, coloring the maze pieces
| is at least as hard as solving it.
| hinkley wrote:
| If you color it the way he describes solving the maze (by
| keeping one hand on the wall the whole time), then solving it
| and coloring it should be the same operation, yes? Because if
| you haven't touched part of that wall yet, then you aren't at
| the exit. And anything you haven't touched is part of a
| different piece.
| [deleted]
| dukeofdoom wrote:
| can this work with light? how would it be different. just trying
| to imagine a light solving a maze
| CyberDildonics wrote:
| Light goes in a straight line an reflects. If the walls are
| diffuse, a tiny amount of light is always going to make it out
| at some point, but what does that have to do with this?
| JumpCrisscross wrote:
| Now do it with a superfluid [1].
|
| [1] https://en.m.wikipedia.org/wiki/Superfluidity
| bilsbie wrote:
| Not sure if mazes are np complete but if so could we map other
| problems into maze designs and the water can solve problems for
| us?
| patates wrote:
| If you extend the definition of the maze a bit, aren't all
| circuits mazes?
|
| But then, you can keep extending it and say that _everything_
| is a computer and also a maze.
|
| Anyway, the brain gymnastics is a lot of fun, at least for me.
| xmcqdpt2 wrote:
| They are not NP at all. A perfect maze (with one solution) as a
| connectivity graph is a tree. Finding the path through a tree
| can be done by DFS in linear O(N) time.
| brokensegue wrote:
| all P problems are in NP \pedantic
| thih9 wrote:
| I thought we decided to use electricity and silicon mazes
| instead?
|
| But there were attempts to use water too, e.g. MONIAC:
| https://en.m.wikipedia.org/wiki/MONIAC
| agilob wrote:
| Would this work as well if the maze had horizontal path instead
| vertical, when gravity and bottom-up air pressure wouldn't be
| helping the water find the path? I think it would look more like
| the one from Bergman Joe.
| [deleted]
| noobcoder wrote:
| You should check how bacterias navigate through mazes. They can
| navigate through complex environments (chemotaxis and swarming).
| Bacteria can sense gradients of chemicals and adjust their
| movements accordingly to find the optimal path through a maze.
| The ability of bacteria to communicate and coordinate their
| movements to solve more complex mazes is hella impressive.
| agilob wrote:
| Sounds like more known name for it is "ant colony
| optimisation". Lots of computer science algorithms and
| structures are based on that principle
|
| https://en.wikipedia.org/wiki/Ant_colony_optimization_algori...
| Darky wrote:
| Simple video, yet fascinating
| ulucs wrote:
| So it's basically A* with higher scores when going towards
| gravity, very cool.
|
| Another physics problem analogue I really like is the problem of
| fastest travel from point A to point B when you have to cross a
| river. One approach to solve is is to treat it as a minimization
| problem by writing down everything, another one is to realize
| light beams have already solved this problem for you, and the
| problem becomes much simpler when your river entry angle a and
| swimming angle b have to satisfy (sin a)/v_walking = (sin
| b)/v_swimming and the fastest path is the one which just happens
| to satisfy this angle constraint
| PartiallyTyped wrote:
| Assuming the heuristic follows triangle inequality, then it is
| A*.
| lazyant wrote:
| animals like ants and dogs intuitively "solve" the equation too
| scarmig wrote:
| Reminded me:
|
| https://en.m.wikipedia.org/wiki/Water_integrator
| The Water Integrator (Russian: Gidravlicheskii integrator
| Gidravlicheskiy integrator) was an early analog computer built in
| the Soviet Union in 1936 by Vladimir Sergeevich Lukyanov. It
| functioned by careful manipulation of water through a room full
| of interconnected pipes and pumps. The water level in various
| chambers (with precision to fractions of a millimeter)
| represented stored numbers, and the rate of flow between them
| represented mathematical operations. This machine was capable of
| solving inhomogeneous differential equations.
|
| Also see "A brief history of liquid computers":
| https://royalsocietypublishing.org/doi/10.1098/rstb.2018.037...
| miketery wrote:
| When I first started learning EE I conceptualized it with
| water. Ie voltage / potential is a higher water level vs else
| where. But this takes it to a whole new level, impressive!
| [deleted]
| pradn wrote:
| There's a whole Wikipedia page for the water-electricity
| analogy:
|
| https://en.wikipedia.org/wiki/Hydraulic_analogy
| marcosdumay wrote:
| If you search the web (or only Youtube), there are even
| digital water computers out there.
| GistNoesis wrote:
| Inspired by Steve mould, I had some fun doing something quite
| similar a while ago experimenting with Bell Siphon, 3d printing,
| and numerical simulation. If this interest someone here I just
| pushed it to Thingiverse now
| https://www.thingiverse.com/thing:5948252
| https://www.youtube.com/watch?v=S748mcM0MSg
|
| As Steve showed, it's particularly important to take into account
| both air and water.
|
| There is still some work needed to make it Sim2Real and optimize
| the design automatically.
|
| The ambitious end-goal, is to have a cascading siphon (not so
| dissimilar than the flushing mechanism in your toilet) that can
| reliably be switched on by a single additional drop of water.
| (Currently I achieve this goal using a Shishi Odoshi fountain to
| arm the siphon very reliably but it still has one moving part,
| but that's a story for another day).
|
| Quite fun, messy and time-consuming rabbit-hole to go down to,
| cause you need to get the details right.
| jagged-chisel wrote:
| > 404 you've reached the end of the thingiverse
| GistNoesis wrote:
| Sorry republished it, should be OK now
| OscarCunningham wrote:
| For sufficiently large mazes it must get harder to push the water
| through. Water can't solve a Tesla valve.
| (https://en.wikipedia.org/wiki/Tesla_valve)
| bell-cot wrote:
| Yes, water can solve a Tesla valve:
|
| > Steady flow experiments, including with the original design,
| however, show smaller ratios of the two resistances* in the
| range of 2 to 4.[6] It has also been shown that the device
| works better with pulsatile flows.[6]
|
| *Ratio of resistance to water flowing "forward" vs. "backward"
| through the Tesla valve.
|
| Though if you stretch things far enough - say, a thick layer of
| "waterproof" clay - your statement is correct for _most_
| purposes.
| hinkley wrote:
| Rectifying diodes also have limitations for how much reverse
| voltage they can block. When I fiddled with circuitry I was
| surprised how low that could be for cheap rectifiers. It sank
| some of my naive designs.
|
| Real circuits can have transistors or resettable fuses to
| handle out-of-spec situations and shut down.
| [deleted]
| beanjuice wrote:
| This reminds me of this classic paper [1] "Maze Solving by
| Chemotactic Droplets". Oil droplets sense a chemical gradient as
| variation of interfacial tension, using what is commonly known as
| the "Tears of wine", or Marangoni effect, to propel themselves to
| the exit.
|
| [1] https://pubs.acs.org/doi/full/10.1021/ja9076793
| s-macke wrote:
| If you are using a gas rather than a liquid, it is even simpler.
| Just set a high pressure at the beginning and a low pressure at
| the end. The gas will automatically follow the steepest part of
| the pressure gradient.
|
| The static solution can be calculated by solving the Poisson
| equation. In [1] you can see a small implementation of the idea.
|
| [1] https://simulationcorner.net/maze/
| willis936 wrote:
| Some if Buls Berglund's recent videos about waves in mazes made
| me realize this.
|
| Funnily enough he uploaded a video two hours ago that shows
| what it looks like.
|
| https://youtu.be/lBLlYmM6tjU
| chriswarbo wrote:
| This reminds me of Collaborative Diffusion
| https://en.wikipedia.org/wiki/Collaborative_diffusion
|
| A classic example is programming the ghosts in pacman to trap
| the player, which seems to require a sophisticated,
| collaborative strategy. Instead, a much simpler solution is to
| make a "pacman smell" diffuse through the maze:
|
| - The cell containing pacman has its "smell" clamped to 1
|
| - Cells containing walls and ghosts have their "smell" clamped
| to 0
|
| - The "smell" of an empty cell is the average of its neighbours
|
| This way, dumb hill-climbing will move the ghosts along the
| fastest route to the player. "Collaborative" behaviour emerges
| from the "smell" being clamped to 0 by ghosts: if a route to
| the player is already blocked-off by a ghost, those behind will
| not get any "smell" from that direction, and will take other
| routes instead; effectively cutting-off all of the escape
| routes. (I implemented this in Pygame many years ago, and it
| was no fun to play, since the ghosts were way too smart!)
| mhink wrote:
| I never knew there was a proper term for this technique! In
| the roguelike development community, these are known as
| "Dijkstra maps", and people use them for all sorts of things.
| [1] One of the coolest tricks the article describes is the
| idea of constructing several different Dijkstra maps for a
| particular game map, and then multiplying them together under
| certain circumstances to get a net weight for each tile.
|
| 1: http://www.roguebasin.com/index.php/The_Incredible_Power_o
| f_...
| xmcqdpt2 wrote:
| AFAIK this would also work with an incompressible fluid like
| water if you started the maze fully filled than add a sink at
| the exit and a source at the entrance. You wouldn't have any
| bubbles in that case and the current would flow along the
| solution.
| simondotau wrote:
| It would be interesting to see what would happen to a fully
| filled maze if, once you got a steady continuous flow at the
| entrance and exit, you injected some dye into the water at
| the maze entrance.
| fooker wrote:
| It would have been even more interesting if this was not in
| the linked video!
| mnw21cam wrote:
| He's wrong about why that maze towards the end of the video
| doesn't empty out the supply tank. It's not surface tension, but
| rather it is the fact that the path goes up and down. The down
| parts of the path will be filled with air, and the up parts will
| be filled with water. Water is more dense than air, so the supply
| must have more pressure than the sum of all the heights of the up
| parts in order for water to flow.
|
| This is why you don't have water pipes in your house go up and
| down loads of times. It can cause an air lock preventing water
| from flowing.
| pjsg wrote:
| Yeah -- I was disappointed that he didn't show an example of a
| maze which is not solved by water (for a finite amount of
| head). I most often experience this phenomenon is when I'm
| putting the garden hoses away for the winter when you want all
| the water out of them. However, if they tend to curl up, then
| you can get into the state where the water won't come out of
| the hose once some air gets in. The only solution is to
| straighten them out.
| kurthr wrote:
| I agree. It's weird, because I have to believe he realizes
| how it works (eg what it can "solve" and what it can't). Just
| demonstrating a little though experiment would go a long way.
| Retric wrote:
| Mostly, but surface tension in aggregate is meaningful.
|
| Surface tension is doing two things, first it's contributing to
| back pressure several times in the same way it's just barely
| keeping water from over topping. Secondly it's taking up volume
| in air pockets thus increasing the pressure of those pockets.
| So, if he added soap to reduce surface tension the tank
| wouldn't empty but it would end up lower. My guess is roughly
| an inch but it's worth testing.
| mywacaday wrote:
| What's great about this video and the discussion is that
| something as familiar as water can have new and non intuitive
| things to learn about it. Are there any other examples of
| common things that have non obvious behaviour from every day
| experience?
| 123pie123 wrote:
| water has a fair number interesting properties
|
| https://www.chemistryworld.com/features/the-weirdness-of-
| wat...
| krisoft wrote:
| > Are there any other examples of common things that have
| non obvious behaviour from every day experience?
|
| How about the chain fountain (also from Steve Mould):
| https://www.youtube.com/watch?v=_dQJBBklpQQ
| dr_kiszonka wrote:
| Sounds like great AskHN material to me, especially if you
| allow computers-related answers : - )
| olejorgenb wrote:
| ZipString/string shooter:
| https://www.youtube.com/watch?v=rffAjZPmkuU (other videos:
| https://www.youtube.com/watch?v=SOEXXlXi4RA /
| https://www.youtube.com/watch?v=f2krPkJ1pfs)
|
| Slightly related:
| https://www.youtube.com/watch?v=BSSecjKRxEE (slow moving
| waves in moving rope)
|
| Bruce Yeany have many good videos covering various physics
| phenomena.
| btilly wrote:
| If you pump air through sand, it turns into a fluid.
| https://thekidshouldseethis.com/post/royal-institution-
| fluid... An important example application is in getting
| grain to flow smoothly out of a grain silo.
|
| Some substances are "non-Newtonian fluids" meaning that
| they are liquid normally but turn solid under pressure.
| Famously, a mixture of cornstarch and water does this,
| which kids can have endless fun with:
| https://www.youtube.com/watch?v=Fnd-2jetT1w An example
| application is bulletproof vests which allow their wearers
| to move normally but will stop a bullet.
| jplona wrote:
| https://youtu.be/zdkp9N3qfkI is a good overview of air lock.
| quickthrower2 wrote:
| I thought so, because the first area of surface tension he
| pointed out is disconnected from the rest of the water. So that
| surface tension alone would have to explain it. But there was a
| lot of water up there!
|
| I guess it is the same as the upsidedown glass of water with a
| sheet of paper underneath trick.
| btbuildem wrote:
| How does that reconcile with the syphon principle? You'd figure
| that once the water is flowing out of the end, even if the tank
| was below some of the water's path, the flow would continue
| until all the water was gone.
| mnw21cam wrote:
| Siphons work best once air has been excluded from the path.
| In fact, they work exactly as the opposite to why this maze
| isn't draining the whole source tank. In a working siphon,
| the head of water in the downwards direction is greater than
| the head of water in the upwards direction, which pulls the
| water forwards. In this case, because of the air columns in
| the down direction, there is a greater head of water in the
| upwards direction than the downwards direction, causing a
| reverse back-pressure.
| CrazyStat wrote:
| Yep. It's easy to test for yourself that a siphon will
| quickly stop working if you let too much air into it.
|
| This is also why you can't make very tall siphons, as if
| the pressure gets too low at the top the water will boil
| off, create a gas pocket of water vapor, and stop the
| siphon.
| huhtenberg wrote:
| Very nice.
|
| I think that the explanation given for why the water stops
| flowing [1] is wrong. It has likely less to do with the surface
| tension "on the lip" (see video) and more with the fact that that
| all air bubbles in the maze become pressurized and their
| cumulative pressure is enough to push back on the water trying to
| get into the maze and prevent it from flowing in.
|
| I do agree though that it's a rather unexpected behavior.
|
| [1] https://www.youtube.com/watch?v=81ebWToAnvA&t=370
| rrobukef wrote:
| It shouldn't be, because every bit of upwards pressure towards
| the exit is compensated by the same amount of downwards
| pressure on the path before. I'm surprised there is that much
| static resistance in the maze.
| [deleted]
| tromp wrote:
| Maze solving by gravity assisted literal flood-fill [1]
|
| https://en.wikipedia.org/wiki/Flood_fill
| andreygrehov wrote:
| This reminds me of The Dumbest Way To Solve A Maze [1] by
| Numberphile - similar approach. Posted on HN before [2]
|
| [1] https://www.youtube.com/watch?v=BvwgdrC8vlE
|
| [2] https://news.ycombinator.com/item?id=32799511
| UncleOxidant wrote:
| You can also solve a maze with Cellular Automata:
| https://github.com/philtomson/CellularAutomata#you-can-solve...
| 1970-01-01 wrote:
| The practical application of this fluid maze is the automatic
| transmission's valve body:
|
| https://youtube.com/v/u4kM67f_P3A?t=23
|
| Tangent: Change your transmission fluid. Lifetime transmission
| fluid spec is the lifetime of your vehicle's powertrain warranty.
| freetime2 wrote:
| The thing that I found most interesting was actually the little
| side discussion about all mazes being two pieces. Something that
| I had never considered, but seems fairly self evident (assuming
| only one path exists through the maze).
|
| Also makes me wonder what a proof would look like.
| [deleted]
| albert_e wrote:
| Hmm interesting indeed. He also shows that you can use the
| "bucket fill" paint tool on any part of the maze to
| automatically highlight and visually "separate" that half from
| the other half of the maze.
|
| Now can we use THIS property to automatically solve a maze?
| make the WALLS of the MAZE themselves out of transparent TUBES
| and fill THEM with dyed water? An then the solved maze is
| simply the path that always has dyed walls on one side and
| transparent walls on the other. Not sure what the mathematical
| proof for this will look like but sounds nearly as good as the
| original "water can solve a maze" proof?
| delecti wrote:
| Most maze solving algorithms don't really interact with the
| maze in that way. You generally act on cells/spaces and
| whether or not the adjacent cells are connected or blocked.
|
| To use this property on a maze you'd have to traverse the
| whole maze using the typical cell adjacency, reconstruct it
| in a format that lets you bucket fill the walls, do that, and
| then also construct an algorithm which acts using the
| different colored walls. It only really works for a person
| interacting with a maze in a format where they can bring it
| into a picture editor.
| jollyllama wrote:
| This reminds me of trying to imagine a "Flatland" creature's
| biology; you can't really have one with a digestive tract.
| bmc7505 wrote:
| You could have, the creature would just need a pair of
| zippers that unzip and zip the digestive tract as materials
| pass through, a bit like RNA polymerase unwinds and rewinds a
| strand of DNA. The zipper's teeth could act as conduits for
| the nervous and circulatory systems.
| btbuildem wrote:
| > all mazes being two pieces
|
| This is true for mazes with only one path from start to end.
| Each additional path necessitates a separate piece (path
| permutations nonwithstanding)
| jeanlucas wrote:
| He says that in the video...
| Moissanite wrote:
| > mazes with only one path from start to end
|
| One of my favourite bits of trivia: it is this property
| (being "unicursal") which leads to a maze being more
| specifically characterized as a labyrinth.
| moefh wrote:
| That's interesting, but it's a weird definition. In the
| myth of the Minotaur, the labyrinth Theseus is trapped in
| surely must have branches (or he wouldn't need a ball of
| thread), so it doesn't fit this definition.
|
| Wikipedia[1] also notes this contradiction:
|
| > 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.
|
| [1] https://en.wikipedia.org/wiki/Labyrinth
| bootsmann wrote:
| This is a consequence of max flow/min cut duality if I recall
| correctly.
| ndsipa_pomu wrote:
| > Also makes me wonder what a proof would look like.
|
| Start with the simplest possible maze (i.e. one square with a
| start and a finish) which will be in two pieces. Then show that
| all possible additions will not add further pieces except for
| when you "cut" into an existing piece to make a separate non-
| solution route (i.e. a looped route that takes you back to the
| same point).
|
| (Having any loops in the maze would break the condition of
| there being only one solution as you could take a detour round
| the loop as many times as you like and thus have an infinite
| number of "solutions")
| latortuga wrote:
| This comment took me straight back to Discrete Math in
| college, learning about inductive reasoning.
| dmurray wrote:
| > (Having any loops in the maze would break the condition of
| there being only one solution as you could take a detour
| round the loop as many times as you like and thus have an
| infinite number of "solutions")
|
| The loop could be somewhere inaccessible from the starting
| point. Perhaps your logic holds if you insist that all
| pathways in the maze are connected, though.
| ndsipa_pomu wrote:
| Or define that the "maze" is the collection of all the
| reachable areas from the start position. Then, it doesn't
| matter what you do in inaccessible areas as they're not
| part of the maze.
| krisoft wrote:
| Meh. Sophistry. Changing definitions to get unexpected
| results is boring.
|
| The simple truth is that the original proposition "all
| mazes being two pieces" is just false.
|
| Obviously false when you have multiple exists, or when
| there is only one exit/entrance and the goal is to reach
| the middle of the maze. But even if we stick to one
| entrance one exit mazes you can have multiple paths from
| exit to entrance which cut the maze into multiple pieces.
|
| But even if we constrain ourselves to one entrance, one
| exit mazes with a single solution path you can trivially
| construct a maze inside a large room without connecting
| it to the walls. Thus creating a third piece to the maze.
|
| It is just simply false.
| ndsipa_pomu wrote:
| I'd consider it to be specifying the "maze" more
| accurately. The idea is to be able to come up with an
| interesting statement (such as "all mazes of this type
| can be made of just two pieces"), but if you include non-
| reachable areas as part of the maze, then it reduces the
| number of interesting statements available but also
| doesn't add to the process of examining the routes and
| solution.
|
| If you consider the same type of maze but have it in
| three dimensions, then all of them can be made out of
| just one piece, so it's clear that the definition of
| "maze" is too encompassing.
| ndsipa_pomu wrote:
| >But even if we constrain ourselves to one entrance, one
| exit mazes with a single solution path you can trivially
| construct a maze inside a large room without connecting
| it to the walls. Thus creating a third piece to the maze.
|
| I would be intrigued to see that "trivial" solution - how
| do you prevent there being two routes (and thus
| solutions) around the third piece without connecting it
| to the wall?
| krisoft wrote:
| I see what you are saying, yes the maze wouldn't have
| only a single solution after the construction of an inner
| maze.
| frivfkg wrote:
| In the literature on mazes, the distinction you are
| talking about is described to using the terms "simply
| connected" abd "multiply connected" from topology.
|
| See e.g. https://www.britannica.com/topic/number-
| game/Mazes
| danjc wrote:
| Did you see this by any chance?
| https://twitter.com/matthen2/status/1642236406465454082?s=46...
| pxeger1 wrote:
| You can make a maze with only one path (other than paths that
| double back on themselves), but has three pieces:
| https://i.imgur.io/R4j6TH3_d.png
|
| I think this is basically a flaw in the intuitive definition
| (or maybe only _my_ intuitive definition) of "doubling back".
| patates wrote:
| That maze has 3 solutions though. If there is only one
| solution, without reversing, it has to be 2 pieces.
| pwagland wrote:
| Except that this maze clearly has at least two solutions.
| Straight through the corridor, or via the loop. And that's
| assuming you don't wander around the loops n times.
| kolinko wrote:
| Three solutions if you want to be nitpicky. You can go
| around the clockwise, and counter-clockwise :)
| redblacktree wrote:
| Infinite solutions. You can take as many loops as you
| like before continuing to the exit.
| pxeger1 wrote:
| But, to me, that requires doubling back on yourself (going
| through the little passageway twice). This is what I meant
| by my definition of going back on yourself being wrong
| xmcqdpt2 wrote:
| In your case there are technically two paths through the maze
| (straight through and going through the loop).
| Enginerrrd wrote:
| >Also makes me wonder what a proof would look like.
|
| I think you need to be very careful in how you define a maze,
| lest you run the risk of rediscovering the difficulties
| involved with the Jordan Curve Theorem.
___________________________________________________________________
(page generated 2023-04-03 23:02 UTC)