# The Maze With An Unknown Size

You awake in the middle of a maze. You do not know how large the maze is. You do not know how many paths there are.

How can you assure you get out in the shortest amount of time?

This assumes the following things:

• There is only 1 exit
• You do not know the correct path
• You cannot walk through walls
• You cannot fly
• You cannot leave your body to get a birds eye view
• Other logic and common sense related things.
• “get in the shortest ammount of time”?
– Ry-
Oct 6 '14 at 23:31
• "Other logic and common sense related things" just feels like the laziest get-out clause for a brainteaser. It just makes me feel like there's no point trying to think of anything because you could just say "no, it's illogical to expect that to work"
– Joe
Oct 6 '14 at 23:48
• @Joe By that I meant like you can't see through walls, go underground, climb the walls, grow super tall, etc. Oct 7 '14 at 0:10
• Well, since this is a brainteaser, and the answers below have indicated that there is no optimal strategy, surely the solution is simply "Run, don't walk"? Oct 7 '14 at 9:06
• Define where you are as the outside of the maze. Oct 7 '14 at 18:00

How can you assure you get in the shortest amount of time?

Unfortunately, if you know nothing about the design of the maze, then there is no optimal strategy. For example, it would be easy to design a maze that quickly splits off into two paths - one that ends almost immediately, and one that winds around to use up all of the remaining area of the maze. The exit could be placed at the end of either path, and a mirror image of the maze could be used to switch whether the long path is to the left or to the right. Thus, the strategy of always trying the left (or right) path first could ending causing you to walk almost the entire area of the maze twice before going on the short path.

