9
$\begingroup$

There is a well-known rule of getting out of any finite labyrinth in a finite timespan; just find an outer wall, touch it with your appropriate hand and when it turns, turn with it. This way, the worst case scenario is that you will roam across the entire labyrinth - or in case of non-recursive labyrinths all the labyrinth except for the islands - but doing so you will walk all points of the labyrinth including the exit, so you can get out. In recursive labyrinths, it will also work with any wall, not just outer walls (since you can't be at an island - a set of walls having no continuity to the wall with the exit on it).

The labyrinth rule will also work in 3D (multi-level) labyrinths, because multiple levels will only mean added ground to cover, not real added complexity. Now my question is, how about n-dimensional labyrinths? Of course n-dimensional labyrinths are theoretical, but would the rule still apply on them? Could you get out of the hyper-labyrinth simply by keeping your left hand on the left wall (assuming you won't get eaten by the hyper-Minotaur)?

Improve this question
$\endgroup$
16
  • 10
    $\begingroup$ It doesn't work in 3D because in 3D you can have configurations where you walk in circles. Consider a trifurcation in 3D, so that the path to the right brings you back to the trifurcation on the path to the left, passing over or under the forward path: you have just been brought back to the trifurcation facing in the opposite sense. A second similar trifurcation will now have you in an endless loop. $\endgroup$
    – AlexP
    Mar 19, 2018 at 11:55
  • 2
    $\begingroup$ Ok, a recursively generated maze. That makes more sense. A recursive maze would be a maze that contains other mazes inside it :) So far as I know there is no generic shorter term for "maze without islands" but I think that's the term you are looking for since the non-island property is a property of the maze not dependent on having used a recursive algorithm (mazes generated non-recursively can be island-free and I can think of recursive algorithms that would generate islands). $\endgroup$
    – Tim B
    Mar 19, 2018 at 12:12
  • 2
    $\begingroup$ How is this about building a fictional world? This seems like an interesting, question about mathematics. $\endgroup$
    – sphennings
    Mar 19, 2018 at 12:19
  • 8
    $\begingroup$ @mg30rg Why would this not be on math.SE? I can imagine this being very useful for a world/setting like "Cube" but it is at its core a topology question. $\endgroup$
    – kaine
    Mar 19, 2018 at 13:29
  • 2
    $\begingroup$ @kaine The key question is whether it is on topic here (it is) not whether it might also be on topic somewhere else. $\endgroup$
    – Tim B
    Mar 19, 2018 at 13:38

5 Answers 5

Reset to default
10
$\begingroup$

Quoting almost entirely from this page

The wall follower, the best-known rule for traversing mazes, is also known as either the left-hand rule or the right-hand rule. [...]

Wall-following can be done in 3D or higher-dimensional mazes if its higher-dimensional passages can be projected onto the 2D plane in a deterministic manner. For example, if in a 3D maze "up" passages can be assumed to lead northwest, and "down" passages can be assumed to lead southeast, then standard wall following rules can apply. However, unlike in 2D, this requires that the current orientation be known, to determine which direction is the first on the left or right.

Improve this answer
$\endgroup$
5
  • 14
    $\begingroup$ That's a big caveat though, any decent 3d maze would not be possible to project into a 2d plane in a deterministic way. $\endgroup$
    – Tim B
    Mar 19, 2018 at 12:05
  • 1
    $\begingroup$ @TimB, I didn't do the mathematics behind it. $\endgroup$
    – L.Dutch ♦
    Mar 19, 2018 at 12:24
  • 2
    $\begingroup$ @TimB: it does not have to be a truly deterministic projection, you only need to remember to which projection you used, if you ever get back to the same crossing. In fact it would be enough to simply mark all exits in an arbitrary order and then always take the next one. However as stated on the quoted page, this will fail if there are loops in the labyrinth. And unlike the 2D case, this cannot be fixed by following an outer wall, since all walls are effectively outer walls. $\endgroup$
    – mlk
    Mar 19, 2018 at 14:06
  • $\begingroup$ @mlk You need to know you are back at the same crossing and all sorts of other complications. See my answer for some discussion of the problems here. $\endgroup$
    – Tim B
    Mar 19, 2018 at 14:26
  • 1
    $\begingroup$ @mlk No--it's just that what's an inside wall gets far more complex when it's more than 2D. $\endgroup$
    – Loren Pechtel
    Mar 20, 2018 at 3:27
17
$\begingroup$

I am going to need to challenge your assumption here, are you sure that the rule works in 3d labyrinths?

The problem of implementation

When you come to a stairs do you go up or down? With a 2 dimensional maze you only have a limited number of choices at an intersection and always turning the same way is a state-free way of guaranteeing you follow all of them. With more dimensions you need some way of knowing that you have been at this intersection before in order to know which possible exit to take and which ones you have already used. For example imagine a square room with a door on each wall and a ladder in the center going both up and down. When you reach the room do you turn left or climb the ladder? Up or down? If you've climbed up and found it is a dead end and then return to this room which exit have you already tried and which one is new? If you have a reliable compass then an algorithm like "U,N,E,S,W,D in that order might work but it is still a lot more complex than just "turn left".

The problem of islands

The biggest problem though is that in a 3d labyrinth it's trivial to design one where constantly turning left will never find the exit - for example just have the exit extend from a set of stairs in an island at the center.

Here is a trivially simple example to illustrate:

    Level 1           Level 2
##############   ##########
#            #   #        Exit
#  #####  #  #   #  ###  ##
#  #>     #  #   #   >#  #
#  ########  #   #  ###  #   > is Stairs from level 1 to level 2
#            #   #       #
#####  #######   #########
    #  #
   Entry

Go in at the entry, you will never find the exit by following the left wall, only end up back at the entrance. Of course in this case it would be easy to find the real entrance and spot the passage you missed. In a more complex maze though that becomes a lot harder. The important point is that the wall following tactic is no longer enough.

The solution

The underlying strategy behind the labyrinth rule does extend out to n-dimensions, it's just the implementation that falls over. The only way to be sure of finding the exit is to exhaustively search every possible part of the labyrinth. The labyrinth rule does that in a simple way in 2 dimensions but as already discussed does not extend to 3 dimensions (or to islands in 2 dimensions).

In a computer you would model this as a recursive algorithm. In real life that becomes harder but you can implement the same algorithm.

The problem is that keeping track of what you have already searched becomes very tricky unless you leave markers behind (and no-one tampers with them) or build a map as you go (and don't notice a sloping passageway or subtle turning).

Recursive Algorithm: Take some chalk, mark every exit you go down. If you come to a room with any marks in it turn around and go back (this bit is important, don't just try another exit in this room as that way you miss things) until you find an unmarked exit. Mark that and follow it.

That is a recursive algorithm that is guaranteed to find the exit in any possible maze in any number of dimensions. So long as no-one messes with your chalk.

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ @Miller86 Yes, mg30rg is correct, I've expanded the relevant section of the answer to explain better. $\endgroup$
    – Tim B
    Mar 19, 2018 at 13:26
  • 1
    $\begingroup$ @mg30rg By your definition of an island, there are 2 in the example given. The first island is contiguous with the Entrance on Level 1, the second island is contiguous with the stairs between levels, and the outside wall is contiguous with the exit, but neither the entrance nor the stairs. Thus, both walls accessible from Level 1 are islands - following the first will lead you from the entrance back to the entrance, following the second will lead you in a loop up and down the stairs. Neither will reach the exit, even though the second loop will (in this simplified form) allow you to see it. $\endgroup$
    – Chronocidal
    Mar 19, 2018 at 15:37
  • 3
    $\begingroup$ @mg30rg but, then you are treating each level as a seperate labyrinth / maze, rather than as a single continuous n-dimensional one - conceptually quite different. $\endgroup$
    – Chronocidal
    Mar 19, 2018 at 15:45
  • 2
    $\begingroup$ Maybe an even simpler counterexample would be something similar to a figure 8, where there is no crossing in the middle, but a bridge. If you put the entry at the bottom and the exit at the top. Then both could be said to be at outer walls, but both are at different walls, so the strategy will fail. $\endgroup$
    – mlk
    Mar 19, 2018 at 15:46
  • 9
    $\begingroup$ @mg30rg I think you are stretching the definition of "islands" to the point where it becomes "wall following will work in 3D except for those mazes where it doesn't" - which is true, but uninteresting. At least the 2D definition of "islands" has a reasonable intuitive meaning. $\endgroup$
    – Martin Bonner supports Monica
    Mar 19, 2018 at 15:59
12
$\begingroup$

Am I the only one that's tempted to point out the differences between a labyrinth and a maze? In a labyrinth, the whole point is simple to make you walk the entire length of the area, while mazes are meant for getting lost in.

And please note. That if you are going to tell me, "Yeah, but it's not that, it's this." Please show sources that conflict with what I've said. Really. The flurry of comments that are all like, "I know better, you're doing it wrong." And no one seems to understand that this is why I'm so sporadically on this site anymore. Relax. Breathe. And cite your source, because:

https://english.stackexchange.com/questions/144052/difference-between-labyrinth-and-maze

http://www.differencebetween.info/difference-between-maze-and-labyrinth

http://www.lessons4living.com/labyrinth_map.htm

https://www.diffen.com/difference/Labyrinth_vs_Maze

I do hope we won't be having the maze=labyrinth discussion. Because, really. The difference between them is exactly why you have maze puzzles, and not labyrinth puzzles.

Having said that, I would be exceedingly careful with those rules in mazes. Again, in a labyrinth, you only have forwards and back on a twisting and turning path. You have no choices.

Let's be clear here. This is a labyrinth:

Labyrinth

(notice one entrance, one possible path, and one goal.)

And this is a maze:

Maze

(notice multiple paths, even if this is a simplified version)

Now that we're on the same page with this (and please don't try to dictionary.com me, because I'm talking about historical and mathematical fact). Is there a conceivable way that touching an outer wall will lead you to getting lost?

Let's start with known algorithms. In the link, it describes ways your wall-follower rule don't always work.

If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

This means there are ways to foil your premise, and known ways. And that's in a 2-D maze. How much more so will this be the case if you add levels to a single maze? All I would have to do is design the maze so that all the outer walls are disconnected from the goal, and do that three or four times, and you'll be stuck in there for eternity.

Additionally. If you want to follow the 'left-hand rule'. Use it to get out of this maze.

simple maze

(above is a simple maze)

And more importantly, perhaps for me, what's the purpose of this maze. I mean, if it's just for the sake of getting people lost, then I can imagine there'd be a host of other obstacles to overcome. Think in the terms of a dungeon-crawl for ideas how to make it considerably more complex.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Tim B
    Mar 19, 2018 at 14:46
  • 3
    $\begingroup$ This distinction between labyrinth and maze does not reflect common usage of the two words; You will not find this distinction in any proper dictionary. It is clearly not the sense of the word the original poster was using. $\endgroup$
    – BobTheAverage
    Mar 19, 2018 at 16:02
  • 5
    $\begingroup$ @BobTheAverage It's also not the sense in the Greek myths. Theseus wouldn't have needed the ball of a string if there were no choices. $\endgroup$
    – Blue Footed Booby
    Mar 19, 2018 at 16:11
  • $\begingroup$ Comments are the right place to improve the question and ask for clarification (like using the right words) - Answers should try to answer the question as intended. $\endgroup$
    – Falco
    Mar 19, 2018 at 16:53
  • $\begingroup$ @BobTheAverage Sun is not a word that should even exist, given the sun is merely our star. Common usage can be wrong, or does the bandwagon fallacy simply stop existing because no one believes they are wrong? $\endgroup$
    – Fayth85
    Mar 19, 2018 at 20:04
6
$\begingroup$

Trivially, you can't. Just imagine a two-dimensional labyrinth, except that the exit goes into the third dimension from one of the "islands" that you can't get to by keeping your hand on a wall.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I ruled that out by saying "just find an outer wall, touch it with your appropriate hand and when it turns, turn with it." and "an island - a set of walls having no continuity to the wall with the exit on it" which would only make walls of the exit island outer. But it worth noticing that finding an outer wall is more tricky than it seems. $\endgroup$
    – mg30rg
    Mar 19, 2018 at 12:09
  • $\begingroup$ @mg30rg It seems to me that the only way to determine if a wall is an "outer wall" as you have defined it is to observe where it is in relation to the exit, thus making it pretty trivial to find the exit after finding an outer wall. $\endgroup$
    – Mike Scott
    Mar 19, 2018 at 13:21
  • $\begingroup$ I didn't say I haven't fiddle with the definitions a bit here, did I? $\endgroup$
    – mg30rg
    Mar 19, 2018 at 13:27
  • 5
    $\begingroup$ @mg30rg The issue here is that a maze that extends into 3D can have a wall that is contiguous with the exit, but is not contiguous with the entrance. At that point, given your definition of "outer" to mean "contiguous with the exit", your precondition of "just find an outer wall" becomes roughly equivalent to "just find a place within the maze from which wall-following will work", which makes your whole question kinda moot. $\endgroup$
    – anaximander
    Mar 19, 2018 at 16:27
  • 2
    $\begingroup$ @Joshua The problem there is that the question defines "outer wall" as "a wall that is contiguous with the exit". As I noted, in a three-dimensional maze, the wall by the entrance does not necessarily fulfil this condition, meaning that your suggestion of picking a wall when you enter the maze may give you a wall that the question considers an "island", not an "outer wall" - and when this happens, following that wall will not lead you to the exit. $\endgroup$
    – anaximander
    Mar 20, 2018 at 10:47
1
$\begingroup$

We all proved the algorithm (left hand on outer wall) correct over the spanning tree in Data Structures and Algorithms computer science class. The algorithm doesn't handle trapdoors but handles staircases just fine and non-embeddable geometries don't have a problem either.

So the actual limiting case is as follows: It does work in arbitrary N dimensions provided that doors exist in only 2 of the dimensions and the floor's orientation is well-defined.

The definition of "work" is not expected though. It's guaranteed to exit the maze, but not necessarily solve it. If you use this in caves and avoid all trapdoors you can avoid getting lost forever. If you go to long you just turn around and come back out the way you went in.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .