Maze Generation Algorithms: How Computers Build Perfect Mazes

Maze generation algorithms are step-by-step recipes a computer follows to build a maze. Most start with a grid of square rooms, or cells, all walled off from each other, and then knock down walls until every cell is connected. If the recipe never creates a loop, the result is a "perfect" maze: exactly one path between any two points. The best-known methods are the recursive backtracker, Prim's algorithm, Kruskal's algorithm, Eller's algorithm, Wilson's algorithm, Aldous-Broder, hunt-and-kill, binary tree, sidewinder and recursive division. Each one leaves a different fingerprint, from long, winding corridors to short, bushy dead ends.

In this guide we'll build the same tiny 3x3 maze with several of these methods, step by step, drawn as tables. You'll see why a perfect maze is really a math object called a spanning tree, how each algorithm makes its choices, and how those choices shape how hard a maze feels to solve. No code is needed, though there are a couple of optional snippets for the curious.

What a perfect maze really is

Walter D. Pullen's maze reference, Think Labyrinth: Maze Algorithms, defines a perfect maze as one with no loops or closed circuits and no unreachable areas. It then adds the key insight: a perfect maze can be described as a spanning tree over the set of cells.

That sounds technical, so let's unpack it.

• Graph: a set of dots (here, the maze cells) and lines joining some of them (here, the open passages between neighboring cells).
• Tree: a graph with no loops. You can't walk in a circle and come back to where you started without retracing your steps.
• Spanning tree: a tree that reaches every dot. Every cell is connected, and there are no loops.

A spanning tree has a handy property. If it has V dots, it has exactly V minus 1 lines. Princeton's Algorithms textbook section on minimum spanning trees, by Robert Sedgewick and Kevin Wayne, uses this when it describes Kruskal's algorithm adding edges "until V-1 edges are added." For mazes, that means:

A perfect maze with N cells has exactly N minus 1 open passages.

Let's check that with simple math for a few grid sizes. In a grid with R rows and C columns, there are R x C cells. The internal walls between neighbors number R x (C minus 1) side-to-side plus (R minus 1) x C top-to-bottom.

Grid	Cells	Passages in a perfect maze (cells minus 1)	Internal walls to start	Internal walls left standing
3 x 3	9	8	3x2 + 2x3 = 12	12 - 8 = 4
10 x 10	100	99	10x9 + 9x10 = 180	180 - 99 = 81
20 x 20	400	399	20x19 + 19x20 = 760	760 - 399 = 361

So every algorithm in this guide that makes a perfect maze is really answering one question: which N minus 1 walls should come down? Knock down too few and some cells are cut off. Knock down too many and you create loops. Every method has its own way of picking exactly the right number.

Our 3x3 grid

We'll number the nine cells like a phone keypad:

	Left	Middle	Right
Top	1	2	3
Middle	4	5	6
Bottom	7	8	9

Two cells are neighbors if they share a side, so 1 and 2 are neighbors, but 1 and 5 are not. There are 12 walls between neighbors: 1-2, 2-3, 4-5, 5-6, 7-8 and 8-9 side to side, and 1-4, 2-5, 3-6, 4-7, 5-8 and 6-9 top to bottom. Our goal each time is to remove 8 of those 12.

To draw the finished mazes, we'll use a bigger table. Each cell number sits in its own square, # marks a wall, and a dot marks an opening where a wall was knocked down.

The recursive backtracker: long, twisty corridors

The recursive backtracker is the most popular maze generation algorithm, and for good reason: it's simple and makes satisfying mazes. It's a randomized version of what programmers call depth-first search. Pullen sums up its spirit nicely: when carving, be as greedy as possible, and always carve into an unmade section if one is next to you.

1. Pick a starting cell and mark it visited.
2. Look at the current cell's unvisited neighbors. If there are any, pick one at random.
3. Knock down the wall between them, move into the new cell, mark it visited, and remember where you came from by adding the old cell to a list called a stack.
4. If the current cell has no unvisited neighbors, back up to the last cell on the stack and try again from there.
5. When you've backed all the way up to the start, you're done.

Worked example

Here's one run, starting at cell 1. The "random" choices were picked for illustration.

