Is the wall-follower algorithm a poly-time algorithm (for Perfect Mazes)?In particular, are there poly time algorithms for solving the Perfect Maze problems?A perfect maze has the following properties:no inaccessible areas and is simply connected. no closed loopsone and only one path from any point to any other point. the maze has exactly one solution.
Is the Wall-Follower Algorithm in P?
algorithm analysis;runtime analysis
Yes, there is a polynomial-time algorithm for solving perfect mazes: depth-first search solves them, and runs in polynomial time.  Actually, depth-first search is more general, as it can handle loops and other structures, too.Breadth-first search also works, and will give you the fastest way out of the maze, but is only implementable on a computer given the full description of the maze.  In contrast, depth-first search can be implemented by a human with a piece of chalk and a ball of string -- the piece of chalk allows you to mark rooms as visited, and the ball of string lets you simulate the stack.