Maze Generator and Solver in Python

Generating a maze and then solving it sits in a sweet spot of computer science — it touches recursion, randomness, graph search, and visualization, all in code that's short enough to read in one sitting. It's also one of the most fun things you can do with a hundred lines of Python.

The Two Halves Of The Problem

A "maze app" is really two unrelated algorithms glued together:

1. A generator that builds a random maze.

2. A solver that finds the way through it.

They don't know about each other — the solver just receives a 2D grid where 0 means "open path" and 1 means "wall" and does its job. You can swap either half independently.

How The Recursive Backtracker Generates A Maze

The recursive backtracker is the most popular maze algorithm, and for good reason — it produces dramatic, winding mazes with long corridors. The recipe:

1. Start with a grid where everything is a wall.

2. Pick a starting cell, mark it visited, carve it out.

3. Look at the cell's unvisited neighbors. Pick one at random.

4. Knock down the wall between the current cell and that neighbor. Move to it. Mark it visited. Push the previous cell onto a stack.

5. If a cell has no unvisited neighbors, pop the stack — back up to the previous cell and try a different direction from there.

6. Done when the stack is empty (every reachable cell has been visited).

The code in the snippet uses an explicit stack = [...] instead of literal recursion. That's deliberate — for a 50×50 maze, real recursion would blow Python's default recursion limit. Using a list as a stack does exactly the same thing without that risk.

The "2× grid" trick

Notice the maze is sized (2*rows+1, 2*cols+1), not just (rows, cols). That's because walls have to live somewhere. Cells live at odd coordinates (1, 1), (1, 3), (1, 5)..., and the wall between two cells lives at the even coordinate between them. When you "knock down a wall", you're flipping that one in-between pixel from WALL to PATH.

This layout makes rendering trivial — every cell of the grid is either a wall or a path, and you just imshow it.

Why The Resulting Mazes Look So Good

Recursive backtracker mazes have a distinctive visual personality:

Different algorithms give different aesthetics. Prim's algorithm produces shorter, branchier mazes. Eller's algorithm runs row by row and is great for infinite mazes. Wilson's algorithm is unbiased — every possible maze has equal probability — but is much slower.

How BFS Solves The Maze

Breadth-First Search is the right tool here because:

BFS explores in expanding rings from the start — first all cells one step away, then all cells two steps away, then three. The first time it reaches the goal, it has found the shortest possible path. This guarantee fails the moment edges have different weights — for that you need Dijkstra's algorithm or A*.

The parent dictionary is the trick that lets you actually reconstruct the path. Every cell records which neighbor it was discovered from. Once BFS reaches the goal, you walk that chain backwards to the start.

What The Visualization Shows

The overlay in the plot uses four colors to tell the whole story at a glance:

If you compare a long winding maze to a short straight one, you'll notice BFS visits almost every cell in winding mazes before finding the goal. That's a property of recursive-backtracker mazes — there's only one path, and BFS has to explore most of the maze to find it.

Why Not DFS? Why Not A*?

Things To Tweak

Where This Pattern Shows Up In Real Code

Run the snippet above and you'll see a unique 25×25 maze get carved out from solid walls, watch BFS sweep through it in light blue, and find the single red shortest path from entrance to exit — followed by three completely different mazes generated from three different seeds.