Algorithm optimization

I was watching this maze page solve itself (press the solve button) when optimization came to mind.  You see, this maze solver seems to be brute forcing a solution by always turning left (initially) until the last turn results in a dead end.  It then backs up to the last turn and tries the next turn in the sequence (left, straight, right).  The technique mentioned is pretty good for mazes and there seems to be nothing one can do to speed it up but there are a few cases that one can do to aid in selecting what turn to make.

For instance, if one knows what direction they’re heading in (known), start and end points (known), and the height and width of the maze (known) then a quick and easy optimization is to determine if one has reached the top of the maze and also if one has reached the bottom (or has one reached left and has one reached right).  By knowing if you have reached the top and bottom in the same traversal then one knows that any bottom turns must be towards the exit.  No solution will exist where you must backtrack all the way back past the top point and then turn right (you’ve cut off a portion of the maze).  In essense you are starting a new maze with the top point the new start (yes you may be able to move left slightly up to the bottom most touch point but not past it).  The same goes for left and right boundaries with reference to upwards and downwards movement.

This is a very small optimization but it can save a tremendous amount of time chasing a dead end.  Basically, if you reach the bottom of the map and you are in a path that has reached the top don’t take a turn away from the goal.  If no turn towards the goal exists at the bottom then backtrack to the last turn that allows a turn towards the goal (end point).

Such small benefits are what keep programmers up all night.