Labyrinth optimal 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 without left turns.

The intermediate distance does not matter as long as the right turns are minimized. We are invited to implement our program using the reverse tracking algorithm and the optimal (time) one.

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

• Insert all four possible trigger directions onto the stack.
• Follow the path whenever possible.
• If we get to the end of the maze, return the current path length as the best.
• If we get to the final path back to the last possible turn to the right and take it.
• If the length of the current path is longer than the current, return to the last possible right turn and take it.

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

It’s hard for me to think about something better than returning.

Answer 1

I think you can do this by first finding all the points that are reachable with 0 right turns. Then with just one turn to the right, etc. You can use the queue for this. Note that in the nth phase, you have optimal solutions for all points that can be achieved with n right turns. Moreover, any not yet reached point is reachable by s> n points or not reachable at all. To achieve optimal time complexity, you should use the fact that you need to search for new reach points only from those that have been reached and that have an unreached neighbor in the appropriate direction. Since each item has only 4 neighbors, you will search for it only 4 times. You can implement it by keeping a separate list for each direction D containing all the points reached, with an unreached neighbor in that direction. This gives you temporal complexity proportional to the size of the maze, which is proportional to the size of your input.

Below is 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 

( ) indicates reached points with an inconsistent neighboring neighbor

Answer 2

Create a graph by building four nodes for each position in the maze. Each node corresponds to a specific direction: N, S, E, W.

Between each node and no more than three neighboring neighbors there will be edges: one - "front", "back" and "right" (if they exist). The edge leading to the node in the front and back will have a weight of 0 (since the path length does not matter), while the edge to the node in the right will have a weight of 1 (this is what the cost of the correct turning).

Once the graph is set up (and probably the best way to do this is to reuse the original maze view), the modified widthth option — the first search algorithm will solve the problem.

The trick for handling 0/1 edge weights is to use deque instead of the standard queue implementation. In particular, nodes that have reached up to 0 weight edges will be pushed in front of the deck, and those reached through the edges of weight 1 will be shifted to the back.