Amaze Me

This came up in the context of the development experience we’re working on. One of the objects we supply to work with is a maze – you can create a new maze, take a step in the maze, check to see if the direction you’re facing is a valid move, turn, and so on.

Anyway, Adam and I were standing in his office looking at the maze feature he’d created and I asked what a good algorithm was for solving it. He suggested on approach (when you hit a wall, always turn left), but we quickly discovered that could cause an infinite loop. I suggested a modification – when you hit a wall, turn a random direction. That seems to solve the maze, but it’s highly non-deterministic (albeit very memory efficient).

What’s the best solution?