Maze generator in Python: three algorithms, measured

A maze for a book has one rule above the others: exactly one way from the entrance to the exit. A maze like that is called perfect. Any of the classic generators makes one. They do not make the same puzzle, though, and the difference is easy to measure.

On 25 October 2026 we built 300 mazes of 16 x 20 squares with each of three algorithms, and counted what a solver meets on the way through.

Perfect, and how to prove it#

Think of each square as a dot and each opening in a wall as a line between two dots. A perfect maze is then a tree: every dot is connected, and there are no loops. A tree with n dots has exactly n - 1 lines. So a maze is perfect when two things hold: every square can be reached from the entrance, and the number of openings is the number of squares minus one. One breadth-first search and one count, and you never have to trust the generator.

We also checked it the slow way, with code that shares nothing with the generators. On 50 small mazes (6 x 7) from each algorithm, a plain search listed every route between the corners: always exactly one. Opening one more wall in a perfect maze made the check fail, as it should.

The code#

Three generators, a solver, the perfect check and a text drawing. Standard library only.

import random
from collections import deque

def neighbours(cell, w, h):
    x, y = cell
    for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
        if 0 <= nx < w and 0 <= ny < h:
            yield nx, ny

def backtracker(w, h, rng):
    """Depth first: walk on until stuck, then step back to the last square with a way out."""
    stack, seen, passages = [(0, 0)], {(0, 0)}, set()
    while stack:
        here = stack[-1]
        fresh = [n for n in neighbours(here, w, h) if n not in seen]
        if not fresh:
            stack.pop()
            continue
        nxt = rng.choice(fresh)
        seen.add(nxt)
        passages.add(frozenset((here, nxt)))
        stack.append(nxt)
    return passages

def prim(w, h, rng):
    """Grow from one square, opening a random wall on the edge of the maze each time."""
    maze, passages = {(0, 0)}, set()
    walls = [((0, 0), n) for n in neighbours((0, 0), w, h)]
    while walls:
        i = rng.randrange(len(walls))
        walls[i], walls[-1] = walls[-1], walls[i]
        here, nxt = walls.pop()
        if nxt not in maze:
            maze.add(nxt)
            passages.add(frozenset((here, nxt)))
            walls += [(nxt, n) for n in neighbours(nxt, w, h) if n not in maze]
    return passages

def wilson(w, h, rng):
    """Random walks until they hit the maze, loops erased: every possible maze is equally likely."""
    cells = [(x, y) for y in range(h) for x in range(w)]
    maze, passages = {rng.choice(cells)}, set()
    for start in cells:
        step, here = {}, start
        while here not in maze:                 # walk; revisiting a square overwrites its exit, which erases the loop
            step[here] = rng.choice(list(neighbours(here, w, h)))
            here = step[here]
        here = start
        while here not in maze:
            maze.add(here)
            passages.add(frozenset((here, step[here])))
            here = step[here]
    return passages

def solve(passages, w, h):
    """Breadth first from the top left: the route to the bottom right, and how many squares were reached."""
    came = {(0, 0): None}
    queue = deque([(0, 0)])
    while queue:
        here = queue.popleft()
        for n in neighbours(here, w, h):
            if n not in came and frozenset((here, n)) in passages:
                came[n] = here
                queue.append(n)
    route, here = [], (w - 1, h - 1)
    while here is not None:
        route.append(here)
        here = came[here]
    return route[::-1], len(came)

def is_perfect(passages, w, h):
    """Every square reachable and exactly one opening fewer than squares: a tree, so one route between any two."""
    return len(passages) == w * h - 1 and solve(passages, w, h)[1] == w * h

def draw(passages, w, h):
    rows = ["+  +" + "--+" * (w - 1)]                       # the way in, top left
    for y in range(h):
        side = "|" + "".join("   " if frozenset(((x, y), (x + 1, y))) in passages else "  |" for x in range(w))
        floor = "+" + "".join("  +" if frozenset(((x, y), (x, y + 1))) in passages or (x, y) == (w - 1, h - 1)
                              else "--+" for x in range(w))     # the way out, bottom right
        rows += [side, floor]
    return "\n".join(rows)

rng = random.Random(7)
for make in (backtracker, prim, wilson):
    m = make(8, 5, rng)
    print(make.__name__, "perfect:", is_perfect(m, 8, 5))
print(draw(backtracker(8, 5, random.Random(7)), 8, 5))

+  +--+--+--+--+--+--+--+
|  |                    |
+  +--+  +--+  +--+--+--+
|     |     |           |
+--+  +  +--+--+--+--+  +
|  |  |  |     |        |
+  +  +--+  +  +  +--+  +
|  |        |     |  |  |
+  +--+--+--+--+--+  +  +
|                       |
+--+--+--+--+--+--+--+  +

Three algorithms, 900 mazes#

• Backtracker (depth first) walks on from the last square until it is stuck, then steps back to the last square with a way out.
• Prim grows the maze from one square, opening a random wall on its edge each time.
• Wilson sends random walks out until they hit the maze, erasing any loop they make on the way. David Wilson proved in 1996 that this picks every possible maze of the grid with the same chance.

All 900 were perfect. Here is what a solver meets, as the median of 300 mazes of 16 x 20 squares, entrance top left, exit bottom right:

• Backtracker: 11% dead ends, route 3.5x, 9 forks.
• Prim: 32% dead ends, route 1.1x, 21 forks.
• Wilson: 29% dead ends, route 1.5x, 24 forks.

Dead ends are the squares with one opening, as a share of all squares. Route is the length of the way through against the shortest walk the grid allows, from corner to corner along the edges: 1.0x means no detour at all. Forks are the squares on the route where a solver has to choose between two or more ways on.

What the numbers mean for a reader#

Prim looks hard and is not. A third of its squares are dead ends, so the page looks busy. But the way through is almost the shortest walk: at most 1.3 times it (rounded) in our 300. Head for the far corner and you mostly get there.

The backtracker is long and calm. It makes long corridors that wind across the page. The route was 3.5 times the shortest walk on the median maze and up to 6.3 times, but with few forks. The reader walks a lot and chooses little.

Wilson asks the most questions. It has the most forks on the route, 24 on the median maze and up to 51, with a route of moderate length. Because it picks every maze with the same chance, it has no habit of its own, such as long corridors or short dead ends.

And none of them guarantees a good puzzle every time. One Wilson maze had a route no longer than the shortest walk the grid allows (1.0x), and one backtracker maze had a single fork on its route. A generator for a book should measure every maze it makes and throw away the ones that are too direct or have too few choices, whatever algorithm it uses.

From mazes to a book#

That last step is what our maze book maker does for KDP. You pick a level (easy 10 x 12, medium 16 x 20, hard 24 x 30 or expert 32 x 40), the number of mazes and the trim size. You get the interior PDF with every solution drawn, a full wrap cover with the spine sized to the page count, and a signed check of both files against KDP's paperback specs. A second program proves from the walls alone that every maze has exactly one route.

For younger readers, mazes for kids books use small grids with bold walls. They keep a maze only when its route is at least one and a half times the shortest walk and passes enough forks: 3 for easy, 4 for medium and 5 for hard.