Solving a maze

The age-old trick of brute forcing your way through a maze doesn't always work -- keep that in mind next time you find yourself smack in the middle of a realm ruled by David Bowie.

Before we begin it would probably be useful to describe the follow the wall method. The common understanding is that simply sliding a hand along one wall will (eventually) lead out of a maze. This is patently wrong.

Regarding a static maze (all bets are off if walls are moving behind you) the best one can hope for from following a wall is this:

• Should you start from outside a maze, you will find an exit (and if none exist, you'll at least eventually return to your entrance).

• You may not necessarily find the correct exit.
• If you begin inside a maze, you may never find your way back out at all.

The naïve follow the wall trick uses the assumption that any maze can be reduced to two separate but coherent sections of maze, with the correct solution running between them. That is, any maze has one entrance, one exit and is essentially a hallway with pliable walls. To illustrate, the following three mazes are fundamentally the same. For clarity the East wall is denoted with a '@', the West with a '#' and the path generated by following the left wall is marked by '.':

                           f
                  #########.@
                  #....#....@
                  #.####.@@@@
   f       f      #....#....@
  #.@     #.@     #.#.#####.@
  #.@   ###.@@@   #.#.....#.@
  #.@   #...  @   #####.#.#.@
  #.@   ###.@@@   #...#.#...@
   s      #.@     #.@.#####.@
           s      #.@.......@
                  #.@@@@@@@@@
                   s

Notice that in each of the above mazes, the East and West walls can be deformed (by pushing and pulling on them) to form either of the other two mazes. At no point is either wall broken.

The follow the wall method starts to fail if either breaks or free-floating wall sections are introduced -- that is, the maze has lost its simple hallway-like structure:

   f     f      
  Z @   # @
  Z @   # @@@@@         
  Z @   #.....@     
  Z @   #.ZZZ.@   
  ..@   #.Z Zs@   
  #.@   #.ZZZ.@    
  #.@   #.....@   
  #.@   ##### @
  #.@       # @
   s         f

BEWARE: It's entirely possible that a non-trivial maze has been designed specifically to thwart this sort of brute forcing.

Note that the follow the wall method is simply the real world application of a depth-first search. A 2D square maze can be represented by a tree with nodes having no more than three children (where each intersection is represented by a node and each node can have Left, Forward and Right children).

Firstly, all junctions can be broken down into a number of T-junctions. Take this four way junction:

  # #
  # #
### ###

### ###
  # #
  # #

  # #
 ## ##
##   ##
   O
##   ##
 ## ## 
  # #

This means that any path between any two points can be converted into a number of lefts and rights. (To go straight on in this example, you turn left then right then left).

Next, you should estimate the depth of the maze. This is the bailout factor, after which you give up on a particular path and try another. If this is not high enough you won't get out of the maze. This is the lowest number of lefts and rights that will get you out of the maze.

Start wherever you are. Then count, in binary, from 0 to 2^bailout-1. (That's going to be in the order of a thousand for a small maze, up to about a couple of million for a complex one. You got the time, I take it...)

Then follow the path, taking 0's to be left-turns and 1's to be right-turns. If you reach the end of the binary string, retrace your steps (the opposite of your path before) and try the next one.

YMMV, but it's going to be quite excessive anyway...

   f     f
  Z @   # @
  Z @   # @@@@@         
  Z @   #     @     
  Z @   # ZZZ @   
 f  @   # Z Zs@   
  # @   # ZZZ @    
  # @   #     @   
  # @   ##### @
  # @       # @
   s         e

Both of your examples merely illustrate te limitations previously mentioned: no guarantee of which exit a person will reach, and that you cannot start in the middle of a maze. (thanks Deejah for pointing out things when I'm tired)

In all cases of a static maze rendered in two dimensions (ie: only a wall or an exit, no sliding/changing bits, etc), your only options are a wall connected to other walls, a freestanding wall (which you'll never end up touching if you use the follow-the-wall-method from the outset), or an exit. It is possible that the only exit you will find will be the exit that you started from. You may not get the 'correct' exit, but otherwise you will reach an exit placed on the outside of the maze. Now if you remove your hand from a wall, you can get confused, and maybe touch a free-standing wall, but otherwise, keep on following.

However, you can treat any exit as a wall, thus if it is not the correct exit you want, and continue onwards to find all the other exterior exits.

    3
   f-g 
  Z| |@
  Z| |@
  Z| |@
 d-e |@
2|   |@
 c-b |@
  #| |@
  #| |@
  #| |@
   a h
    1

Enterance 1, from a-c to exit 2, conversely, you don't like exit 2, continue on as if 2 were a wall, and go a-f to exit 3. If you don't like exit 3, continue on as if 3 were a wall, and you wind up at 1 a-h (all the exits available to you)

Also, it must be noted that this solution only works if the exits (and enterance) are on the outermost wall of the maze. For mazes with exits located in the interior, use the Pledge algorithm, a form of wall-following which allows the jumps to islands, thus allowing it to solve mazes wall-following can't (thanks XWiz for the short description of pledge).

Now if I could just get e2 to quit reloading my old write-ups :P