Fun with Python #2: Rat in a Maze

Welcome to “Fun with Python”, part 2. In this part, we will take a closer look at backtracking by attempting to solve the Rat in a maze problem.

Theory and Foundations

First, we need to explain what backtracking is. The official definition is:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

In other words, backtracking is an recursive technique, which attempts to solve problems by assuming parts of the solution. After the first part of the solution is assumed, then we move on by assuming the second part of the solution and so on. If we are lucky, all the assumptions we made form a complete solution and the problem is solved.

On the other hand, if the chosen path does not return a solution, then we backtrack. This means that we “undo”the latest part of the solution we have assumed and we try another. This goes on until we find a solution, or try all possibilities and see that a solution does not exist.

In the previous part, we wrote a script that generate mazes by using Randomized Prim’s algorithm. In this part, we will take one of the mazes we created in the previous part and try to solve it using backtrack.

Without loss of generality, we assume that we know the entrance and the exit of the maze. We will start at the entrance. We will make a move towards a direction, as long as it is not a wall. The new cell we are on, we will add to a path list. We will keep moving until we either find the exit, we we get to a dead end. If our solution leads to a dead end, we will remove from the path list the last cell we walked on and try the next possible one.

Implementation

First, we need a maze. We will use one, generated from the previous part. Let’s assume that we have generated the maze below:

The generated maze we will try to solve

This maze we need to move to a variable. We will use a list of lists. Let’s call this list maze .

maze = [
    ['w', 'c', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w',
     'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w'],
    ['w', 'c', 'c', 'w', 'c', 'w', 'c', 'c', 'w', 'w', 'c', 'c', 'c', 'c',
     'c', 'w', 'w', 'c', 'w', 'w', 'c', 'c', 'c', 'c', 'c', 'c', 'w'],
    ['w', 'w', 'c', 'w', 'c', 'c', 'c', 'w', 'w', 'w', 'w', 'w', 'w', 'w',
     'c', 'c', 'c', 'c', 'c', 'w', 'w', 'w', 'w', 'w', 'w', 'c', 'w'],
                     .       .       .
    

    ['w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w',
     'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'w', 'c', 'w']
]

In order to keep things simple, we will use a maze that has a possible solution. There is an entrance and also there is an exit. We will use these two points later on. We will automate the process of locating them.

def get_starting_finishing_points():
    _start = [i for i in range(len(maze[0])) if maze[0][i] == 'c']
    _end = [i for i in range(len(maze[0])) if maze[len(maze)-1][i] == 'c']
    return [0, _start[0]], [len(maze) - 1, _end[0]]

The method above will return the entrance and the exit of the maze. We will call it as so:

start, finish = get_starting_finishing_points()

Here we can take a closer look at two of Python’s features:

1. We have not passed variable maze as an argument in the get_starting_finishing_points function. Still, we can access this variable inside the function. This is because of the list type mutability.
2. We are able to return multiple values via the function’s return statement, due to tuple unpacking Python is offering.

But more on these topics will follow in the future.

We will also use the function we created in the previous part that prints the maze. In this case we need to print the path of the rat, so we need to make a small modification to the function:

from colorama import Fore, init

def print_maze():
    for i in range(0, len(maze)):
        for j in range(0, len(maze[0])):
            if maze[i][j] == 'u':
                print(Fore.WHITE, f'{maze[i][j]}', end=" ")
            elif maze[i][j] == 'c':
                print(Fore.GREEN, f'{maze[i][j]}', end=" ")
            elif maze[i][j] == 'p':
                print(Fore.BLUE, f'{maze[i][j]}', end=" ")
            else:
                print(Fore.RED, f'{maze[i][j]}', end=" ")
        print('\n')

We have the standard wall, cell and unvisited, but now we also have path which denotes the rat’s path. We will use p for that. We are changing the letter in the list of the maze, so we do not go to a cell we have already visited and have marked as a part of the maze.

Now that we have our helper functions ready, we will change the status of the first cell and then add the the coordinates of this cell to a rat_path list. This list will contain the path of the rat.

maze[start[0]][start[1]] = 'p'

rat_path = [start]

And now we are ready to tackle our backtracking function. As stated in the theory section above, we will implement a recursive function. In this function we will retrieve the current cell of our rat. We will check if we can go downwards, and if we do, we will add the cell below us to the rat_path list and then call the recursive function again:

def escape():
    current_cell = rat_path[len(rat_path) - 1]
    if maze[current_cell[0] + 1][current_cell[1]] == 'c':
        maze[current_cell[0] + 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] + 1, current_cell[1]])
        escape()

