The backtracker does not just make a maze, it makes a perfect one, exactly one path between any two cells. Today you verify that property directly by counting passages and checking full connectivity.
Verify a generated maze is perfect, N*M cells connected by exactly N*M-1 passages.
A maze generated this way is not just any maze, it is a perfect maze: there is exactly one path between any two cells, no loops and no walled-off regions. That is the same thing as saying the rooms and passages form a spanning tree of the grid, and trees have a crisp signature you can check with counting.
Two facts together prove it. First, a tree on N nodes has exactly N-1 edges, so a
perfect maze of W*H rooms must have exactly W*H-1 passages, here 8 passages for 9
rooms. Second, it must be connected: a flood that steps only through carved
passages, starting anywhere, must reach every room. Connected and one edge short
of a cycle can only be a tree, so those two checks together certify perfection. This
property is exactly what makes a maze’s solution unique, which the capstone leans
on, and it holds for any generator that carves a spanning tree, including the second
one you build next.
// count passages: len(m.links)// connectivity: BFS/flood over cells, stepping cell -> neighbor only// when m.Linked(cell, neighbor); count how many cells are reached.// perfect maze <=> passages == W*H-1 AND reached == W*H// (a tree: connected, and one fewer edge than nodes means no cycle)