How do I go about proving this algorithm?

Question

How do I prove that this algorithm can solve all n x n mazes?

The entrance of the maze is at the bottom left and the centre are the middle 4 squares. The algorithm is to first set an arbitary direction as North (in this case we set North as North), then moving in that direction until an obstacle is met. If there is an obstacle at North, move East. If there is an obstacle at East, move South. If there is an obstacle at South, move West. Keep repeating these steps. Eventually we can reach the centre of the maze. The robot (or person) is also clever enough not to retake the route taken previously if it has returned to the starting point, as in it will ignore the first opening to another route (as it had taken this route in the first try). If it returns to the starting again, it will ignore the first and second routes and repeat the whole process again. How do I prove or if possible improve this algorithm? Much help appreciated, thanks.

Answer 1

1. When first starting, if you can/t move North, then move East. If you can't move East move North, because you can't move South. So your algorithm should account for this situation peculiar to the bottom row. Similar checks should be made for the top row and the two side rows. If you're in the top row, don't consider North as a possibility, etc.

2. If you are going North and meet an obstacle try East and if you meet an obstacle, don't go South and back to the beginning, instead try going West. If you can, do so and then try North. If that is blocked, then return to the beginning.

3. As you travel North at each square indicate whether it is possible to move East or West Use this mark for future reference. Do the same if you are moving in any directon; thatis proceed as far as you can in the current direction, but note each possible turn along the way.

4. If you take a turn and it ends in an obstacle, do not go back to the beginning, instead, just go back to where you made the turn and continue in the direction you were going, unless you know there are no additional turns ahead. If no additional turns ahead go to previous checkpoint.


.

Answer 2

Any n x n maze can be represented by a undirected graph with n*n nodes (each square in the maze is a node, and iff two adjacent squares are not blocked by a wall, their corresponding nodes in the graph share an edge).

To find a path from the an entrance to the maze to the end of the maze we just need to use an algorithm called Depth First Search from the start node to end node on the graph of our maze. Please see the wikipedia entry for a detailed explanation of Depth First Search.

A human executing DFS on this maze would follow these rules whenever he entered any square of the maze (including the entrance square).

1) If this square hasn't been visited yet, mark this square as visited by leaving a note of the path he took from the entrance square to this square (this path can be found adding this square to path noted on the square we just came from).

2) Pick any of the squares connected to this square that hasn't been visited yet and enter that square (it doesn't matter which square we pick, we'll come back to this square later)

3) If all the squares connected to this square have been visited or have been marked "Done." Then mark this square as "Done" and enter the square that goes back to the entrance of the maze. (you can make a recursive argument that we won't mark this square as "Done" until all of the squares connected to it, except the square that goes back to the entrance, are marked "Done", because we cannot return to this square after it has been marked visited unless we are coming from a square marked "Done")

Notice that at any given square, we can't mark it as done until we explore all useful paths that we can take from it (we avoid already explored paths by not entering visited squares). So we won't mark the entrance of the maze as "Done" until all usefull paths from the entrance have been explored, so that if the entrance is connected to the exit, we will visit the exit and find a path through the maze.

Another useful algorithm is Dijkstra's algorithm which will find the shortest path thru the maze.