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.
2007-06-30
05:36:20
·
2 answers
·
asked by
whatagowk
2