That's an interesting algorithm.  I can intuitively see why it works, but want to think of how I could prove it.  One could put a start and endpoint to the maze in that case.

The traversal algorithm through a maze generated like that would probably just be a right-hand-rule variant since the walls would be a single connected component.  The purely random generation that I mentioned in the podcast does not guarantee that of course meaning the right-hand rule could just lead the mouse in a circle forever.

Two ways that immediately spring to mind for ensuring the mouse always makes it to the cheese (barring running out of energy, eaten by cat, etc..) are:
  * scan the maze and mark the connected components and ensure that the mouse and the cheese land in the same connected component
  * scan the maze, mark the connected components and then take pairs of independent connected components and break walls between them to connect them until the maze is a single connected component.

Your generation approach produces a much more sane and generally pleasing looking maze.  I'm wondering if there's a good way to then take that and "shake it up a little" to allow for disconnected wall segments, and such while retaining much of the pleasingness.

Of course there's another possibility:  add the notion of "teleporters" to the maze.  :)

Thanks for the insight and the algorithm.  That's what I like best about this little exercise:  there are so many variations that one can make on it.