À propos des labyrinthes - histoire, labyrinthes parfaits, générateurs et astuces

Labyrinthes et dédales

Un labyrinthe classique n'a qu'un seul chemin sinueux, sans choix. Un dédale a des embranchements et des impasses, il faut donc décider où aller. Les labyrinthes de haies sont devenus populaires dans les jardins européens à partir du XVIe siècle, et les labyrinthes sur papier sont restés un classique depuis.

Labyrinthes parfaits

Un labyrinthe parfait n'a ni boucles ni zones fermées : il y a exactement un chemin entre deux cases. En mathématiques, ses passages forment un arbre couvrant de la grille, donc un labyrinthe de n cases a exactement n - 1 ouvertures entre les cases.

Comment un ordinateur crée un labyrinthe

Le backtracker récursif parcourt la grille au hasard, abat les murs vers les cases non visitées et revient en arrière quand il est bloqué. Il crée de longs couloirs avec peu d'embranchements. L'algorithme de Prim fait plutôt grandir le labyrinthe à partir d'une case, en ajoutant chaque fois une case voisine au hasard, ce qui donne beaucoup de courtes impasses.

Astuces pour résoudre

Dans un labyrinthe parfait, vous atteignez toujours la sortie en gardant une main sur un mur et en le suivant. Ce n'est pas le plus court chemin, mais cela marche toujours. Regarder de la sortie vers le départ peut aussi aider, et une trace vous évite de parcourir deux fois la même impasse.

Questions fréquemment posées

Quelle est la différence entre un dédale et un labyrinthe ?

Un labyrinthe a un seul chemin sans choix ; un dédale a des embranchements et des impasses. Dans la langue courante, les deux mots désignent souvent la même chose.

La règle de la main sur le mur marche-t-elle toujours ?

Dans un labyrinthe parfait, oui, car tous les murs sont reliés. Dans un labyrinthe avec des boucles, vous pouvez tourner sans fin autour d'un îlot.

Quelle taille peut avoir un labyrinthe ?

Ici jusqu'à 100 x 100 cases, soit 10 000 cases avec un seul chemin entre le départ et la sortie.