About

A perfect maze has exactly one path between any two cells. This property emerges from the Recursive Backtracker algorithm, a randomized Depth-First Search that carves passages through a grid of R × C cells. The algorithm maintains a stack of visited cells and backtracks when it reaches a dead end. The result is a spanning tree of the grid graph. Getting maze generation wrong produces trivial mazes with obvious shortcuts or disconnected regions. This tool generates guaranteed-perfect mazes and solves them using BFS to find the shortest path in O(R ⋅ C) time. Note: animation speed affects only visualization. The underlying algorithm completes in milliseconds for grids up to 100 × 100.

Formulas

The Recursive Backtracker treats the grid as an implicit graph where each cell is a vertex and shared walls are edges. The algorithm is an iterative DFS:

push(start) → mark visited

while stack ≠ ∅:

current = peek(stack)

neighbors = unvisited(current)

if |neighbors| > 0:

next = random(neighbors)

removeWall(current, next)

push(next) → mark visited

else: pop(stack)

Total cells visited: N = R × C. Walls removed: N − 1 (spanning tree property). Solution path found via BFS from cell (0, 0) to cell (R − 1, C − 1), guaranteeing shortest path length L in unweighted graph.

Where R = number of rows, C = number of columns, N = total cells, L = solution path length.

Reference Data

Algorithm	Type	Bias	Dead Ends	Complexity	Perfect Maze
Recursive Backtracker (DFS)	Carving	Long corridors	Few	O(R ⋅ C)	Yes
Kruskal’s	Wall removal	Uniform	Moderate	O(E log E)	Yes
Prim’s	Growing tree	Short corridors	Many	O(E log V)	Yes
Eller’s	Row-by-row	Horizontal	Moderate	O(R ⋅ C)	Yes
Aldous-Broder	Random walk	Uniform (unbiased)	Moderate	O(R² ⋅ C²) avg	Yes
Wilson’s	Loop-erased walk	Uniform (unbiased)	Moderate	Variable	Yes
Hunt-and-Kill	Hybrid carving	Long corridors	Few	O(R ⋅ C)	Yes
Sidewinder	Row-by-row	Vertical top bias	Moderate	O(R ⋅ C)	Yes
Binary Tree	Per-cell	Diagonal (NE/NW)	Many	O(R ⋅ C)	Yes
Growing Tree	Configurable	Depends on selection	Varies	O(R ⋅ C)	Yes
Recursive Division	Wall adding	Long walls	Many	O(R ⋅ C log)	Yes
BFS (Solving)	Pathfinding	N/A	N/A	O(V + E)	N/A

Frequently Asked Questions

A perfect maze has exactly one path between any two cells, meaning it contains no loops and no isolated regions. The Recursive Backtracker guarantees this because it constructs a spanning tree of the grid graph. It visits every cell exactly once and removes exactly N − 1 walls for N cells, which is the definition of a tree on N vertices.

DFS explores as deep as possible before backtracking. This creates a strong directional bias: the algorithm tends to carve long, winding passages before hitting a dead end. Compare this to Prim's algorithm, which grows outward from a frontier and produces shorter, bushier corridors with more dead ends.

Generation is O(R ⋅ C). A 10 × 10 maze processes 100 cells. A 100 × 100 maze processes 10,000 cells, still under 50ms on modern hardware. Solution difficulty (measured by path length relative to grid area) typically increases with size. The ratio LN tends toward 0.25 - 0.35 for DFS-generated mazes.

Yes. The PNG export renders at the canvas resolution. For print-quality output at 300DPI, use a larger grid with a larger cell size. A 25 × 25 maze with 20px cells yields a 500 × 500px image, approximately 1.67in at 300DPI. Scale cell size proportionally for your target print dimensions.

BFS explores all cells at distance d before any cell at distance d + 1. In an unweighted graph (all edges have cost 1), the first time BFS reaches the target cell, it has found the shortest path. This is provably optimal for unweighted graphs. DFS-based solvers may find a path, but not necessarily the shortest.

The algorithm handles it correctly. Generation of 40,000 cells completes in under 200ms. However, animated visualization at that scale may be slow. The tool automatically disables animation for grids exceeding 5,000 cells and generates instantly. Canvas rendering remains smooth because walls are drawn as lines, not individual pixels.