Supposing you are in a labyrinth, but you have a map and know where you are, there are many algorithms that will find a way out, if there is one.
Now, imagine you are allowed to wreck walls and make holes in them, so as to pass through. If you wreck enough walls, you are certain to be able to leave the labyrinth!
The problem: find an algorithm that determines the MINIMUM number of walls that should be broken in order to escape. Of course, it should also determine WHICH walls to break!
Consider a graph which represents the maze. This means a node for every
crossing of walls (three or more walls are joined in that point) and an
edge for every wall. The outerplanarity of the graph is the maximal
number of walls you would have to wreck to get out, starting from every
possible position. To calculate the number for a certain position, the
same algorithm can be used as for the determining of the outerplanarity
of such a graph. First, take every region which has a shared wall with
the outside. Paint that piece of wall (from the inside), and number the
region '1'. Remove all these regions from the maze, and repeat, but now
number the outer regions '2'. Repeat until the region you're currently
in has a number. Look for a painted wall, wreck it, and continue this
until you're free.
Mathematical thoughts