Step	At cell	Unvisited neighbors	Choice	Wall removed
1	1	2, 4	2	1-2
2	2	3, 5	5	2-5
3	5	4, 6, 8	4	5-4
4	4	7	7	4-7
5	7	8	8	7-8
6	8	9	9	8-9
7	9	6	6	9-6
8	6	3	3	6-3
9	3	none	back up	none

After step 9, the algorithm backs up through 6, 9, 8, 7, 4, 5, 2 and 1, finding no unvisited neighbors anywhere, and stops. We removed 8 walls, exactly as the spanning-tree math predicted. Here's the result:

#	#	#	#	#	#	#
#	1	.	2	#	3	#
#	#	#	.	#	.	#
#	4	.	5	#	6	#
#	.	#	#	#	.	#
#	7	.	8	.	9	#
#	#	#	#	#	#	#

Look at that: the whole maze is a single winding corridor, 1, 2, 5, 4, 7, 8, 9, 6, 3, with no branches at all. On a 3x3 grid that's partly luck, but it shows the recursive backtracker's personality. Because it always pushes forward into new territory, it makes long passages with few, long dead ends. Pullen's comparison table backs this up: of all the algorithms he lists, the recursive backtracker has the lowest share of dead-end cells (10%) and the longest solutions (19% of cells, on average).

If you like code, the heart of it fits in a short blockquote:

visit(cell): mark cell visited; for each unvisited neighbor n of cell, in random order: remove the wall between cell and n, then visit(n)

Prim's algorithm: growing from a seed

Prim's algorithm comes from a 1957 paper by R.C. Prim, "Shortest Connection Networks and Some Generalizations", published in the Bell System Technical Journal. Prim was interested in connecting points with the least total wire, but his method adapts beautifully to mazes. Instead of following one long path, it grows the maze outward from a seed, like mold spreading across bread.

Pullen describes several versions. Here's the "modified" one, which is the easiest to do by hand:

1. Pick a starting cell and mark it "in." Mark its neighbors "frontier."
2. Pick a random frontier cell.
3. Knock down the wall between it and one random neighbor that's already "in." Mark it "in."
4. Mark any of its neighbors that are still "out" as frontier.
5. Repeat until there are no frontier cells left.

Worked example

Step	Frontier before picking	Picked	"In" neighbors to choose from	Wall removed
Start	none	5 (seed)	none	none
1	2, 4, 6, 8	8	5	5-8
2	2, 4, 6, 7, 9	4	5	4-5
3	1, 2, 6, 7, 9	7	4, 8	4-7
4	1, 2, 6, 9	2	5	2-5
5	1, 3, 6, 9	1	2, 4	1-2
6	3, 6, 9	9	8	8-9
7	3, 6	6	5, 9	6-9
8	3	3	2, 6	3-6

#	#	#	#	#	#	#
#	1	.	2	#	3	#
#	#	#	.	#	.	#
#	4	.	5	#	6	#
#	.	#	.	#	.	#
#	7	#	8	.	9	#
#	#	#	#	#	#	#

This time the center cell, 5, is a hub with three openings, and the maze branches out from it. That's Prim's personality: lots of short branches radiating from the starting area. On big grids, that makes many short dead ends. In Pullen's table, the modified Prim's has one of the highest dead-end shares (36%) and one of the shortest typical solutions (2.3% of cells). Mazes like this look busy but are often easier to solve than they look, because the dead ends are short.

Kruskal's algorithm: merging islands

Kruskal's algorithm also comes from network math. Joseph Kruskal published it in 1956 in "On the shortest spanning subtree of a graph and the traveling salesman problem" in the Proceedings of the American Mathematical Society. Where Prim's grows one blob, Kruskal's grows many little islands all over the grid and merges them.

Pullen's maze version goes like this:

1. Give every cell its own label. At the start, every cell is its own island.
2. Shuffle the list of all walls between neighbors.
3. Take the next wall. If the cells on either side have different labels, knock it down and merge the two islands into one, giving them all the same label.
4. If the cells already have the same label, leave the wall. Removing it would create a loop.
5. Stop when everything is one island.

Programmers use a structure called union-find to keep track of the labels quickly, and Princeton's textbook describes Kruskal's using exactly that.

