Maze Solver in Python
Intermediate · Logic and puzzles · about 60 minutes to build · 148 lines
Solve the example maze or a new random one and see the shortest path from S to E drawn in dots.
The program
Press Run and answer its questions in the box that appears under the code.
maze_solver.py
"""Maze solver: find the shortest way from S to E with breadth-first search."""
import random
from collections import deque
WALL, OPEN, START, END, PATH = "#", " ", "S", "E", "."
STEPS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
MIN_ROOMS, MAX_ROOMS = 3, 10
EXAMPLE = [
"###############",
"#S # #",
"# ### # ##### #",
"# # # # #",
"# # ##### # # #",
"# # # # #",
"# ### ####### #",
"# E#",
"###############",
]
# --- Making a random maze ---
def carve(rooms):
"""Carve a square maze with exactly one way between any two rooms."""
size = 2 * rooms + 1 # rooms sit at odd rows and columns, walls between
grid = [[WALL] * size for _ in range(size)]
grid[1][1] = OPEN
stack = [(1, 1)]
while stack: # walk randomly, knocking down walls; back up at dead ends
row, col = stack[-1]
nexts = [(row + 2 * dr, col + 2 * dc) for dr, dc in STEPS
if 0 < row + 2 * dr < size and 0 < col + 2 * dc < size
and grid[row + 2 * dr][col + 2 * dc] == WALL]
if not nexts:
stack.pop()
continue
r, c = random.choice(nexts)
grid[(row + r) // 2][(col + c) // 2] = OPEN # the wall in between
grid[r][c] = OPEN
stack.append((r, c))
return grid
def random_maze(rooms):
"""Make a random maze with a few extra gaps, so some routes are shorter."""
grid = carve(rooms)
size = len(grid)
for _ in range(rooms):
r, c = random.randrange(1, size - 1), random.randrange(1, size - 1)
if (r + c) % 2 == 1: # a wall between two rooms
grid[r][c] = OPEN
grid[1][1], grid[size - 2][size - 2] = START, END
return ["".join(row) for row in grid]
# --- Solving with breadth-first search ---
def find(maze, char):
"""Return the (row, col) of a character in the maze."""
for row, line in enumerate(maze):
if char in line:
return row, line.index(char)
return None
def neighbours(maze, cell):
"""Yield the open cells next to this one."""
row, col = cell
for dr, dc in STEPS:
r, c = row + dr, col + dc
if 0 <= r < len(maze) and 0 <= c < len(maze[r]) and maze[r][c] != WALL:
yield r, c
def solve(maze):
"""Return the shortest path from S to E (or None) and cells explored."""
start, end = find(maze, START), find(maze, END)
came_from = {start: None} # each cell remembers where we reached it from
queue = deque([start])
while queue:
cell = queue.popleft() # oldest first, so we explore in rings
if cell == end:
break
for nxt in neighbours(maze, cell):
if nxt not in came_from:
came_from[nxt] = cell
queue.append(nxt)
if end not in came_from:
return None, len(came_from)
path, cell = [], end
while cell is not None: # walk back from E to S
path.append(cell)
cell = came_from[cell]
return path[::-1], len(came_from)
# --- Showing the result ---
def draw_path(maze, path):
"""Return a copy of the maze with the path drawn in dots."""
grid = [list(line) for line in maze]
for row, col in path[1:-1]: # keep S and E as they are
grid[row][col] = PATH
return ["".join(row) for row in grid]
def solve_and_show(maze):
"""Solve a maze and print it next to the solved version."""
path, explored = solve(maze)
if path is None:
print(f"There is no way from S to E ({explored} cells explored).")
return
width = max(len(line) for line in maze)
print(f"\n{'Maze':<{width}} Solved")
for left, right in zip(maze, draw_path(maze, path)):
print(f"{left:<{width}} {right}")
print(f"Shortest path: {len(path) - 1} steps. Cells explored: {explored}.")
def ask_rooms():
"""Ask how many rooms across the random maze should be."""
while True:
answer = input(f"Rooms across ({MIN_ROOMS}-{MAX_ROOMS}): ").strip()
if answer.isdecimal() and MIN_ROOMS <= int(answer) <= MAX_ROOMS:
return int(answer)
print(f"Please type a whole number from {MIN_ROOMS} to {MAX_ROOMS}.")
def main():
"""Show the menu until the user quits."""
print("Maze solver")
while True:
print("\n1) Solve the example maze 2) Solve a random maze 3) Quit")
choice = input("Choose 1-3: ").strip()
if choice == "1":
solve_and_show(EXAMPLE)
elif choice == "2":
solve_and_show(random_maze(ask_rooms()))
elif choice == "3":
print("Goodbye.")
break
else:
print("Please type 1, 2 or 3.")
if __name__ == "__main__":
main()
Open it in the full editor to save it, share it and keep building.
Sample run
What the program printed, and what was typed (in yellow).
Maze solver 1) Solve the example maze 2) Solve a random maze 3) Quit Choose 1-3: 1 Maze Solved ############### ############### #S # # #S # # # ### # ##### # #.### # ##### # # # # # # #. # # # # # # ##### # # # #.# ##### # # # # # # # # #.# # # # # ### ####### # #.### ####### # # E# #............E# ############### ############### Shortest path: 18 steps. Cells explored: 50. 1) Solve the example maze 2) Solve a random maze 3) Quit Choose 1-3: 2 Rooms across (3-10): big Please type a whole number from 3 to 10. Rooms across (3-10): 6 Maze Solved ############# ############# #S # # #S..# ... # ### # # # # # ###.# #.#.# # # # # # # # #...# #.#.# # # ### # # # # #.### #.#.# # # # # # # # #.# #.#.# # # # ### # # # #.# ###.#.# # # # # # # #.# #...#. # # ### ### ### #.###.###.### # # # # #.....# #...# ####### ### # ####### ###.# # E# # E# ############# ############# Shortest path: 40 steps. Cells explored: 60. 1) Solve the example maze 2) Solve a random maze 3) Quit Choose 1-3: 3 Goodbye.
How it is built
1. The maze as text
A maze is a list of strings: # is a wall, a space is open, S is the start and E the end. A cell is a (row, col) pair, and maze[row][col] tells you what is there.
WALL, OPEN, START, END, PATH = "#", " ", "S", "E", "." STEPS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right MIN_ROOMS, MAX_ROOMS = 3, 10 EXAMPLE = [ "###############", "#S # #", "# ### # ##### #", "# # # # #", "# # ##### # # #", "# # # # #", "# ### ####### #", "# E#", "###############", ]
2. Carving a random maze
Rooms sit at odd rows and columns with walls between them. The loop walks from room to room in random order, knocking down the wall it passes through, and backs up along stack at dead ends. This is depth-first search, and it makes a maze with exactly one way between any two rooms.
def carve(rooms): """Carve a square maze with exactly one way between any two rooms.""" size = 2 * rooms + 1 # rooms sit at odd rows and columns, walls between grid = [[WALL] * size for _ in range(size)] grid[1][1] = OPEN stack = [(1, 1)] while stack: # walk randomly, knocking down walls; back up at dead ends row, col = stack[-1] nexts = [(row + 2 * dr, col + 2 * dc) for dr, dc in STEPS if 0 < row + 2 * dr < size and 0 < col + 2 * dc < size and grid[row + 2 * dr][col + 2 * dc] == WALL] if not nexts: stack.pop() continue r, c = random.choice(nexts) grid[(row + r) // 2][(col + c) // 2] = OPEN # the wall in between grid[r][c] = OPEN stack.append((r, c)) return grid
3. Making shortcuts
With only one route, the shortest path would be the only path, so a few walls between rooms are knocked out at random to make loops. A wall between two rooms always has an odd row plus column.
def random_maze(rooms): """Make a random maze with a few extra gaps, so some routes are shorter.""" grid = carve(rooms) size = len(grid) for _ in range(rooms): r, c = random.randrange(1, size - 1), random.randrange(1, size - 1) if (r + c) % 2 == 1: # a wall between two rooms grid[r][c] = OPEN grid[1][1], grid[size - 2][size - 2] = START, END return ["".join(row) for row in grid]
4. Open neighbours
yield hands back the open cells next to a cell one at a time; cells off the edge or inside a wall are skipped.
def neighbours(maze, cell): """Yield the open cells next to this one.""" row, col = cell for dr, dc in STEPS: r, c = row + dr, col + dc if 0 <= r < len(maze) and 0 <= c < len(maze[r]) and maze[r][c] != WALL: yield r, c
5. Breadth-first search
The queue starts with S. Each step takes the oldest cell from the front with popleft() and adds its unvisited neighbours to the back, so cells are explored in rings by distance from S, and the first route that reaches E is the shortest. came_from remembers how each cell was reached, and following it back from E gives the path.
def solve(maze): """Return the shortest path from S to E (or None) and cells explored.""" start, end = find(maze, START), find(maze, END) came_from = {start: None} # each cell remembers where we reached it from queue = deque([start]) while queue: cell = queue.popleft() # oldest first, so we explore in rings if cell == end: break for nxt in neighbours(maze, cell): if nxt not in came_from: came_from[nxt] = cell queue.append(nxt) if end not in came_from: return None, len(came_from) path, cell = [], end while cell is not None: # walk back from E to S path.append(cell) cell = came_from[cell] return path[::-1], len(came_from)
6. Drawing the path
Strings cannot be changed, so each line is copied into a list. Every cell on the path except S and E becomes a dot, and the lists are joined back into strings.
def draw_path(maze, path): """Return a copy of the maze with the path drawn in dots.""" grid = [list(line) for line in maze] for row, col in path[1:-1]: # keep S and E as they are grid[row][col] = PATH return ["".join(row) for row in grid]
Make it bigger
- Let the player type their own maze line by line, then solve it.
- Use a list as a stack instead of the deque and compare: depth-first search finds a path, but not always the shortest.
- Print each open cell's distance from S to see the rings breadth-first search explores.
- Add mud cells that cost 3 steps and solve with Dijkstra's algorithm and heapq.
What it practises
- breadth-first search
- collections.deque
- dictionaries
- generators with yield
- depth-first search