On part d'un labyrinthe dont tous les murs sont fermés. On crée :

une liste de cellules "non visitées" (pleine au départ)
une liste de murs (initialement les murs adjacents d'une cellule choisie aléatoirement)

Tant qu'il y a des murs dans la liste :

on choisit un mur au hasard dans la liste.
si une seule des deux cellules que le mur divise est visitée, alors :
- on ouvre un passage à travers ce mur
- on marque la cellule "non visitée" comme "visitée" (on la supprime de la liste)
- on ajoute les murs voisins de la cellule à la liste des murs.
on retire le mur de la liste.