Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have covered the topic on finding the Shortest path in a Maze using Backtracking. We have presented the Time and Space Complexity for various cases.
Table of contents:
- Introduction to Backtracking Algorithm
- Finding the Shortest path in a Maze using Backtracking
- Time and Space Complexity
- Conclusion
Introduction to Backtracking Algorithm
Backtracking is a depth-first search algorithm used to find all possible solutions to a problem by building a solution incrementally and then undoing (backtracking) the last step if the solution is invalid. This process is repeated until a valid solution is discovered, or all possibilities are exhausted. Backtracking is frequently used in obtaining the solution of problems such as the N-Queens problem and Sudoku.
Finding the Shortest path in a Maze using Backtracking
from os import environ
import sys
environ['PYGAME_HIDE_SUPPORT_PROMPT'] = '1'
import pygame
import copy
from queue import Queue
import random
We first imports the essential libraries and creates the environment for the Pygame library to function properly.
We will be making use of the Pygame library, which is used in Python to create games and graphical applications to generate the GUI for our maze solver program.
def shortest_path(maze, start, end):
rows = len(maze)
cols = len(maze[0])
This function accepts a maze represented as a 2D list of 0's and 1's, as well as the maze's starting and ending positions. It begins by determining the number of rows and columns in the maze.
def find_path(row, col, length, path):
if row == end[0] and col == end[1]:
return length, path + [(row, col)]
if maze[row][col] == 1:
return float('inf'), None
maze[row][col] = 1
path.append((row, col))
The function find_path is used to recursively explore all possible paths between the starting and ending positions. It takes in the current row and column position in the maze, the length of the path up to the current position, and the current path represented as a list of tuples.
The first if statement determines whether the current position is the ending position, in which case the length of the path and the entire path up to the ending position are returned. The path is returned as a list of tuples, with each tuple representing one of the maze's positions.
The second if statement determines whether the current position is a wall, which is represented by the value 1 in the maze list. If this is the case, it returns a large value (infinity) for the length and None for the path, indicating that the path is invalid.
The function then marks the current position in the maze as visited by setting it to 1 and adding it to the path list.
min_length = float('inf')
min_path = None
if row > 0:
l, p = find_path(row-1, col, length+1, path)
if l < min_length:
min_length = l
min_path = p
if row < rows-1:
l, p = find_path(row+1, col, length+1, path)
if l < min_length:
min_length = l
min_path = p
if col > 0:
l, p = find_path(row, col-1, length+1, path)
if l < min_length:
min_length = l
min_path = p
if col < cols-1:
l, p = find_path(row, col+1, length+1, path)
if l < min_length:
min_length = l
min_path = p
The function then explores all possible directions from the current position by calling the find_path function recursively for each neighboring position. The function calculates the length of the path to the new position for each neighboring position by adding 1 to the current length, and appends the new position to the path list.
If the path to the new position is shorter than the current minimum length found so far, the function updates the minimum length and the path to the minimum path found.
path.pop()
maze[row][col] = 0
return min_length, min_path
Finally, after exploring all possible directions from the current position, the function returns to the previous step by removing the current position from the path list and marking the cell as unvisited. The minimum length and shortest path found among all possible paths from the starting position to the ending position are then returned.
min_length, path = find_path(start[0], start[1], 0, [])
return min_length, path
The shortest_path function then invokes the find_path function, passing it the starting row and column positions, a length of 0, and an empty path list. The minimum length and complete path to the ending position are then returned.
The function works by recursively exploring all possible paths from the starting position to the ending position in the maze. For each position in the maze, the function calculates the length of the path up to the current position, and updates the minimum length and path found so far if a shorter path is found. The function continues to explore all possible paths from the current position, and backtracks when it reaches a dead end or has explored all possible paths from the current position.
def generate_maze(M, entry, exit):
The generate_maze function accepts three arguments: M, entry and exit.
M denotes the number of rows and columns in a square maze, while entry and exit denote the entry and exit column indices.
# Create the maze grid with all walls intact
maze = [[1 for j in range(M)] for i in range(M)]
# Mark the entry and exit points as visited
maze[0][entry] = 0
maze[M-1][exit] = 0
We then Create a M x M square maze filled with 1s, using 1 to represent a blocked cell.
Next we set the maze's entry point (top row, column entry) and exit point (bottom row, column exit) to 0, which represents a free cell(path).
# Recursively explore the maze
explore_maze(maze, 0, entry)
Next we call the explore_maze function with three arguments: maze, 0 and entry.
We use this function's to create a path through the maze from the entry point to the exit point.
# Check if there is a valid path from entry to exit
if not check_valid_path(maze, entry, exit):
return generate_maze(M, entry, exit)
return maze
We then determines whether a valid path exists in the maze from the entry point to the exit point. This is accomplished by calling the check_valid_path function with three parameters: maze, entry, and exit. If no valid path is found, the function recursively calls itself with the same arguments until a valid maze is generated. Backtracking is a common technique in maze generation algorithms. Once the program have a valid path from entry to exit, it will return the maze.
def explore_maze(maze, i, j):
The function explore_maze accept three arguments: maze (the 2D list representing the maze), i (the current position's row index), and j. (the column index of the current position).
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
Next it generates a list of four tuples, each of which represents a direction to move from the current position. Each tuple has two elements: the change in row index and the change in column index. Right, down, left, and up are the four directions represented.
random.shuffle(directions)
We then randomly shuffles the list of directions. This ensures that the algorithm does not always explore the maze in the same order, resulting in a less predictable maze.
for d_i, d_j in directions:
new_i, new_j = i + 2*d_i, j + 2*d_j
if 0 < new_i < len(maze) and 0 < new_j < len(maze[0]):
if maze[new_i][new_j] == 1:
maze[i+d_i][j+d_j] = 0
maze[new_i][new_j] = 0
explore_maze(maze, new_i, new_j)
The program then loops through the shuffled list of directions. It computes the new row and column indices of the position that would be reached by moving in that direction for each direction (i.e., two cells away from the current position). If the new position is within the maze's bounds and has a value of 1 (indicating a wall), the function "knocks down" the wall between the current and new positions by setting the values of the two cells between them to 0. It then calls itself recursively with the new position as the current position, continuing the maze exploration from there.
To explore the maze and create a path from the entry point to the exit point, this function employs a depth-first search algorithm. By randomly shuffling our directions, we ensures that the order of exploration is random, resulting in more varied and interesting mazes.
def check_valid_path(maze, entry, exit):
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
The check_valid_path function accepts three arguments: maze (the 2D list representing the maze), entry (the entry point's column index), and exit (the column index of the exit point).
Next it generates a list of four tuples, each of which represents a movement direction from the current position. Each tuple has two elements: the change in row index and the change in column index. The four directions are the same as in the explore_maze function: right, down, left, and up.
q = Queue()
q.put((0, entry))
This creates an instance of the Queue class from the queue module and adds the starting position (0, entry) to the queue. The first element represents the row index, which is 0 because the entry point is in the maze's top row.
visited = set()
visited.add((0, entry))
This adds the starting position to an empty set called visited. To avoid revisiting positions that have already been visited during the search, this set will keep track of them.
while not q.empty():
i, j = q.get()
The while loop dequeues positions from the queue q one at a time, assigning row and column indices to i and j. The loop is repeated until the queue is clear.
if i == len(maze)-1 and j == exit:
return True
Next the program determines whether or not the present position is the exit point. If it is, then a valid route from the entry point to the exit point has been determined, and the function returns True.
for d_i, d_j in directions:
new_i, new_j = i + d_i, j + d_j
if 0 <= new_i < len(maze) and 0 <= new_j < len(maze[0]) and (new_i, new_j) not in visited and maze[new_i][new_j] == 0:
visited.add((new_i, new_j))
q.put((new_i, new_j))
The for loop iterates through the four directions, determining whether the new location obtained after moving in that direction is a valid position to move to. If the new location is within the maze's bounds, hasn't been visited before, and isn't a wall (i.e., has a value of 0), it is added to the visited set and enqueued to the q queue. This continues the search for a valid path.
return False
The function returns False if the search fails to find a valid path from the entry point to the exit point.
We used a breadth-first search algorithm to determine whether a valid path exists in the maze from the entry point to the exit point. It keeps track of the positions to visit in a queue and the positions already visited in a set. The search will continue until the queue is empty or an exit point is discovered.
def animate_path(maze, path):
The animate_path function takes in two arguments: maze (the 2D list representing the maze) and path (a list of tuples representing the coordinates of the path from the entry point to the exit point).
pygame.init()
clock = pygame.time.Clock()
Next we initialize the Pygame library and create a Clock object for keeping track of time.
size = len(maze)*20
screen = pygame.display.set_mode((size, size))
pygame.display.set_caption("Maze Animation")
we then setup the Pygame window to display the maze animation. The size variable is calculated by multiplying the length of one side of the maze by 20. (each cell in the maze is displayed as a 20x20 rectangle). The display module's set_mode method generates a Pygame window of the specified size. We use the set_caption method to change the window's title.
white = (255, 255, 255)
black = (0, 0, 0)
red = (255, 0, 0)
The above define RGB color values for white, black, and red colors, respectively.
for i in range(len(maze)):
for j in range(len(maze[i])):
if maze[i][j] == 1:
pygame.draw.rect(screen, black, (j*20, i*20, 20, 20))
else:
pygame.draw.rect(screen, white, (j*20, i*20, 20, 20))
These nested loops iterate through the maze, drawing a rectangle in the Pygame window to represent each cell. The rectangle is drawn in black if the cell has a value of 1 (representing a wall) and white if the cell has a value of 0 (representing a path).
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
pygame.quit()
sys.exit()
for point in path:
pygame.draw.rect(screen, red, (point[1]*20, point[0]*20, 20, 20))
pygame.display.update()
clock.tick(25) #run the loop X tick(s) per second, higher number is faster
The while loop will be repeated until the user closes the Pygame window. The for loop inside the while loop iterates through the path list, drawing a rectangle in the Pygame window to represent each point. The rectangle is highlighted in red. The display.update method adds the new rectangle and clock to the Pygame window. To control the animation speed, we set the clock.tick() value.
if __name__ == "__main__":
maze_size = input("Input the size of the maze? Range from 10 to 40: ")
try:
maze_size = (int(maze_size)//2)*2
except ValueError:
print("This is not a number")
sys.exit()
The code contained within this block will only be executed if the script is run directly.
The program request that the user enter the maze's size, which must be an even integer between 10 and 40. To ensure that the resulting maze size is even, the input is converted to an integer, divided by 2, and rounded down. It will print an error message and the program will exit if the input is not a valid integer.
if maze_size < 10:
maze_size = 10
elif maze_size > 40:
maze_size = 40
maze_entry = int(maze_size*0.15)
maze_exit = int(maze_size*0.85)
It then check to see if the maze size is less than 10 or greater than 40, and if it is, the program will set the maze size to the closest valid value (either 10 or 40). Next we compute the row index of the maze's entry and exit points. The entry point value is set as 15% of the maze's size, and the exit point value is set as 85% of the maze's size.
maze = generate_maze(maze_size, maze_entry, maze_exit)
animate_maze = copy.deepcopy(maze)
start = (0, maze_entry)
end = (maze_size-1, maze_exit)
min_length, path = shortest_path(maze, start, end)
print(f"Minimum Path Length: {min_length}")
animate_path(animate_maze, path)
Here the program generate a maze of the specified size with the previously calculated entry and exit points. The shortest_path function is used to determine the shortest path length and path from the entry point to the exit point. The animate_path function is used to animate the path.
Time and Space Complexity
Time Complexity: The algorithm has a time complexity of O(4^(M*N)), where M is the number of rows and N is the number of columns in the maze. At each point in the maze, the algorithm has the option of moving in four directions (up, down, left, or right). It must explore all possible paths through the maze to find the shortest one, which is 4^(M*N).
Space Complexity: The algorithm has a space complexity of O(M*N) because it uses a recursive function call stack to keep track of the current path and can move in four directions at each point in the maze. The maximum size of the call stack is the number of total points in the maze, which is M*N.
Conclusion
We can consider using Breadth-first search (BFS) algorithm as an alternative approach which perform better in the Time Complexity area.
With this article at OpenGenus, you must have the complete idea of finding the Shortest path in a Maze using Backtracking.
