Maze solving optimal no left turn algorithm

Question

I am working on a project where I need to solve a maze using the minimum number of right turns and no left turns.

The distance travelled is irrelevant as long as right turns are minimized. We are asked to implement our program using both a backtracking algorithm and an optimal (time) one.

For the backtracking algorithm I was going use a stack. My algorithm would be something like:

• Push all four possible starting directions on the stack.
• Follow a path, going straight whenever possible.
• If we reach the end of the maze return the current path length as the best.
• If we reach a dead end backtrack to the last possible right turn and take it.
• If the current path length is greater than the current best, backtrack to the last possible right turn and take it.

I was wondering if anyone could point me in the direction of an optimal algorithm for this.

I'm having a tough time thinking of anything better than the backtracking one.

Answer 1

I think you can do it by first finding all the points that are reachable with 0 right turns. Then with just 1 right turn, and so on. You can use a queue for doing that. Note that in the n-th phase you've got optimal solutions for all the points that can be reached with n right turns. More so - any not yet reached point is reachable with > n points or not reachable at all. In order to achieve optimal time complexity you have to use the fact that you need to search for new reachable points only from those reached points, which have an unreached neighbour in the appropriate direction. As every point has only 4 neighbours you will only search from it 4 times. You can implement it by maintaining a separate list for every direction D containing all the reached points with an unreached neighbour in that direction. This gives you a time complexity proportional to the area of the maze that is proportional to the size of your input data.

Below I present a graphical example:

 .  .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1 (1)   0  1  1  1  1  1
 .  #######  .  .    0  ##########  .    0  ##########  .    0  ##########  2
 .  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  . (2)
 .  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  . (2)
 .  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  2
(.) .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1  1    0  1  1  1  1  1

 0  1  1  1  1  1    0  1  1  1  1  1
 0  ##########  2    0  ##########  2
 0  #  .  #  3  2    0  #  4  #  3  2
 0  # (3) 3  3  2    0  #  3  3  3  2
 0  ####  .  #  2    0  ####  4  #  2
 0  1  1 (1) 1  1    0  1  1  1  1  1

( ) denote reached points with the appropriate neighbour unreached

Answer 2

Build a graph by constructing four nodes for every position in the maze. Every node will correspond to a particular direction: N, S, E, W.

There will be edges between every node and at most three of its adjacent neighbors: the ones to the "front", "back" and "right" (if they exist). The edge leading to the node in the "front" and "back" will have weight 0 (since the path length doesn't matter), whereas the edge to the node in the "right" will have weight 1 (this is what represents the cost of making a right turn).

Once the graph is set up (and probably the best way to do this is to reuse the original representation of the maze) a modified variant of the breadth-first search algorithm will solve the problem.

The trick to handle the 0/1 edge weights is to use a deque instead of the standard queue implementation. Specifically, nodes reached through 0 weight edges will be pushed in the front of the deque and the ones reached through edges of weight 1 will be pushed in the back.