Hacker News Reader

Comment by ndsipa_pomu | Hacker News Reader

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

View on HN

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

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.

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.

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

I see what you are saying, yes the maze wouldn't have only a single solution after the construction of an inner maze.

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

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.

This comment took me straight back to Discrete Math in college, learning about inductive reasoning.

Reply on news.ycombinator.com