6 ms·

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 see

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.

Enginerrrd 4y ago
>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.
ndsipa_pomu 4y ago
> 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")
- dmurray 4y ago
  > (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 4y ago
    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 4y ago
      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 4y ago
        >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 4y ago
        I see what you are saying, yes the maze wouldn't have only a single solution after the construction of an inner maze.
        frivfkg 4y ago
        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 https://www.britannica.com/topic/number-game/Mazes
      - ndsipa_pomu 4y ago
        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.
- latortuga 4y ago
  This comment took me straight back to Discrete Math in college, learning about inductive reasoning.
deleted 4y ago
[deleted]
pxeger1 4y ago
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 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".
- pwagland 4y ago
  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 4y ago
    Three solutions if you want to be nitpicky. You can go around the clockwise, and counter-clockwise :)
    - redblacktree 4y ago
      Infinite solutions. You can take as many loops as you like before continuing to the exit.
  - pxeger1 4y ago
    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
  - Terretta 4y ago
    Not if your path trace kills you like the lightcycle trails in Tron.
- patates 4y ago
  That maze has 3 solutions though. If there is only one solution, without reversing, it has to be 2 pieces.
- xmcqdpt2 4y ago
albert_e 4y ago
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 4y ago
  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.
btbuildem 4y ago
> 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 4y ago
  He says that in the video...
- Moissanite 4y ago
  > 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 4y ago
    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 https://en.wikipedia.org/wiki/Labyrinth
    - Moissanite 4y ago
      You could say the English language is... Puts on sunglasses A-maze-ing.
bootsmann 4y ago
This is a consequence of max flow/min cut duality if I recall correctly.
jollyllama 4y ago
This reminds me of trying to imagine a "Flatland" creature's biology; you can't really have one with a digestive tract.
- bmc7505 4y ago
  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.
danjc 4y ago
Did you see this by any chance? https://twitter.com/matthen2/status/1642236406465454082?s=46&t=tkaijzzdSxVe0ACSNvvxHw https://twitter.com/matthen2/status/1642236406465454082?s=46...

Enginerrrd 4y ago

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

ndsipa_pomu 4y ago

> 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")

dmurray 4y ago
> (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 4y ago
  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 4y ago
    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 4y ago
      >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 4y ago
        I see what you are saying, yes the maze wouldn't have only a single solution after the construction of an inner maze.
        frivfkg 4y ago
        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 https://www.britannica.com/topic/number-game/Mazes
    - ndsipa_pomu 4y ago
      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.
latortuga 4y ago
This comment took me straight back to Discrete Math in college, learning about inductive reasoning.

deleted 4y ago

[deleted]

pxeger1 4y ago

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 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".

pwagland 4y ago
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 4y ago
  Three solutions if you want to be nitpicky. You can go around the clockwise, and counter-clockwise :)
  - redblacktree 4y ago
    Infinite solutions. You can take as many loops as you like before continuing to the exit.
- pxeger1 4y ago
  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
- Terretta 4y ago
  Not if your path trace kills you like the lightcycle trails in Tron.
patates 4y ago
That maze has 3 solutions though. If there is only one solution, without reversing, it has to be 2 pieces.
xmcqdpt2 4y ago

albert_e 4y ago

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 4y ago
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.

btbuildem 4y ago

> 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 4y ago
He says that in the video...
Moissanite 4y ago
> 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 4y ago
  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 https://en.wikipedia.org/wiki/Labyrinth
  - Moissanite 4y ago
    You could say the English language is... Puts on sunglasses A-maze-ing.

bootsmann 4y ago

This is a consequence of max flow/min cut duality if I recall correctly.

jollyllama 4y ago

This reminds me of trying to imagine a "Flatland" creature's biology; you can't really have one with a digestive tract.

bmc7505 4y ago
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.

danjc 4y ago

Did you see this by any chance? https://twitter.com/matthen2/status/1642236406465454082?s=46&t=tkaijzzdSxVe0ACSNvvxHw https://twitter.com/matthen2/status/1642236406465454082?s=46...