Worked example

Wall (shuffled order)	Same island?	Action	Islands afterward
5-6	No	Remove	{5,6} and seven singles
1-4	No	Remove	{1,4}, {5,6}, others single
2-3	No	Remove	{1,4}, {2,3}, {5,6}, 7, 8, 9
4-5	No	Remove	{1,4,5,6}, {2,3}, 7, 8, 9
8-9	No	Remove	{1,4,5,6}, {2,3}, {8,9}, 7
1-2	No	Remove	{1,2,3,4,5,6}, {8,9}, 7
2-5	Yes	Keep wall	No change
6-9	No	Remove	{1,2,3,4,5,6,8,9}, 7
3-6	Yes	Keep wall	No change
7-8	No	Remove	One island: done

The walls 2-5 and 3-6 were skipped because removing them would have closed a loop. Walls 4-7 and 5-8 were never reached. Eight removals again:

#	#	#	#	#	#	#
#	1	.	2	.	3	#
#	.	#	#	#	#	#
#	4	.	5	.	6	#
#	#	#	#	#	.	#
#	7	.	8	.	9	#
#	#	#	#	#	#	#

Because Kruskal's picks walls from all over the grid at random, it doesn't favor any region. Pullen lists it as low in "river," his word for how much a maze flows in long channels, with about 30% dead-end cells. Kruskal mazes tend to have lots of short dead ends spread evenly everywhere.

Aldous-Broder and Wilson's algorithm: perfectly fair mazes

Every algorithm so far has a hidden bias. Some possible mazes come up more often than others. The recursive backtracker, for example, strongly favors long corridors. What if you wanted a maze chosen completely fairly, so that every possible perfect maze on the grid is equally likely? Mathematicians call that a uniform spanning tree, and two algorithms produce one.

Aldous-Broder: the random wanderer

Andrei Broder and David Aldous found this method independently. Broder presented "Generating random spanning trees" at the 1989 Symposium on Foundations of Computer Science, and Aldous published a paper on the random walk construction of uniform spanning trees in the SIAM Journal on Discrete Mathematics in 1990. The recipe is almost silly in its simplicity:

1. Start at any cell and mark it visited.
2. Step to a random neighbor, visited or not.
3. If that neighbor hasn't been visited before, knock down the wall you just walked through and mark it visited.
4. Keep wandering until every cell has been visited.

Here's an illustrative wander starting at 5: 5, 6, 5, 4, 1, 2, 3, 2, 5, 8, 7, 8, 9. Walls come down only on first visits: 5-6, 5-4, 4-1, 1-2, 2-3, 5-8, 8-7 and 8-9. That's 8 walls from 12 steps. The 4 wasted steps were moves back into cells already visited. On a big grid, the wasted steps pile up enormously, especially near the end when the walker has to stumble onto the last few unvisited cells. Pullen's speed table rates Aldous-Broder as one of the slowest methods (279 on his scale, where the fastest is 10).

Wilson's algorithm: wandering with an eraser

David Bruce Wilson found a much faster way to get the same perfectly fair result. His paper, "Generating random spanning trees more quickly than the cover time," appeared at the 1996 Symposium on the Theory of Computing. The trick is called a loop-erased random walk.

1. Put one random cell into the maze.
2. Pick any cell not yet in the maze and wander randomly from it until you bump into the maze.
3. If your wander ever crosses its own path, erase the loop it just made.
4. Carve the loop-free path into the maze.
5. Repeat from step 2 until every cell is in the maze.

Worked example

Round	Starting cell	Random wander	After erasing loops	Walls removed
Setup	9 is put in the maze	none	none	none
1	1	1, 2, 5, 4, 1, 2, 3, 6, 9	1, 2, 3, 6, 9 (the loop 1, 2, 5, 4, 1 is erased)	1-2, 2-3, 3-6, 6-9
2	4	4, 5, 2	4, 5, 2 (no loop)	4-5, 5-2
3	7	7, 8, 5	7, 8, 5 (no loop)	7-8, 8-5

Eight walls, no loops, and every cell connected. Pullen notes that Wilson's and Aldous-Broder's mazes have the same texture, since both are uniform, but Wilson's runs far faster (48 on his scale versus 279). Wilson's algorithm is slow at the start, while the maze is a single cell that's hard to bump into, and speeds up as the maze grows.

