2 ms·
Are there efficient algorithms to generate uniformly random mazes? i.e. selects a maze randomly with uniform probability from the set of all valid mazes.
by jules 16y ago
Are there efficient algorithms to generate uniformly random mazes? i.e. selects a maze randomly with uniform probability from the set of all valid mazes.
- jamis 16y agohttp://www.astrolog.org/labyrnth/algrithm.htm#perfect http://www.astrolog.org/labyrnth/algrithm.htm#perfect says that both the Aldous-Broder and Wilson's algorithms will generate "all possible Mazes of a given size with equal probability". But neither meets your criteria of "efficient", since neither is even guaranteed to finish. I'm curious, too, whether there is an efficient algorithm with the same property (generate any valid maze with equal probability).