Let’s explain this piece of code. If the below us index is a cell, then we set this as a path in the maze and then we add this cell in the rat path. Now we call the escape function again. This time the current_cell will be the one we decided to move to in the previous function call, so now we will check if we can visit the index below that and so on. Of course, we can move to 4 directions, so let’s add them.

def escape():
    current_cell = rat_path[len(rat_path) - 1]
    if maze[current_cell[0] + 1][current_cell[1]] == 'c':
        maze[current_cell[0] + 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] + 1, current_cell[1]])
        escape()
    if maze[current_cell[0]][current_cell[1] + 1] == 'c':
        maze[current_cell[0]][current_cell[1] + 1] = 'p'
        rat_path.append([current_cell[0], current_cell[1] + 1])
        escape()

    if maze[current_cell[0] - 1][current_cell[1]] == 'c':
        maze[current_cell[0] - 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] - 1, current_cell[1]])
        escape()

    if maze[current_cell[0]][current_cell[1] - 1] == 'c':
        maze[current_cell[0]][current_cell[1] - 1] = 'p'
        rat_path.append([current_cell[0], current_cell[1] - 1])
        escape()

Imagine now, that we keep following a path, and at some point, we meet a dead end. What does this mean? It means that we have checked all 4 cases and none of them is satisfied. We are surrounded by walls in front of us and behind us we have the path. So now we need to backtrack, we need to undo the last action we made:

def escape():
    current_cell = rat_path[len(rat_path) - 1]
    if maze[current_cell[0] + 1][current_cell[1]] == 'c':
        maze[current_cell[0] + 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] + 1, current_cell[1]])
        escape()
    if maze[current_cell[0]][current_cell[1] + 1] == 'c':
        maze[current_cell[0]][current_cell[1] + 1] = 'p'
        rat_path.append([current_cell[0], current_cell[1] + 1])
        escape()

    if maze[current_cell[0] - 1][current_cell[1]] == 'c':
        maze[current_cell[0] - 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] - 1, current_cell[1]])
        escape()

    if maze[current_cell[0]][current_cell[1] - 1] == 'c':
        maze[current_cell[0]][current_cell[1] - 1] = 'p'
        rat_path.append([current_cell[0], current_cell[1] - 1])
        escape()

    cell_to_remove = rat_path[len(rat_path) - 1]
    rat_path.remove(cell_to_remove)
    maze[cell_to_remove[0]][cell_to_remove[1]] = 'c'

What we do is, we take the last item inserted in our rat_path list and we remove it. Also, we set the cell to empty again.

When are we done? When the current cell is equal to the finish. Of course, in the piece of code that takes care of the backtracking we need to check if the current cell is the finish, so that we do not remove it from our list.

def escape():
    current_cell = rat_path[len(rat_path) - 1]
    if current_cell == finish:
        return
    if maze[current_cell[0] + 1][current_cell[1]] == 'c':
        maze[current_cell[0] + 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] + 1, current_cell[1]])
        escape()
    if maze[current_cell[0]][current_cell[1] + 1] == 'c':
        maze[current_cell[0]][current_cell[1] + 1] = 'p'
        rat_path.append([current_cell[0], current_cell[1] + 1])
        escape()

    if maze[current_cell[0] - 1][current_cell[1]] == 'c':
        maze[current_cell[0] - 1][current_cell[1]] = 'p'
        rat_path.append([current_cell[0] - 1, current_cell[1]])
        escape()

    if maze[current_cell[0]][current_cell[1] - 1] == 'c':
        maze[current_cell[0]][current_cell[1] - 1] = 'p'
        rat_path.append([current_cell[0], current_cell[1] - 1])
        escape()

    current_cell = rat_path[len(rat_path) - 1]
    if current_cell != finish:   
        cell_to_remove = rat_path[len(rat_path) - 1]
        rat_path.remove(cell_to_remove)
        maze[cell_to_remove[0]][cell_to_remove[1]] = 'c'

And this concludes our backtracking function. If everything is done correctly, we should get a solution to our maze. Let’s test it!

Putting it all together

The main code for this problem is pretty simple:

if __name__ == '__main__':
    start, finish = get_starting_finishing_points()
    maze[start[0]][start[1]] = 'p'

    rat_path = [start]
    escape()
    print_maze()

By running it for the maze we presented above, we get the following output:

Maze solved!

You can see with blue, the path towards the maze exit.

In this maze, there was only one solution possible. So, our algorithm return only one solution. If we had multiple paths towards the exit, the backtracking algorithm would find all the possible solutions to the problem! Try editing the maze so that multiple solutions are feasible and let me know what you find.

The full functional code can be found here.

I hope you enjoyed the article and try it yourself. In the meanwhile, you can find the rest of the “Fun with Python” series here.