Let’s imagine we find ourselves at the entrance of a labyrinth. We just know that there is definitely an exit along the perimeter, but we don’t know where is found. If we enter this labyrinth, how can we be sure we can get out? And would we be able to find the shortest route? If we cannot see the labyrinth from abovethere are three possible strategies that we can exploit to ensure we get out: the “rule ofright hand”, the algorithm of Tremaux and the algorithms of “breadth-first search”. These maze-solving algorithms are not only orientation exercises, but are also applied in computer science, robotics and video games. In this article we see how they work and what the possible solutions are to get out of a labyrinth.
Exiting a labyrinth, the hand rule: we place it on the wall at the entrance, then we follow the wall

“The right (or left) hand rule” allows us to solve a maze even with your eyes closed. This is one of the simplest algorithms: at the entrance we decide which hand to use and which side of the wall to follow. We support there hand al wall and then we start to walk without never detach it. With this technique we are sure of succeeding find the exit in all the labyrinths they have a single entry And only one exit. Be careful, though, that we can’t use it if we meet already inside the labyrinth and here we are lost. In that case, we might accidentally put our hand on a “cycle” or “island”, i.e. a set of walls disconnected from the main walllike the ones colored blue in the image. If we placed our hand on one of these walls and continued to follow them using the right hand rule, we would find ourselves loop without ever reaching the exit.

A strategy that allows us to find the solution in all types of mazes, even those in which there are loops or where the goal is not to find the exit, but a central room with a prize, is the Trémaux, a depth-first search algorithm.
We go back if we find a dead end, an intersection we have already seen and we mark where we have already passed
In order to use theTrémaux algorithmwe have to bring something with us for mark intersections and roads that we are meeting. In fact, with this algorithm, we must take note of every crossroads, explore each road thoroughly and, every time we reach a dead end or a loop, return to the last intersection and try a different route. This strategy is known as “search in depth” (depth-first search) and consists ofgo the most thoroughly possible in the labyrinth and only go back when he can no longer go forward.

Concretely, what happens is that let’s start walking in the maze following the road until we come to a alley sky (in that case we go back) or a intersection. At this point, there are three possibilities:
- AND the first time we come to that intersection: If it’s the first time we’ve seen that intersection, we mark the route we came from, then arbitrarily choose a direction to continue in and mark that too.
- It’s the second time we arrive at that intersection, but from another direction: If we have already seen that intersection but had not yet arrived there from this direction, then we mark the connection between the direction we came from and the intersection with two signs (or with an “x”) and then go back. A path with two signs is treated as a wall and we cannot travel it again. This mechanism allows us to escape loops.
- We have already been to those at that intersection and we get there from a road we have already seen: If the intersection has already been visited and we arrive from a route that already has a sign, then we mark it a second time and arbitrarily choose a direction among the routes without signs, if there are any, or among the routes with only one sign. In any case, we add a sign to the chosen direction.

This algorithm succeeds in solve all types of mazes and, by placing two signs to close the roads that do not lead to the solution, it allows those arriving after us not to get lost and to reach the exit, because they know that they must treat those two signs on the ground as if they were walls and only follow the streets with a single sign. This method, however, does not guarantee that the street that we will show to others will be the shorter. To do this, we need to use “breadth-first” search, not depth-first.
Finding the shortest path: Explore breadth, not depth
The “breadth-breadth search” (breadth-first search) is a strategy related to the Trémaux algorithm, but, rather than exploring the routes it finds to the end, this algorithm aims to explore all the possibilities, so as not to miss the shortest solution, the one that optimizes the route. This algorithm guarantees us that we will succeed to find the shortest path between entry and exitbut we will work hard a very long time. If we follow this strategy, we walk until we come to an intersection A, then we choose an arbitrary direction and continue walking until we encounter another intersection (B). At this point, we go back to check the road we had previously ignored (the remaining one at intersection A) and continue until we find intersection C. Once we see intersection C, we return to intersection B to explore the other possibilities doing back and forth several times. To do what we have described, the algorithm essentially reduces the maze to a diagram, and then finds the shortest route from one end to the other.

To do this, follow all the streets until we find the exit, walking and retracing the paths of the labyrinth/diagram dozens and dozens of times. As we can imagine, this algorithm is only useful if we are marathon runners or if we can do computer simulations and then follow the shortest route which indicates to us.