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!

As it says, if there is a way out, there are many ways of finding it -- the right hand on the wall method, for example, and many others, furthermore if you have a map.

I am thinking about something on the lines of:

* try to find a way out without breaking any walls, using the right hand on the wall method.
* if you fail, assume ALL walls you touched with your hand will be broken down...

...and then start again lookign for a way out? Allow/disallow stepping again over the places you already visited? And if you donīt find a way out now?

Posted by e.g. on 2006-04-03 12:55:57