I’d like to discuss some techniques for solving mazes.

Standard mazes contain no loops and are called “perfect”. They are equivalent with trees (you can pull and stretch the corridors in the shape of a tree), so graph theory can supply algorithms for solving perfect mazes. Other mazes are typically more difficult to solve in general.

A trivial method: follow the corridor until you reach a junction, and randomly choose the next direction to follow. If you have enough time and patience, eventually you’ll find the exit (with probability 1), but luckily there are more intelligent ways…

For instance, **wall-following**. Keep your right hand on the wall to your right, and follow the maze, without breaking contact between hand and wall. So simply, always turn right at a junction. You’re guaranteed to find the exit if the maze is perfect, or to return at your starting position if there isn’t an exit. If you’re left-handed, this method also works with your left hand ;)

If the maze does contain an island, wall-followers could be trapped into continually encircling a loop. **Pledge’s algorithm** solves this problem: choose a random direction and move that way until you hit a wall. Start wall-following and count the turns you make (for instance +1 for a right turn and -1 for a left turn). When your chosen direction is available again (you’ll see this when the total number of turns is 0), stop wall-following and continue in the direction you’re facing. This way, you’ll escape every maze, even if they contain loops.

An algorithm which also works in higher dimensions is **Trémaux’s algorithm**: draw a line on the floor. When you reach a junction, turn around if you’ve been there before; otherwise pick any direction. If you revisit a passage that’s already marked, draw a second line (you’ll never need to take a passage more than twice) and at the next junction take an unmarked passage if you can.

If you’re not actually stuck in the maze but you can see it “from above”, it’s useful to find the dead ends in the maze and fill in the path from every dead end until the first junction met. If there’s a solution, it will be preserved and you can try to solve the simpler maze instead.

A nice website with a lot more information:

http://www.astrolog.org/labyrnth/algrithm.htm.