# Sampling Bias in Maze Generation: Randomised Kruskal vs Wilson's Algorithm

> Kruskal samples spanning trees unevenly; Wilson samples uniformly. Across all 7! edge orders on a 2x3 grid, Kruskal produces each tree either 360 or 300 times.

Source: https://sheng.page/en/posts/maze-generation-sampling-bias-kruskal-vs-wilson/ · Published: 2026-10-25 · Author: Sheng

A perfect maze is a spanning tree of its grid graph. Choosing a tree at random does not guarantee that every tree has the same chance. On a 2x3 grid, running Kruskal over all 5,040 edge orders produces 15 trees: nine appear 360 times each, while the other six appear 300 times each. Wilson's loop-erased random walk gives a uniform distribution over spanning trees.

For a level with fewer dead ends and longer paths, backtracker is a useful starting point in the 20x20 comparison. Choose Wilson when the requirement is equal probability for every spanning tree.

## A perfect maze is a spanning tree

Treat each cell as a vertex and each wall between neighbouring cells as a candidate edge. Removing a wall adds a passage. A perfect maze forms a spanning tree: it connects the entire grid without a cycle, leaving exactly one path between any two cells.

A tree with n cells has `n−1` passages. On a 20x20 grid, there are 400 cells and 760 candidate edges, of which 399 become passages. A 2x3 grid has six cells joined by seven candidate edges, with 15 possible spanning trees.

## Three generators