Eller's algorithm: one row at a time

Eller's algorithm is a favorite among programmers because it can build a maze of any length while only remembering one row. Pullen describes it as building one row at a time while tracking which cells are already connected.

1. Give each cell in the first row its own set label.
2. Go along the row and randomly join neighboring cells that are in different sets, merging their labels.
3. For each set, open at least one passage down to the next row. (Cells alone in their set must open downward, or they'd be cut off.) Other cells may open downward at random.
4. In the new row, cells that got a passage from above keep that label. The rest get fresh labels.
5. Repeat for each row. On the last row, join every pair of neighbors that are still in different sets.

Here's an illustrative run on our 3x3 grid:

Row	Labels before joining	Side-to-side joins	Down passages
Top (1, 2, 3)	A, B, C	2-3 (B and C merge into B)	1-4 (A must go down), 3-6 (B needs at least one)
Middle (4, 5, 6)	A, D (new), B	4-5 (D joins A)	5-8 (for A), 6-9 (B needs one)
Bottom (7, 8, 9)	E (new), A, B	Last row: join all different sets, 7-8 and 8-9	None (last row)

Count the removed walls: 2-3, 1-4, 3-6, 4-5, 5-8, 6-9, 7-8 and 8-9. That's 8, and the last-row rule makes sure everything ends up connected. Because Eller's only needs one row of memory, Pullen marks it as suitable for mazes that can be extended indefinitely. His table also lists it as not bias-free, so a careful eye can sometimes spot its row-by-row construction.

Fast and simple: binary tree, sidewinder and hunt-and-kill

Binary tree

The binary tree algorithm may be the simplest maze generator there is. Pullen describes it as carving each cell either upward or leftward, never both, independent of every other cell. In our grid, that means:

• Cell 1 (top-left corner) can't go up or left, so it does nothing.
• Cells 2 and 3 in the top row can only go left, so 1-2 and 2-3 always open.
• Cells 4 and 7 in the left column can only go up, so 1-4 and 4-7 always open.
• Cells 5, 6, 8 and 9 each flip a coin: up or left.

That's 2 + 2 + 4 = 8 walls removed, every time. It's lightning fast and needs no memory, but you can always spot a binary tree maze: the top row and the left column are always one long, open corridor, and paths trend diagonally toward the top-left corner. Pullen calls this a strong diagonal bias.

Sidewinder

Sidewinder fixes part of that bias. Working row by row, it randomly decides whether to keep carving to the right. When a run of cells ends, it opens a passage upward from one random cell in that run. Pullen notes it always leaves one long passage along the top edge, so solving from bottom to top is easy, but it's less lopsided than the binary tree.

Hunt-and-kill

Hunt-and-kill is like the recursive backtracker without the stack. It wanders randomly into unvisited cells until it gets stuck. Then, instead of backing up, it "hunts": it scans the grid for an unvisited cell next to a visited one, connects them and starts wandering again. Pullen notes it needs no extra memory and produces long, winding mazes similar to the recursive backtracker's, with a low dead-end share (11%).

Recursive division: building walls instead of removing them

Every method so far starts with all walls up and knocks some down. Recursive division works the opposite way. It starts with an empty room and adds walls. Pullen describes it like this:

1. Start with one big open area.
2. Draw a wall straight across it, either horizontally or vertically, at a random spot.
3. Leave one gap in that wall, so both sides stay connected.
4. Repeat on each of the two smaller areas, until the areas are one cell wide.

It's fast and has no directional bias, but its mazes have a recognizable look: long, straight walls that cut across the grid, making a box-within-a-box pattern. That can be a pleasing style for a printed puzzle, but it's also a clue for solvers. If you can tell which big wall has the one gap, you've already cut the maze in half.

Comparing maze generation algorithms

Here's a summary drawn from the comparison table in Pullen's Think Labyrinth reference. "Dead ends" is the share of cells that are dead ends. "Solution" is roughly how much of the maze the solution path passes through. "Speed" is relative, with the fastest method set to 10, so bigger numbers are slower. "Uniform" means every possible perfect maze is equally likely.

Algorithm	Dead ends	Solution	Speed (lower is faster)	Uniform?	Feel of the maze
Recursive backtracker	10%	19.0%	27	Never	Long, twisty corridors
Hunt-and-kill	11%	9.5%	100	Never	Long and winding
Prim's (true)	30%	4.1%	160	No	Branchy
Prim's (modified)	36%	2.3%	30	No	Many short dead ends
Kruskal's	30%	4.1%	33	No	Short dead ends, evenly spread
Aldous-Broder	29%	4.5%	279	Yes	Perfectly fair, slow to build
Wilson's	29%	4.5%	48	Yes	Perfectly fair, much faster
Eller's	28%	4.2%	20	No	Row-based, can run forever
Binary tree	25%	2.0%	10	Never	Strong diagonal bias
Sidewinder	27%	2.6%	12	Never	Open top row, upward bias
Recursive division	23%	7.2%	10	Never	Long straight walls, boxy

A couple of patterns jump out. The two uniform algorithms produce the same kind of maze, so the only reason to pick Aldous-Broder over Wilson's is that it's easier to explain. And the recursive backtracker stands apart, with the fewest dead ends and by far the longest solutions.

How maze generation algorithms shape difficulty

You might expect the biggest grid to make the hardest maze. Grid size matters, but the algorithm matters just as much. Here's why.

Long dead ends are more punishing than short ones. A recursive backtracker maze has few dead ends, but each one is long. Take a wrong turn, and you may walk a long way before you realize it. A modified Prim's maze has dozens of tiny dead ends that a solver's eye dismisses almost instantly.

Long solutions take longer to trace. With a solution covering 19% of the cells on average, a recursive backtracker maze simply asks you to walk farther than a binary tree maze, where the solution covers about 2%.

Bias gives solvers shortcuts. In a binary tree maze, you know the top row and left column are open corridors, so you can often solve it in seconds by working toward the top-left. In a sidewinder maze, solving from the bottom up is easy. Puzzle makers who want a fair challenge avoid these.

Dead-end filling loves short dead ends. A solver using the dead-end filling method shades every dead end away. That's quick when there are lots of short ones, and slower when they're long and winding.

So, for printed puzzles, a sensible rule of thumb is:

• For an easy maze, a branchy algorithm like Prim's on a small grid gives a short solution and obvious dead ends.
• For medium mazes, Kruskal's or Wilson's give a balanced texture with no exploitable bias.
• For a difficult maze, the recursive backtracker on a large grid gives long, misleading corridors.

From perfect mazes to mazes with loops

Perfect mazes are only one kind. Pullen defines a "braid" maze as one without any dead ends, which means it must have loops. Jamis Buck's book Mazes for Programmers has a whole chapter on braiding and weaving mazes.

The usual way to make one is to start with a perfect maze and then fix the dead ends:

1. Generate a perfect maze with any algorithm above.
2. Find each dead end.
3. For some or all of them, knock down one extra wall to a neighboring cell, turning the dead end into a through passage.

Each extra wall you remove adds exactly one loop, because a spanning tree plus one extra edge always contains exactly one cycle. (Princeton's textbook notes that adding an edge between two vertices of a tree creates a unique cycle.) Braid mazes feel very different to solve. There's no dead end to tell you you've gone wrong, so you can walk in circles for a long time. They're also harder for simple solving tricks, as we cover in our guide to maze solving algorithms.

Common mix-ups about maze generation

• "A bigger grid always means a harder maze." Not always. A large binary tree maze can be easier than a small recursive backtracker maze, because its bias hands solvers a shortcut along the top and left edges.
• "Random means fair." Every algorithm here uses random choices, but only Aldous-Broder and Wilson's give every possible maze the same chance. The others lean toward certain shapes.
• "Prim's and Kruskal's are only for mazes." They were invented for connecting points with the least total length of line. Mazes are a playful side use.
• "A maze generator also solves the maze." Generating and solving are separate jobs. A generator only guarantees that a path exists. Finding it takes a solving method, such as following the walls or a breadth-first search.
• "Perfect means pretty." In maze talk, "perfect" is a technical word. It means no loops and no unreachable cells, nothing more.

A short history of maze generation

Maze generation algorithms grew out of practical math problems long before anyone used them for puzzles.

Year	Who	What
1956	Joseph Kruskal	Publishes his shortest spanning subtree method in the Proceedings of the American Mathematical Society
1957	R.C. Prim	Publishes "Shortest Connection Networks" in the Bell System Technical Journal, volume 36, pages 1389 to 1401
1989	Andrei Broder	Presents "Generating random spanning trees" at the Symposium on Foundations of Computer Science
1990	David Aldous	Publishes the random walk construction of uniform spanning trees
1996	David Bruce Wilson	Presents his loop-erased random walk method at the Symposium on the Theory of Computing
2015	Jamis Buck	Mazes for Programmers collects binary tree, sidewinder, Aldous-Broder, Wilson's, hunt-and-kill, recursive backtracker, Kruskal's, Prim's, Eller's and recursive division in one book

Kruskal and Prim were solving a real network puzzle: how to connect many points with the shortest total length of line. A maze is the same problem with a twist. Instead of the shortest spanning tree, we want a random one. Give every wall a random weight, and Kruskal's and Prim's minimum spanning tree methods turn straight into maze generators. That's exactly what the randomized versions do.

Try it yourself: build a maze with a die

You can run Kruskal's algorithm with nothing but graph paper, a pencil and a six-sided die.

1. Draw a 4x4 grid of cells and number them 1 to 16. Every wall between neighbors starts standing. There are 4x3 + 3x4 = 24 of them.
2. List the 24 walls and number them. To "shuffle," roll the die a few times to pick the next wall from the list, crossing walls off as you go.
3. Give each cell its own color or letter.
4. For each wall you pick, check the colors on each side. Different? Erase the wall and recolor the smaller island to match the bigger one. Same? Leave the wall.
5. Stop when all 16 cells share one color. You should have erased exactly 15 walls (16 minus 1). If you count 15, the math worked, and you have a perfect maze.
6. Add a start and finish on opposite edges and hand it to a friend.

Then try the recursive backtracker on another 4x4 grid, rolling the die to pick among unvisited neighbors. Put the two mazes side by side, and you'll see the difference in texture even at this small size. It's a hands-on way to introduce algorithms, and our page on maze maker uses has more ideas for classrooms and clubs.

Make your own mazes

Maze generation algorithms all answer the same question: which walls should come down so that every cell is connected and there are no loops? The recursive backtracker answers with long, winding corridors. Prim's and Kruskal's give branchy mazes full of short dead ends. Aldous-Broder and Wilson's pick a maze with perfect fairness. And the fast, simple binary tree and sidewinder methods leave telltale shortcuts.

If you'd rather skip the dice, our free puzzle maker lets you choose a puzzle type such as a maze and print it with an answer key. For ready-made practice, browse our printable mazes or try one of our mazes for adults.

How Seven Methods Start and What They Leave Behind

This table compares the starting idea of seven maze builders with the look of the maze each one produces.

Algorithm	Its starting idea	What the maze looks like
Recursive backtracker	Be as greedy as possible, always carving into an unmade section next to you and backing up along a stack when stuck	Long, twisty corridors
Prim's algorithm	Grow the maze outward from a seed by picking random frontier cells	Branchy, with many short dead ends in the modified version
Kruskal's algorithm	Start with every cell as its own island and merge islands by knocking down walls	Short dead ends, evenly spread
Eller's algorithm	Build one row at a time while tracking which cells are connected	Row-based, and it can run forever on a maze of any length
Wilson's algorithm	Wander randomly, erase any loop, then carve the loop-free path in	Perfectly fair, since every possible perfect maze is equally likely
Binary tree	Carve each cell either upward or leftward, never both	A strong diagonal bias, with an open top row and left column
Recursive division	Start with an empty room and add walls, leaving one gap in each	Long, straight walls in a box-within-a-box pattern

Frequently Asked Questions

What is the best maze generation algorithm?

There's no single best one. It depends on the maze you want. The recursive backtracker is the most popular choice because it's simple and makes long, twisty corridors that feel challenging. Wilson's algorithm is the pick if you want every possible maze to be equally likely. Kruskal's and Prim's make branchy mazes with lots of short dead ends. Binary tree and sidewinder are the fastest and need almost no memory, but their mazes have obvious directional shortcuts that experienced solvers spot quickly.

What is a perfect maze?

A perfect maze has no loops and no unreachable areas, so there's exactly one path between any two points. Mathematically, it's a spanning tree: every cell is connected and nothing forms a circle. That gives a neat rule you can check. A perfect maze with N cells always has exactly N minus 1 open passages. A 10 by 10 grid has 100 cells, so a perfect maze on it has 99 passages, and 81 of its 180 inside walls stay standing.

How does the recursive backtracker make a maze?

It starts at one cell and keeps moving to a random unvisited neighbor, knocking down the wall between them as it goes. It remembers each cell it leaves on a list called a stack. When it reaches a cell with no unvisited neighbors, it backs up along the stack until it finds a cell that still has one, then carves forward again. When it has backed all the way to the start, every cell has been visited and the maze is finished, with no loops.

What is the difference between Prim's and Kruskal's algorithm for mazes?

Prim's grows one connected blob outward from a starting cell, always adding a random cell from the edge of the blob. Kruskal's works on the whole grid at once: it looks at walls in random order and removes each one only if the cells on either side aren't already connected, so many small islands slowly merge into one. Both come from 1950s network math. Both tend to make mazes with many short dead ends rather than long corridors.

What does uniform mean for a maze algorithm?

A uniform algorithm picks every possible perfect maze on a grid with exactly equal chance. Most algorithms don't. The recursive backtracker, for example, strongly favors mazes with long corridors, and the binary tree algorithm always leaves the top row and left column open. Aldous-Broder and Wilson's algorithm are the two well-known uniform methods. They produce mazes with the same overall texture, but Wilson's loop-erased random walk builds them much faster than Aldous-Broder's aimless wandering.

Which maze algorithm makes the hardest mazes?

For printed puzzles, the recursive backtracker on a large grid usually feels hardest. In Walter Pullen's comparison, it has the fewest dead-end cells, about 10 percent, but its dead ends are long, and its solutions are the longest, passing through about 19 percent of cells on average. A wrong turn can lead you a long way before you notice. Mazes with many short dead ends, like those from Prim's algorithm, often look busier but are quicker to solve.

How do you make a maze with loops?

Start with a perfect maze from any algorithm, then knock down a few extra walls. Each extra wall you remove adds exactly one loop, because a spanning tree plus one more connection always contains exactly one cycle. If you remove a wall at every dead end, you get a braid maze, which has no dead ends at all. Mazes with loops are harder to solve with simple tricks like following one wall, since there may be no dead end to warn you.

Can I generate a maze by hand?

Yes. Kruskal's algorithm works well with graph paper and a die. Draw a small grid, give each cell its own color, and pick walls at random. Erase a wall only if the cells on each side have different colors, then recolor one side to match. Stop when every cell is the same color. On a 4 by 4 grid you'll erase exactly 15 of the 24 inside walls, which proves the result is a perfect maze with a single path between any two cells.

Sources

We checked every source below while writing this guide. Last reviewed October 30, 2026, by Joan Ramos.

1. Think Labyrinth: Maze Algorithms (Walter D. Pullen) (Think Labyrinth (astrolog.org))
2. Mazes for Programmers: Code Your Own Twisty Little Passages (Jamis Buck, 2015) (The Pragmatic Bookshelf)
3. Algorithms, 4th Edition, Section 4.3: Minimum Spanning Trees (Sedgewick and Wayne) (Princeton University)
4. On the shortest spanning subtree of a graph and the traveling salesman problem (Kruskal, 1956) (Proceedings of the American Mathematical Society)
5. Shortest Connection Networks and Some Generalizations (Prim, 1957) (Bell System Technical Journal, via Internet Archive)
6. Generating random spanning trees (Broder, 1989) (30th Annual Symposium on Foundations of Computer Science (IEEE))
7. The Random Walk Construction of Uniform Spanning Trees (Aldous, 1990) (SIAM Journal on Discrete Mathematics)
8. Generating random spanning trees more quickly than the cover time (Wilson, 1996) (ACM Symposium on the Theory of Computing)