# Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze? I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if our partner is given the "move right" command when there's a wall on the right, he will simply stay where he is.

In other words, we're given a maze, and we must choose a sequence of commands. Then, our partner will be placed somewhere in the maze and will follow the sequence of commands we've chosen in advance. We want this sequence to ensure our partner will escape, no matter where our partner was initially placed. Note that the allowable commands do not have any conditional statements, so they cannot follow a different sequence depending on your partner is.

Is there a polynomial-time algorithm to construct such a sequence, given a description of the maze?

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences. I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem. Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case. I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A* search this way.

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Feb 11, 2019 at 19:53
• Eppstein's strategy for monotonic automata is to cluster states so that rather than looking for a path in the full power set of states he looks for a path in a graph with only polynomially many vertices. The most natural generalisation of intervals to 2D that I can think of is the convex hull, but unfortunately it's not clear that their number grows polynomially. Commented Feb 26, 2019 at 23:29
• Are up, down, left, and right absolute directions, or relative to the most recently moved direction? Commented Dec 30, 2022 at 2:17
• Do you get feedback? “Turn right”. “I can’t, there is a wall”. Commented Dec 30, 2022 at 8:57

One optimal solution for this problem is A* with iterative deepening (IDA*) as described in the accepted answer to my puzzle. I am not sure whether IDA* is a polynomial-time algorithm in general, but the following sheds some light.

• Does a solution always exist? Commented Jan 17 at 18:52
• Knowing the maze, you can determine all positions from which you can leave in k steps, for k = 1. 2, 3 etc. This should cover all positions inside the maze unless there is a wall around you. Commented May 15 at 14:46

Let’s say there are n positions in the maze, there are not all walls around you so leaving is possible, then for each position you can find the shortest path to the outside, and that path has length <= n. Getting out in n^2 steps is easy:

For each possible position find the shortest path to the outside and its length. You know you are in one of n positions. Find one with a shortest path to the outside and turn that path into instructions.

There are k >= 1 starting positions where you are now outside (for example all positions left of an exit). So either you are on the outside, or in one of n-k positions, and you can determine which ones. Actually, the number of possible positions is often less than n-k, because the walls can turn multiple start positions into the final end position. If you tried the path “one step to the left”, then being exactly to the right of a wall and one step away will move you to the same place at the right of that wall.

If you are not on the outside, you repeat the same method again until you reach the outside. I’m not sure if choosing the shortest paths first is optimal; if there are 200 positions in the labyrinth then a path of length 150 would have a reasonable chance to get outside, plus many possibilities to reduce the number of points where you can end up.

This assumes that the only feedback you get is when you are outside the wall.

Iterative deepening might take exponential time. Let’s say the longest shortest path has length 100. Trying fewer than 100 instructions won’t work. Try 100 instructions: First you need an instruction that leads to a point with distance <= 99, wherever you are. Calculate all points that this instruction leads you, then find an instruction leading only to points with distance <= 98, and so on. If this doesn’t work you try 10- instructions and so on.

In this case if you try to find a sequence of 150 instructions, you would have a free choice for the first 50, so you need to remove duplicates somehow.

An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $$A^*$$ (A-star) algorithm, it was originally designed for just such tasks).

• You cannot encode wall-following as a fixed sequence of Cardinal directions. The choices depend on the walls around you, which is specifically disallowed by the question. Commented Aug 16, 2019 at 14:20
• If you know the shortest path, you can encode it as "move left, then straight, then...". If you don't know the shortest path, you can't give such directions for the shortest way out. If you don't know a path, you can't give directions to get out. Commented Aug 16, 2019 at 14:26
• The real problem is it doesn’t work if the maze has an internal wall that is not connected to the outside wall. You’ll walk round and round the internal wall. If your left hand is on a one piece vertical wall you go up-left-down-down-right-up forever. Commented Dec 30, 2022 at 9:02