That being said, there are a couple things we do know - we are in the middle of the maze, and the exit is on the outside. So first, pick a direction to call North - if you can see the sun and know whether it is morning or evening, then you can use actual North. Then whenever you are at an intersection, your priorities should be North first, then East, then West, and last South. (Note - the priorities are mainly to try to get you to the edge of the maze as fast as possible. You're likely to get out of the maze faster if you're going around near the edge of the maze than if you're walking around in circles near the middle of the maze)

As with Denis' strategy, you should make marks to keep track of where you've been. At each intersection, make a mark connecting where you entered with where you exit. You should also make a mark indication what direction is your North at each intersection and at each turn.

If you run into an intersection that you've already been in and you've already taken or come from all of the paths, then backtrack until you find a path that you haven't gone down already. You can mark off all paths you backtrack over in some way that will indicate to you that the path will not help you find the way out.

Since you will never backtrack over the same path twice, you will at worst cover the area of the maze twice other than the path that leads out. Thus, my strategy has the optimal worst-case scenario, but I think that attempting to get as far from the middle (your starting place) as possible to begin with should make it more likely that you'll escape the maze quicker in the average case.

MOST IMPORTANT PART OF ANY STRATEGY:

As I said, there is no optimal strategy, but there are definitely strategies that will be worse on average. Consider a breadth-first search (go down each path a little ways, check the other paths that far, then check down the first path a little bit farther, etc). This could beat the one long + one short maze faster, but you might end up walking up and down each path multiple times. If the two paths were the same length, then you'd end up covering the entire area of the maze far more than just twice.

So the most import part of any strategy is to guarantee that you will never go down the same path more than twice. The strategy I gave does this by marking off any path that you've backtracked on.

The strategy of following a wall guarantees this most of the time. You'd think that, since you only follow a wall once and each path has two walls, you'd never walk the same path more than twice, but consider the case that Trennin pointed out of starting between two loops:

----------------
|              |
| -----1 ----- |
| |   |  |   | ->More maze
| |   |:S|   | ->this way
| -----2 ----- |
|              |
----------------


You walk the full path between the loops once when you follow the first wall (start to 1, then 2 to start), and once again when following the second loop. Then you're back at the starting position, and you've got to walk to either 1 or 2 and cover that ground for the third time if order to get to a wall that you haven't followed yet. Unfortunately, a particularly devious maze designer could, if he/she knew your strategy, build the maze such that the shared path of the two walls is as twisty and long as possible and make sure you get placed in the middle of that path, causing you to waste a fair bit of time on that third traversal.

Follow the left wall, always turn to the left. Meanwhile, mark the wall you are following. If you go back to your mark, try with another wall (it can be that now you always turn on the right). You will end up trying the "outside" wall, and finding the exit.

• What if there's a complete ring around the centre of the maze? You'd just keep turning back around it
– Joe
Oct 6 '14 at 23:37
• Only ensures you get out, not that you get out in the shortest amount of time
– Joe
Oct 6 '14 at 23:41
• It might be optimal, but this has a brainteaser tag on it...
– Joe
Oct 6 '14 at 23:44
• While this is a classic and common theory, it doesn't ensure a shortest amount of time to get out. If the question were to find the shortest path, and you can cut out the unneeded looping around caused by the method, it may actually lead to a shortest path (and even that is uncertain). It however does not guarantee an optimal time strategy, where I think Rob Watts answer is more relevant. Oct 7 '14 at 9:04
• @Trenin, we can solve the "two circles almost touching" loop problem if we modify the technique to "If you go back to your mark, try another wall that doesn't already have a mark on it". If the maze really does have an exit, I believe there will always be an unmarked wall somewhere along the path you've already traversed. Oct 7 '14 at 15:34

There are 2 simple algorithms that will let you exit a maze (from Wikipedia)

# Pledge algorithm

Named after after Jon Pledge of Exeter. Works for a plane maze when you need to move out. It requires perfect orientation.

1. Move north until you are blocked by a wall.
2. Follow the wall touching it with your right hand. Track exactly how much you turn left and right.
3. As soon as you are facing north again and you have turned left as much as you have turned right, restart at 1. moving north.
4. Stop when you see the exit.

# Trémaux's algorithm

By Charles Pierre Trémaux. Works for any maze.

Count the starting point as a junction.

At every junction, mark the path where you arrive and the path where you leave. To choose a path, just take the one with the less marks. You are guaranteed to walk the whole maze before returning to the starting point and having tried all paths from there.

# Minimal Time

Tremeaux's algorithm favors exploring new paths before backtracking. And since the exit could be anywhere, the best way to find the exit fast is to explore as much and as soon as possible. Therefore I would estimate that Tremeaux's algorithm is as good as most algorithm to find the exit fast. Better algorithms would have to track precisely where you have been and eliminate surrounded regions without visiting them.

Recursive Backtracker....

• asserting it's a perfect maze

you walk until reach a dead-end... mark that deadend and walk back the path you came until you reach a crossing, then take another way (not that you where you started, not the way from the dead-end)... if you reach a dead again walk your way back further and take the next crossing ... repeat until you leave the maze...

This is not an answer, but rather a disproof of Denis' answer (sorry Denis - no offense, but the comments were insufficient to show the counter example).

Say you have the following maze:

+-----|  |-----+
|              |
|  +--+  +--+  |
|  |  |  |  |  |
|  +--+  +--+  |
|              |
+--------------+


And say you started right in the middle of the two squares. If you put your hand on the left wall and followed it around, you would eventually return to where you started. If you then switched to the right, the same thing would happen. The problem is that in this case, neither wall is an outside wall, so following either will not get you to the exit.

• At that point, since your hand was marking the wall with chalk, you switch to the outer wall (with the exit in it) when both the inner walls are chalk-covered
– Joe
Oct 7 '14 at 14:51
• @Joe You start with the left wall, marking it with chalk. Since it is not an outer wall, you return to the point between the the two squares and see that you have already marked this wall. Thus, you switch to the right wall. It too is not an outer wall, so you will again return to the point between them. Now you are standing in potentially a long corridor (if the squares are large) and both sides have chalk. There is no outer wall close by to try at this point. Oct 7 '14 at 14:59
• So you follow one until you see a wall without chalk, which you will (and you'll remember that they're there)
– Joe
Oct 7 '14 at 15:13
• @Joe OK - but that is not the strategy he originally posted and is more like Martin's; simply use chalk to mark where you have been and always take a path you haven't tried yet. Oct 7 '14 at 15:16

My solution is similar to Denis one, but I think it's faster to turn alternatively left and right in order to reach the bounds of the maze faster.

• You may want to try and 'prove' that somehow - wild guesses aren't really valid answers. Oct 7 '14 at 9:01
• Don't see any proof in Denis answer. Don't see any proof on this site in general. Oct 7 '14 at 10:18
• It is pretty easy to create a maze where alternating will take longer than sticking to one side. But that would be a maze constructed specifically to thwart this strategy, and it is probable that this strategy works better on average. Oct 7 '14 at 15:19