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!

First, I would figure out all the connected "chains" in the maze.  If there exists a way to get from A to B, both A and B must be part of the same chain.  The algorithm for this would be almost the same as the algorithm used to determine chains in the game of Go.  However, I would also write the algorithm such that it outputs a connectivity matrix that shows which chains are divided by only one wall.

So let's just say the connectivity matrix looks something like this:

[0,1,1,0,0]
[1,0,0,1,0]
[1,0,0,1,1]
[0,1,1,0,1]
[0,0,1,1,0]

Each row and column represents a chain, so in this example, there are 5 distinct chains.  Let's just call the first chain the "start" chain and the last one the "finish" chain.  Note that the matrix is symmetrical.  Also, note that the main diagonal is all zeroes, though I don't think it really matters.

To figure out the number of walls that must be broken, repeatedly multiply by this matrix until the number in the upper-right corner is non-zero.  If you had to raise the matrix to the nth power, n walls must be broken.  Why does this work?  Because if you multiply connectivity matrices, you get a matrix that represents the number of ways to get from chain A to chain B in two moves.

By nature of this algorithm, it is a little more difficult to determine which walls should be broken, but it feels to me relatively trivial.  I'm sure there's a way to look at the powers of the connectivity matrix and output the sequence of chains to go through.

Edit: after looking at the other solutions, mine seems too complicated.  Working backwards!  Of course.

Edited on April 4, 2006, 2:03 am

Posted by Tristan on 2006-04-04 02:01:26