Solving mazes using regular expressions

Can the .Net regex engine find its way through a maze?

A maze?

We have a text based maze. We can walk on spaces, and need to find a path from the start point (S) to the end point (E). Anything else in a wall.

Examples:

██████████ █S█ █ █ █ █ █ ██ █ █ █ E█ ██████████

███████████████████████████S█████████████ █ █ █ █ █ █ █ █ █ ███ ███ █ █ ███████ █ █ ███ █ ███ ███ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █████ █ █ ███ ███ ███ █████ █ █ ███ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █████ █████ █ █████ █ ███ █ █ █████ █ █ █ █ █ █ █ █ █ █ █ █ █████ █████ █ █████ █████ ███ ███████ █ █ █ █ █ █ █ █ █ █ █ █████ ███ █ █ ███ █ █ █████████ ███ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ ███ ███████████ █████ █ █████ ███████ █ █ █ █ █ █ █ █ █ █ █ █ ███ ███████████ █ ███ █ ███ █ █ █████ █ █ █ █ █ █ █ █ █ █ █ █ █ █████ █ █ █████████ ███ █████ █ █████ █ █ █ █ █ █ █ █ █ █ █ █ ███ ███ ███ █ ███████ ███ █████████ █ █ █ █ █ █ █████████████████████E███████████████████

█S█ █ ███████ █ █ ███████ █ █ █ █E█

Strategy

We are going to implement the following algorithm for solving a maze:

1. Find the start point.
2. Pick a new position to go to. We have four choices: right, left, down, or up.
   The new position is invalid if it crosses our current path through the maze (the path cannot have loops).
3. If we reached the End, we are done.
4. If we cannot advance, undo the last choice and make a new one.
5. Go to step 2.

As you may have noticed, this is backtracking: we’re making choices and reverting them when we know they were wrong.

Advertisement