Python Implementation of a Maze Solving Algorithm

Document 对象参考手册Python3 Example

We will use the depth-first search (DFS) algorithm to solve a simple maze problem. The maze is represented by a two-dimensional array, where0represents a passable path,1represents a wall,2represents the starting point,3represents the ending point. We will start from the starting point and attempt to find a path to the ending point.

Example

def solve_maze(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    path = []

    def dfs(x, y):
        if x = rows or y = cols or maze[x][y] == 1 or visited[x][y]:
            return False
        visited[x][y] = True
        path.append((x, y))
        if (x, y) == end:
            return True
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if dfs(x + dx, y + dy):
                return True
        path.pop()
        return False

    if dfs(start[0], start[1]):
        return path
    else:
        return None

# Example maze
maze = [
    [2, 0, 1, 0, 0],
    [1, 0, 1, 0, 1],
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 1],
    [0, 0, 0, 0, 3]
]

start = (0, 0)
end = (4, 4)
result = solve_maze(maze, start, end)
print(result)

Code analysis:

  1. solve_mazeThe function accepts the maze, starting point, and ending point as parameters.
  2. visitedis a two-dimensional array used to record which positions have been visited, avoiding repeated visits.
  3. pathis a list used to store the path from the starting point to the ending point.
  4. dfsis a recursive function used for depth-first search. It first checks whether the current position is out of bounds, is a wall, or has already been visited. If these conditions are met, it returnsFalse。
  5. If the current position is the ending point, it returnsTrue, indicating that a path has been found.
  6. For the four directions of the current position (up, down, left, right), recursively calldfsfunction. If a path is found, returnTrue。
  7. If all directions have been tried but no path is found, then frompathremove the current position from it, and returnFalse。
  8. Finally, ifdfsfunction returnsTrue, then returnpath, otherwise returnNone。

Output result:

[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]

This result represents from the starting point(0, 0)to the ending point(4, 4)path.

Document 对象参考手册Python3 Example

Other extensions