Est-ce vrai que suivre le mur de droite dans un labyrinthe nous mène à la sortie ? Pourquoi ?

---

---

Est-ce vrai que suivre le mur de droite dans un labyrinthe nous mène à la sortie ? Pourquoi ?

La méthode du mur de droite dans les labyrinthes

La méthode du mur de droite est une stratégie couramment utilisée pour résoudre les labyrinthes. Selon cette méthode, il suffit de suivre le mur de droite tout au long du labyrinthe jusqu’à atteindre la sortie. Mais est-ce vraiment vrai ?

En effet, suivre le mur de droite dans un labyrinthe conduit toujours à la sortie si le labyrinthe satisfait à certaines conditions. Cette méthode fonctionne efficacement dans les labyrinthes connexes simples sans boucles ou chemins cachés.

Algorithme du mur de droite

L’algorithme du mur de droite est basé sur le concept que si vous suivez toujours le mur de droite, vous finirez par atteindre la sortie. Lorsque vous entrez dans le labyrinthe, vous tournez vers la droite et continuez à suivre le mur de droite à chaque intersection. Si vous rencontrez un mur à droite, vous continuez tout droit jusqu’à ce qu’une nouvelle intersection soit atteinte et que vous puissiez tourner à droite. Ce processus est répété jusqu’à atteindre la sortie.

Quand cela fonctionne-t-il ?

Cette méthode de résolution du labyrinthe ne fonctionne que lorsque le labyrinthe est simplement-connecté, c’est-à-dire qu’il n’y a aucune boucle ou chemin caché. Dans un labyrinthe simplement-connecté, il est possible de rejoindre n’importe quelle position depuis n’importe quelle autre position en suivant les murs. Si le labyrinthe est simplement-connecté, il est garanti qu’en suivant le mur de droite, vous finirez par atteindre la sortie.

Pourquoi cela fonctionne-t-il ?

Cette méthode fonctionne grâce au théorème de la main droite. En suivant le mur de droite, vous pouvez être sûr de parcourir chaque partie du labyrinthe sans jamais vous perdre, à condition qu’il n’y ait pas de boucles ou de chemins cachés.

L’idée sous-jacente est de toujours garder le mur à sa droite, ce qui garantit que vous n’explorerez jamais une zone déjà visitée et que vous finirez par atteindre la sortie.

Exemple avec un labyrinthe

Prenons un exemple de labyrinthe simple pour illustrer cette méthode :

   ###############

   #S            #

   # ### ###### #

   #   #       # #

   ### # ##### # #

   #   #   #   # #

   # ### # ### # #

   #     #   #   #

   # ######### ##

   #             #

   ###############

Dans cet exemple, S représente le point de départ et # représente les murs du labyrinthe. En suivant le mur de droite depuis le point de départ, la solution serait la séquence de déplacements suivante :

   DROITE, DROITE, DROITE, BAS, BAS, BAS, BAS, DROITE, DROITE, DROITE, DROITE, DROITE, DROITE, HAUT, HAUT, HAUT, DROITE, DROITE, DROITE, DROITE, DROITE, DROITE, DROITE

En suivant cette séquence de déplacements, nous atteignons la sortie du labyrinthe.

Références

1. Build a Maze Solver in Python Using Graphs (consulté le 10 août 2023)
2. Maze-solving algorithm (consulté le 10 août 2023)
3. Learn How to Think – with Karel the Robot (consulté le 10 août 2023)