DFS vs Kruskal vs Prim: Which Maze Algorithm Makes the Best Puzzle Book?

A "perfect" maze is a maze with no loops: from any cell there is exactly one way to any other cell. Mathematically it is a spanning tree of the grid, and there are many ways to build one. The three classic methods — randomized depth-first search, Kruskal's algorithm and Prim's algorithm — all produce perfect mazes, yet the mazes look and solve very differently.

Instead of repeating rules of thumb, we measured them. For every grid size and style below we generated 200 mazes with the Wisdom Effect maze engine — the exact code that draws the mazes in your book — with the entrance at the top left and the exit at the bottom right. For each maze we counted the dead ends (cells with a single opening), the length of the solution route in cells and the number of turns along it. The solution is always the shortest route, found by breadth-first search.

One number helps to read the results: on a 30×30 grid the shortest possible route from corner to corner is 59 cells (29 steps right, 29 down, plus the start). The closer a style gets to 59, the more direct its solution is.

The recursive backtracker starts in a random cell and keeps carving into a random unvisited neighbor for as long as it can. Only when it is boxed in does it back up to the last cell with an unvisited neighbor and branch from there. The result is long, winding corridors — maze designers call them "rivers" — with few branches.

On a 30×30 grid a Classic maze has about 92 dead ends (10% of the cells) but a solution route of about 223 cells with around 140 turns: the route snakes through a quarter of the whole grid. It also varies the most — individual mazes ranged from 97 to 481 cells. This is the traditional puzzle-book look and the default style of every edition in Wisdom Effect.

Kruskal's algorithm shuffles all the inner walls and removes them one by one, skipping any wall whose removal would join two cells that are already connected (it tracks this with a union–find structure). Small corridors appear everywhere at once and slowly merge into one maze, so branches are spread evenly over the whole grid.

A 30×30 Kruskal maze has about 272 dead ends (30% of the cells), three times as many as Classic, and a route of about 96 cells with around 54 turns. There are many plausible wrong turns, but each of them is fairly short.

Randomized Prim grows the maze outward from one cell: it keeps a list of cells next to the maze, picks one of them at random and connects it to the maze. Because the growth spreads in all directions at once, the maze is full of very short side branches.

Prim makes the most dead ends of the three — about 316 on a 30×30 grid (35% of the cells) — but the route is the most direct: about 66 cells with only around 30 turns, barely longer than the 59-cell minimum. Its busy look is real; its difficulty is not, as the next sections show.

The picture shows one maze of each style on the same 30×30 grid and with the same book code. Dead ends are shaded yellow and the solution is drawn in red, as in a Wisdom Effect answer key.

A common claim is that Prim and Kruskal make the hardest mazes because they have the most dead ends. Solving by hand does not work that way. "Hard" has at least three parts: how long the route is (how much work the solver does), how many wrong turns are on offer (how often the solver can get lost) and how busy the page looks.

Prim scores high only on the last two. Its dead ends are short — a wrong turn is usually visible after one or two cells — and because the route runs almost straight toward the exit, a solver who simply heads in the direction of the finish rarely goes far wrong. Prim mazes look the hardest and are usually solved the fastest.

Classic mazes are the opposite: few decisions, but a long journey that often runs away from the exit before it comes back, so the obvious direction is often the wrong one. Kruskal sits in between, with many wrong turns and a moderately winding route.

Grid size beats all of it. A 45×56 Classic maze has a route of about 570 cells; the same grid in Prim, about 112. Pick the size for the audience first, then use the style to shape the experience.

Loops (also called braiding) knock through walls at dead ends, joining them to a neighbor, so the maze gets several routes. In Wisdom Effect the Loops slider sets the share of dead ends that get joined: 0% keeps a perfect maze, 100% removes every dead end.

Loops change a maze more than most people expect. At 50% a 30×30 Kruskal maze drops from about 272 to 87 dead ends, and its shortest route from 96 to 68 cells, because the new openings create shortcuts. A Classic maze with 50% loops drops from a 223-cell route to about 105 cells. With 100% loops there are no dead ends at all.

So loops make a maze measurably shorter and with fewer dead ends. What they add is uncertainty: the solver can no longer rely on "there is only one way", and can walk in circles. Use a little for adult and expert books; the answer key always shows the shortest route.

In the maze configurator the Maze Style panel offers Classic (depth-first search), Kruskal and Prim, each with a real miniature generated by the same engine. The style applies to every shape — rectangles, circular mazes and silhouettes such as the heart — and in every edition. Every maze is generated from the book code, so the same settings always reproduce the same mazes.

The Difficulty presets set the grid size, style and loops in one click. We built them on these measurements: all four Standard presets are Classic mazes, because only Classic makes the route grow together with the grid. Easy is 12×15, Medium 20×25, Hard 30×38 and Expert 45×56 with 10% loops for a little uncertainty. The Kids and Senior presets are Classic too.

The result is a real difficulty ladder — every level has a longer route and more dead ends than the one before: about 59, 145, 287 and 374 route cells, and 20, 52, 116 and 228 dead ends. Our earlier presets used Kruskal for Hard and Prim for Expert; they had more dead ends, but their routes (about 95 and 108 cells) were shorter than Medium's, so a reader could finish an "Expert" maze quicker than a "Medium" one. Kruskal and Prim are still one click away in the Maze Style panel when you want more decisions or a denser look.

There is no best algorithm, only a best fit for the reader. Use these rules as a starting point and check a few pages in the live preview before you export.