Maze solving Algorithms
Wall Follower
Uses the right hand rule. If all the walls are connected together or to the maze’s outer boundary, then by keeping one hand in contact with one wall of the maze, the solver is guaranteed to not get lost and will reach a different exit if there is one.
Wall-following should start at the entrance to the maze. If the maze is not simply-connected and one begins wall-following at an arbitrary point inside the maze, one could find themselves trapped along a separate wall that loops around on itself containing no entrances or exists. The starting point should be marked so you can conclude if a cycle exists.
Disjoint mazes can be solved with the wall follower method so long as the entrance and exit are on the outer walls of the maze.
Implemented using a depth-first in-order tree traversal
Pledge Algorithm
Left: Left-turn solver trapped
Right: Pledge algorithm solution
Choose an arbitrary direction to go toward.
Implementation
Optimizations
Optimized Complexity
Time Complexity
Space Complexity
Related
- [[LC-489. Robot Room Cleaner]]
- https://en.wikipedia.org/wiki/Maze-solving_algorithm#Wall_follower