Recursive backtracker follows a depth-first search (DFS). Starting from one cell, it chooses an unvisited neighbour at random and opens a passage to it. When it runs out of unvisited neighbours, it backtracks until it can continue. It tends to produce [long, winding corridors with few branches](https://yog-ex.hexdocs.pm/maze_generation.md).

Randomised Kruskal shuffles every candidate edge and considers them in that order. A union-find structure tracks which cells are already connected. If an edge joins two separate components, it becomes a passage; otherwise it is skipped to avoid a cycle.

Wilson starts with one cell in the tree. From any cell outside it, a random walk chooses uniformly among the current cell's neighbours. Whenever the walk revisits a cell on its own path, it erases the resulting loop. On reaching the existing tree, it adds the surviving path, then starts again from a cell still outside the tree, until every cell has been added. Fixing the initial cell at the top-left corner preserves uniform sampling, as established by [Wilson's 1996 proof](https://www.cs.cmu.edu/~15859n/RelatedWork/RandomTrees-Wilson.pdf).

## Exhaustive 2x3: Kruskal is not uniform

Seven edges have just `7! = 5040` possible orders, so `kruskal_enum.py` runs them all, counting each distinct set of tree edges, then draws 504,000 Wilson samples on the same grid for comparison.

```python
# Does "random spanning tree" mean "every spanning tree equally likely"?
# On a 2x3 grid (6 cells, 7 edges) we can feed Kruskal every one of the 7! = 5040 edge
# orderings and count how often each tree appears. Wilson's algorithm on the same grid is
# sampled 504,000 times for comparison; it is known to sample spanning trees uniformly.
from itertools import permutations
from collections import Counter
import random

random.seed(42)
W, H = 3, 2
cells = [(x, y) for y in range(H) for x in range(W)]
edges = [((x, y), (x + 1, y)) for y in range(H) for x in range(W - 1)] + \
        [((x, y), (x, y + 1)) for y in range(H - 1) for x in range(W)]
nb = {c: [b if a == c else a for a, b in edges if c in (a, b)] for c in cells}

def kruskal(order):
    parent = {c: c for c in cells}
    def find(c):
        while parent[c] != c:
            c = parent[c]
        return c
    tree = []
    for a, b in order:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            tree.append((a, b))
    return frozenset(tree)

def wilson():
    in_tree = {cells[0]}
    tree = []
    while len(in_tree) < len(cells):
        c = random.choice([x for x in cells if x not in in_tree])
        path = [c]
        while c not in in_tree:            # loop-erased random walk
            c = random.choice(nb[c])
            if c in path:
                path = path[:path.index(c) + 1]
            else:
                path.append(c)
        for a, b in zip(path, path[1:]):
            tree.append(tuple(sorted((a, b))))
            in_tree.add(a)
    return frozenset(tree)

orders = list(permutations(edges))
kc = Counter(kruskal(o) for o in orders)
print(f"2x3 grid: {len(edges)} edges, {len(orders)} edge orderings, {len(kc)} distinct spanning trees, uniform would be {len(orders) // len(kc)} each")
print("Kruskal: trees per multiplicity ->", dict(sorted(Counter(kc.values()).items())))
samples = 504_000
wc = Counter(wilson() for _ in range(samples))
print(f"Wilson ({samples} samples): {len(wc)} trees, counts from {min(wc.values())} to {max(wc.values())}, uniform would be {samples // len(wc)}")
```

```text
2x3 grid: 7 edges, 5040 edge orderings, 15 distinct spanning trees, uniform would be 336 each
Kruskal: trees per multiplicity -> {300: 6, 360: 9}
Wilson (504000 samples): 15 trees, counts from 33360 to 34007, uniform would be 33600
```

Uniform sampling would allocate 336 of the 5,040 orders to each tree. Instead, nine trees receive 360 orders each and six receive 300.

The central vertical edge separates the two groups. It belongs to both four-edge cycles in the grid. Each of the nine trees containing it appears 360 times; each of the six without it appears 300 times. Kruskal therefore includes that edge with probability `3240/5040`, or about 64.3%. Under uniform sampling, the probability would be `9/15`, or 60%.

The Wilson sample gives counts between 33,360 and 34,007, against an expected 33,600 per tree. A binomial count with probability `1/15` has a standard deviation of about 177, putting the largest deviation at roughly 2.3σ across 15 trees, an ordinary sampling fluctuation.

A small sample of Kruskal mazes could hide its unequal probabilities in the noise; counting every edge order exposes the difference directly.

## Texture metrics on 20x20

A [dead end](https://educative.io/courses/mazes-for-programmers/counting-dead-ends) is a cell with exactly one passage. Its share is the number of those cells divided by the total cell count. Diameter is the greatest shortest-path distance between any pair of cells, measured in edges. For a tree, two breadth-first searches find it: start anywhere and find a farthest cell, then search from that cell for the farthest one again. If the entrance and exit are already fixed, measure their distance separately. The solution length equals the diameter when those endpoints form a farthest pair.

Run `maze_metrics.py` to compare 200 mazes per generator on a 20x20 grid; it sets `seed 42` once and shares the random state across generators, so reproducing the results requires keeping their execution order.

```python
# Texture of 20x20 mazes from three generators: share of dead ends, diameter (longest shortest
# path, counted in edges) and wall-clock time. Numbers describe this grid size and sample
# size only; they are not fixed properties of the algorithms.
import random, time

random.seed(42)
W = H = 20
CELLS = [(x, y) for x in range(W) for y in range(H)]

def nbrs(c):
    x, y = c
    return [(x + dx, y + dy) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) if 0 <= x + dx < W and 0 <= y + dy < H]

def link(adj, a, b):
    adj[a].add(b); adj[b].add(a)

def backtracker():
    adj = {c: set() for c in CELLS}
    stack, seen = [(0, 0)], {(0, 0)}
    while stack:
        c = stack[-1]
        options = [n for n in nbrs(c) if n not in seen]
        if not options:
            stack.pop(); continue
        n = random.choice(options)
        link(adj, c, n); seen.add(n); stack.append(n)
    return adj

def kruskal():
    adj = {c: set() for c in CELLS}
    parent = {c: c for c in CELLS}
    def find(c):
        while parent[c] != c:
            parent[c] = parent[parent[c]]; c = parent[c]
        return c
    edges = [(a, b) for a in CELLS for b in nbrs(a) if a < b]
    random.shuffle(edges)
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb; link(adj, a, b)
    return adj

def wilson():
    adj = {c: set() for c in CELLS}
    in_tree = {(0, 0)}
    while len(in_tree) < len(CELLS):
        c = random.choice([x for x in CELLS if x not in in_tree])
        path = [c]
        while c not in in_tree:
            c = random.choice(nbrs(c))
            if c in path:
                path = path[:path.index(c) + 1]
            else:
                path.append(c)
        for a, b in zip(path, path[1:]):
            link(adj, a, b); in_tree.add(a)
    return adj

def farthest(adj, start):
    dist = {start: 0}
    queue = [start]
    for c in queue:
        for n in adj[c]:
            if n not in dist:
                dist[n] = dist[c] + 1; queue.append(n)
    far = max(dist, key=dist.get)
    return far, dist[far]

RUNS = 200
print(f"20x20, {RUNS} mazes each")
for name, gen in (("recursive backtracker", backtracker), ("Kruskal", kruskal), ("Wilson", wilson)):
    dead = diameter = 0.0
    t0 = time.perf_counter()
    mazes = [gen() for _ in range(RUNS)]
    elapsed = (time.perf_counter() - t0) / RUNS * 1000
    for adj in mazes:
        dead += sum(len(v) == 1 for v in adj.values()) / len(CELLS)
        a, _ = farthest(adj, (0, 0))
        diameter += farthest(adj, a)[1]
    print(f"{name:22s} dead ends={dead / RUNS * 100:5.1f}%  mean diameter={diameter / RUNS:6.1f} edges  ({elapsed:5.1f} ms per maze)")
```

```text
20x20, 200 mazes each
recursive backtracker  dead ends= 10.6%  mean diameter= 228.6 edges  (  0.6 ms per maze)
Kruskal                dead ends= 30.3%  mean diameter=  81.8 edges  (  0.7 ms per maze)
Wilson                 dead ends= 29.3%  mean diameter=  91.5 edges  (  5.1 ms per maze)
```

Backtracker has a mean dead-end share of 10.6% and a mean diameter of 228.6 edges, giving fewer dead ends and a longer maximum path than the other generators. Kruskal and Wilson have similar dead-end shares, at 30.3% and 29.3%, while their mean diameters are 81.8 and 91.5 edges respectively.

Generation took about 0.6 ms per maze for backtracker, 0.7 ms for Kruskal and 5.1 ms for Wilson, excluding metric calculations. These are single-threaded Python timings from one run on a Mac, useful only for comparing these implementations. If your levels use a different grid size, rerun the timings and dead-end counts rather than carrying over the 10.6% figure.

## What uniformity means for the player

Wilson gives each spanning tree of the grid the same chance. A dead-end share represented by more trees will still appear more often, and the same applies to path length.

For reproducible daily levels, store each level's seed alongside the generator and Python versions, and give it a separate random state. Regenerating it then needs no replay of earlier levels' random draws. This works with Kruskal and backtracker too.

Choose Wilson if every spanning tree must have an equal chance, and keep all its results. If sampling bias is acceptable, Kruskal offers a similar dead-end share at lower generation cost in this comparison. Backtracker is a useful starting point for fewer dead ends and longer maximum paths. To select for a level's requirements, use the measurement loop as a filter: each generator returns `adj`, listing the reachable neighbours of each cell, so measure each maze's dead-end share and entrance-to-exit distance before accepting it. Draw an accepted maze by removing walls along those connections; discard failures and generate another candidate.

## Notes

- Check that a perfect maze connects every cell without a cycle before checking its sampling distribution.
- Count every edge order when the grid is small enough: all `7!` orders on a 2x3 grid give nine Kruskal trees 360 times each and six 300 times each, exposing the bias exactly.
- Check a Wilson implementation against tree frequencies on a small grid; the 504,000 samples provide a comparison close to the uniform expectation.
- Use the 20x20 comparison, with 200 mazes per generator, as a starting point for selection. Try backtracker for fewer dead ends and longer paths: about 10.6% dead ends and a mean diameter of 229 edges here. Kruskal and Wilson have about 30% dead ends and mean diameters of roughly 82 to 92 edges.
- Filter individual mazes by dead-end share and entrance-to-exit distance; a batch average cannot decide whether a particular level fits.

## Further reading

- David Bruce Wilson, [Generating Random Spanning Trees More Quickly than the Cover Time](https://www.cs.cmu.edu/~15859n/RelatedWork/RandomTrees-Wilson.pdf), 1996: the paper introducing uniform spanning-tree generation through loop-erased random walks.
- YogEx, [Maze generation](https://yog-ex.hexdocs.pm/maze_generation.md): documentation for an Elixir maze library, with qualitative descriptions of corridor texture.
- Jamis Buck, *Mazes for Programmers*, [Counting dead ends](https://educative.io/courses/mazes-for-programmers/counting-dead-ends): an online lesson showing how to count dead ends in code and compare maze generators.

> Ideas and technical judgement by Sheng; drafted with Claude · examples run on a Mac with Python 3.15.0.