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).
Nothing else is guaranteed. Specifically,
-
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).