Maze solving (backtracking)

Find a way from the top-left to the bottom-right corner: go forward, and at every dead end mark it and back up.

The maze is a table: 0 is an open cell and 1 a wall. Start at the top-left corner and try right, down, left and up in turn:

Input:

A 5×5 maze; the branch on the right is tried first and hits a dead end (x), then the way along the bottom reaches the exit (o).

def solve_maze(grid):
# 0 is open and 1 is a wall; find a way from the top-left to the bottom-right corner.
rows, cols = len(grid), len(grid[0])
board = [["█" if cell else "·" for cell in row] for row in grid]
if grid[0][0] or grid[rows - 1][cols - 1]:
return False
return walk(board, 0, 0, rows, cols)
def walk(board, r, c, rows, cols):
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != "·":
return False
board[r][c] = "o"
if r == rows - 1 and c == cols - 1:
return True
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
if walk(board, r + dr, c + dc, rows, cols):
return True
board[r][c] = "x"
return False

Invariant: The o cells always form one connected path from the start to the current cell, and each cell is entered at most once.

Start

r—

c—

The table is still empty.

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Orange = changed in this step

[0, 0, 0, 1, 0][1, 1, 0, 1, 0][0, 0, 0, 0, 0][0, 1, 1, 1, 1][0, 0, 0, 0, 0]

Step 1 of 230

Explanation

The maze is a table: 0 is an open cell and 1 a wall. Start at the top-left corner and try right, down, left and up in turn:

if the next cell is open and not seen yet, enter it (o);
if no way forward is left from a cell, mark it as a dead end (x) and step back.

This is depth-first search on the graph of cells; the call stack is the current path.

Each cell is entered at most once: O(rows × cols). The path found is not necessarily the shortest; for that, use breadth-first search.

The table is the maze: █ walls, o the current path and x the dead ends. The call tree shows the branches tried.