Trying to create a program that solves mazes, but it is getting stuck in specific paths

Question

So, basically, I'm trying to code a program that solves mazes. I did many tests with different mazes and I realize that my program isn't able to solve all kinds of mazes, only a few, since there some specific dead ends that my program gets stuck and cannot go back.

The logic behind my code is basically something that runs all over the maze until it finds the exit, and, if it finds a dead end during this processes, it should be able to go back and find a new unexplored path.

My code was working well until I start to test it with more complex mazes with different kinds of tricky dead ends. For Example:

maze = (
                [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
                [1,0,1,1,1,0,1,1,1,1,1,1,1,1,1],
                [1,0,0,0,0,0,0,0,1,0,0,0,0,0,1],
                [1,1,1,0,1,1,1,0,1,0,1,0,1,0,1],
                [1,1,1,0,1,0,1,0,1,0,1,1,1,0,1],
                [1,1,1,1,1,0,1,0,1,0,0,1,0,0,1],
                [1,1,0,0,0,0,1,0,1,1,0,1,0,1,1],
                [1,1,0,1,1,0,0,0,0,1,0,1,0,1,1],
                [1,1,0,0,1,1,0,1,0,1,0,1,0,0,1],
                [1,1,0,1,0,0,1,0,0,0,1,0,0,1,1],
                [1,1,1,1,1,1,1,1,1,1,1,3,1,1,1]
                                                )

This an example of a maze with dead ends that my program can solve, whereupon 1 is a wall, 0 is a free path, 3 is the end and the beginning is maze[1][1]

maze = (
                [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
                [1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
                [1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
                [1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
                [1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
                [1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
                [1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
                [1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
                [1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
                [1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
                [1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
                                                )

Now a maze that my program cannot solve. I suppose that the problem with this maze is that it has dead ends with an "L" shape or something like a zigzag, but to be honest, I don't know what is happening. For example, the dead end in maze[5][5] (where my program is stuck)

Before showing the code I want to explain some topics about it:

1. All the strings that I'm printing are in English and in Portuguese, the languages are separated by "/" so don't worry about that.
2. To explore the maze the program uses a recursive strategy and mark with 2 the paths that were explored.
3. The program works with x and y coordinates based on the array. x + 1 goes down, x - 1 goes up, y + 1 goes right and y - 1 goes left.
4. If it gets stuck in a dead end, the strategy is looking at what is around to discover which kind of dead end it is, and then going back until it finds a new path marked with 0.

Those are the cases of dead ends that you will see in my code.

5. If possible I want some tips about how can I improve my code or make it clean.

So, here we go:

maze = (
                [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
                [1,0,0,0,0,0,0,0,0,0,0,0,1,1,1],
                [1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
                [1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
                [1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
                [1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
                [1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
                [1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
                [1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
                [1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
                [1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
                                                )


def solve(x, y):

    if maze[x][y] == 0 or maze[x][y] == 2:
        # To walk around and explore the maze
        print('Visiting/Visitando xy({},{})'.format(x, y))
        maze[x][y] = 2
        if x < (len(maze) - 1) and (maze[x + 1][y] == 0 or maze[x + 1][y] == 3):
            solve(x + 1, y)
        elif y < (len(maze) - 1) and (maze[x][y + 1] == 0 or maze[x][y + 1] == 3):
            solve(x, y + 1)
        elif x > 0 and (maze[x - 1][y] == 0 or maze[x][y + 1] == 3):
            solve(x - 1, y)
        elif y > 0 and (maze[x][y - 1] == 0 or maze[x][y + 1] == 3):
            solve(x, y - 1)

        else:
            # If it gets stuck in a dead end
            step_back = 1
            dead_end = True
            # each possible kind of dead ends and the strategy to go back
            if (maze[x + 1][y] == 1 or maze[x + 1][y] == 2) and maze[x][y - 1] == 1 and \
                    maze[x][y + 1] == 1 and maze[x - 1][y] == 2:

                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x - step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
                        solve(x - step_back, y - 1)
                    elif maze[x - step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
                        solve(x - step_back, y + 1)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x - step_back, y)

            elif (maze[x - 1][y] == 1 or maze[x - 1][y] == 2) and maze[x][y - 1] == 1 and \
                    maze[x][y + 1] == 1 and maze[x + 1][y] == 2:
                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x + step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
                        solve(x + step_back, y - 1)
                    elif maze[x + step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
                        solve(x + step_back, y + 1)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x + step_back, y)

            elif (maze[x][y + 1] == 1 or maze[x][y + 1] == 2) and maze[x + 1][y] == 1 and \
                    maze[x - 1][y] == 1 and maze[x][y - 1] == 2:
                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
                        solve(x - step_back, y)
                    elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
                        solve(x + step_back, y)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x, y + step_back)

            elif (maze[x][y - 1] == 1 or maze[x][y - 1] == 2) and maze[x + 1][y] == 1 and \
                    maze[x - 1][y] == 1 and maze[x][y + 1] == 2:
                print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
                while dead_end is True:
                    if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
                        solve(x - step_back, y)
                    elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
                        solve(x + step_back, y)
                    else:
                        print("Going back/Voltando")
                        dead_end = False
                        step_back += 1
                        solve(x, y - step_back)

    # to check if the end of the maze were found
    if maze[x + 1][y] == 3 or maze[x - 1][y] == 3 or maze[x][y + 1] == 3 or maze[x][y - 1] == 3:
        print('Exit found in/Saída encontrada em xy({},{})'.format(x, y))


solve(1,1)

Answer 1

A simple bfs/dfs is enough to solve this problem. just start from the initial position and keep track of all the nodes that have been covered. If you reach any deadend or if any of the positions is repeated, you can just terminate this path. If you reach the final state, output the current path.

You can find more information about this algorithm here.