The Slow Journey to Freedom

Task

Given a connected rectangular maze $n\times m$ cells, one of which is designated as the exit. A turtle appears in a random cell and can move in four directions (up, right, down, left).

The turtle does not think logically, but has an impeccable memory. It can remember and execute any finite sequence of commands. The turtle cannot move through the walls of the maze, and therefore simply ignores the command if it cannot execute it and moves on to the next one.

As soon as the turtle finds itself in the “exit” cage, it immediately leaves the maze and no longer executes any commands.

The location of the walls of the labyrinth and the “exit” cage are known in advance, but the initial location of the turtle is unknown.

Help the turtle get out of the maze. Write the final sequence of commands (up, right, down, left), which guarantees her exit regardless of her initial location.

For example, for the turtle shown in Fig. 1 the following sequence is suitable: down, left, left, up, right, up, up, up, up, left, down, left, up. However, it is easy to see that this sequence will not work if the starting position of the turtle is moved, for example, to the lower left corner.

You don't know the turtle's starting location. Your sequence of commands should be universal, that is, lead the turtle out of the maze regardless of its starting position.

At the entrance you are given a labyrinth with an “exit” cell. It is guaranteed that the maze is connected: it is possible to walk from any cell to any other.

Come up with an algorithm that uses a labyrinth to construct a universal sequence of commands for the turtle.

Solution

First attempt to solve

Let's create a route for each cell that leads the turtle to the exit. Since there is a finite number of cells in which a turtle can be located, namely $n\cdot m - 1$ then we’ll simply write down all such routes and go through them in any order.

If the turtle followed the route and did not find a way out, then we will continue to go through the options, first returning to the starting position and canceling the commands from right to left. For example, for the route right, up, left first cancel the third action – execute rightthen the second one – let's do it downthen the first thing – let's do it left. Thus we get a new sequence right, down, left.

Everything's great, right? But there is one thing But.

Consider the turtle in Fig. 2. Let her have a sequence consisting of one single command right. In this case, the turtle will run into the wall on the right, so it will not do anything. However, if we try to cancel this operation, we will have to ask the turtle to go left (execute left), which will lead her to a completely different place from where she started.

So we don't really know how to undo moves and return the turtle to its original position, which ruins our first attempt and we fail.

Work on mistakes

In the first attempt, we still realized something important: for each cell of the maze we can write out a path to the exit.

Let's just choose one arbitrary cell and write a sequence of commands that leads the turtle to the exit. If the turtle actually ended up in this cage, then we are lucky and don’t need to do anything else. By the way, even if the turtle started from a different cell, the prefix of our sequence could lead it to the exit, which is only better.

However, if a miracle did not happen, then the turtle is now still somewhere in the maze. But where exactly could it be?

In fact, there are not as many options as it seems at first glance. Initially, the turtle was in one of the $n\cdot m - 1$ cells, but having completed this route she could go to one of $n\cdot m - 2$ cells, if not out. Thus, the number of options for the new location is at least 1 less than it was originally.

Figure 3 depicts roughly what happened in set theory terms. On the left is a set of cells before executing a set of commands, on the right is after. Blue dots indicate cells that could theoretically house a turtle. As you can see, due to the fact that at least one blue dot (cell) is guaranteed to go to the “exit” cell, at least one white dot will appear on the right (a cell to which this sequence of commands will never lead us).

At this point you may have already guessed where I'm going with this 🙂

In the next step, we will select any other blue point (a cell with a turtle) and build a route from it to the exit. Having followed the route, the number of possible cells for the turtle will again decrease by at least one. We will continue in the same spirit until the blue cells run out completely. In total we will need no more $n\cdot m - 1$ such iterations to successfully complete the process and ensure that the turtle is released before it starves to death.

Fun fact: turtles can go hungry for months at a time. Their body is adapted to such conditions due to its slow metabolism 🙂

Conclusion

Thank you for reading to the end. If you liked it, click the up arrow, it really motivates me to continue sharing interesting problems and their analyzes with you.