Labyrinthes : principes pour en réaliser des difficiles

Cet article s’inspire très largement de cet article.

Je parle souvent des aspects techniques concernant les labyrinthes (temps de calcul, taille qu’ils prennent, etc.). Néanmoins, les labyrinthes ont un côté particulièrement humain et intéréssant : leur difficulté. Réussir à concevoir un labyrinthe difficile est toujours bien plus que le simple fait de réaliser un labyrinthe très grand, même si, avouons le, ça aide quand même pas mal (sourire). Voici quelques principes à partir desquels vous pourrez construire vous-même des algorithmes qui augmentent la difficulté d’un labyrinthe :

• Le ratio :
  Pour des labyrinthes dont les cellules ont le même volume, un labyrinthe avec des dimensions plus proportionnelles peut être plus difficile à résoudre.
  Par exemple, un labyrinthe de 25 x 40 (1000 cellules au total) sera plus difficile qu’un de 4 x 250 (1000 cellules aussi, au total). C’est pour cette raison que des labyrinthes en 3D sont bien plus difficiles à résoudre que des labyrinthes en 2D avec le même volume (dans notre exemple, un labyrinthe 3D de 10 x 10 x 10 cellules (toujours 1000 cellules au total) sera le plus difficile des trois à résoudre).
• Le nombre de solutions :
  Plus un labyrinthe a de solutions possibles, plus il est facile. Les labyrinthes les plus difficiles à résoudre sont ceux qui n’ont qu’une seule solution.
• Longueur de la solution :
  Souvent, plus le chemin pour arriver à la solution est long, plus le labyrinthe est dur à résoudre. Ce n’est pas systématiquement vrai, car parfois un labyrinthe vraiment bien pensé peut être très dur à résoudre, même si la solution est courte. Dans ce cas là, si vous ne la trouvez pas rapidement, vous allez vous promener dans tout le reste du labyrinthe sans réussir à la trouver. Quelque chose est cependant certain : un chemin long pour arriver à la solution vous garantit que ceux qui vont essayer de la trouver passeront un minimum de temps dans le labyrinthe, même s’ils sont chanceux.
• Les courbes :
  Un labyrinthe irrégulier est toujours plus difficile à résoudre qu’un labyrinthe régulier construit sur une grille classique. On est difficilement désorienté dans un labyrinthe « droit ». Alors que dans un labyrinthe avec des angles tordus, des courbes subtiles, des cellules positionnées de manière asymétrique vous serez facilement désorienté.
• Les boucles :
  Avoir des boucles ou des portions de murs détachés peuvent rendre un labyrinthe plus difficile, simplement parce que celui qui tente de le résoudre ne saura pas qu’il est arrivé au bout et continuera dans sa recherche jusqu’à s’apercevoir qu’il tourne en rond. Notez bien que cela ne contredit pas ce qui est expliqué juste avant : si les boucles ne font pas partie du chemin vers la solution, elles rendent le labyrinthe plus difficile au lieu de le rendre plus facile.
• Ne pas pouvoir suivre un mur :
  Lorsqu’on résout un labyrinthe, que ce soit un grandeur nature ou un sur papier, la plupart des personnes suivent un mur. Dans les labyrinthes les plus difficiles, ça ne doit pas pouvoir fonctionner : si vous suivez un mur, vous devriez vous retrouver au point de départ. Pour créer un labyrinthe de ce genre, il vous faut le départ ou l’arrivée au centre du labyrinthe, et une boucle disposée autour (voir paragraphe précédent). Les ponts peuvent être utilisés pour empêcher de suivre un seul mur : vous placez un pont à un endroit, au bout du pont, vous faites en sorte que si on va à droite ou à gauche, les murs de droite et gauche se rejoignent en une boucle.
• Tournants :
  Les passages qui ont l’air d’aller dans un sens, mais qui, à la fin, finissent à l’opposé, rendent un labyrinthe plus difficile. Un excellent exemple : les spirales. Dans une spirale c’est très difficile de deviner où un passage va vous mener sans le suivre réellement.
• Choix non intuitifs :
  Psychologiquement parlant, la plupart des gens ont tendance à faire des choix, sur les intersections, parmi ceux qui les rapprochent de l’arrivée. Un labyrinthe qui a des passage qui ont l’air de s’éloigner de l’arrivée, alors que ce sont ceux-là qu’il faut emprunter pour y arriver, sera beaucoup plus dur à résoudre. De plus, les personnes qui vont essayer de le résoudre auront du mal à trouver l’arrivée, parce qu’on a toujours une fâcheuse tendance à vouloir éviter de « revenir en arrière ». Autrement dit, si on sait qu’on s’éloigne de l’arrivée, on pense qu’il va falloir « revenir » dans l’autre sens, et ça ne plaît pas. Et enfin, beaucoup de personnes ont tendance à aller à droite lorsqu’ils ont des choix qui semblent identiques, peut-être parce que beaucoup de gens sont droitiers, ou que l’on conduit à droite, etc. Bref, un labyrinthe qui a des passages qui s’éloignent de l’arrivée et qui tournent à gauche, pour y arriver, sont plus difficiles à résoudre, et cela uniquement en se basant sur un critère de psychologie humaine.
• Répetition :
  Lorsque dans une labyrinthe assez grand, il y a des motifs identiques, il est assez facile à résoudre parce qu’il aide à avoir des points de référence. Inversement, le fait d’avoir des endroits très similaires mais qui se comportent différemment déroutera la plupart des personnes : la mémoire, dans ce cas là, risque plutôt de les induire en erreur, plutôt que de les aider.
• Différence de genre :
  Même si on ne peut pas appliquer le principe à tout le monde, les approches pour résoudre un labyrinthe sont différentes si la personne est un homme, ou si elle est une femme. En général, les femmes essaient de se repérer avec des marques particulières, des repères dans l’espace, des « motifs » qu’elles ont vus et ainsi progressent souvent de cette façon, alors que les hommes sont beaucoup plus axés sur la position physique et précise dans l’espace, ils pensent en terme de position absolue. Donc un labyrinthe sera plus ou moins difficile selon que la personne soit un homme ou une femme.