A Blind Robot in a Maze

What’s going on

A robot is somewhere in a maze of square cells with a single exit. You have a map of the maze, but the maze is covered, so you cannot see the robot, and it sends nothing back. You can only radio four commands: up, down, left, right. If a wall is in the way, the robot does nothing.

Is there one program, a fixed list of commands, that brings the robot out wherever it started?

A cloud of possibilities

Since we do not know where the robot is, the scene puts a dot in every cell: each dot is one place where it might be. Every command moves all the dots at once, because whichever dot is the real robot, it obeys.

Press a few arrows. Some dots move, some bump into a wall and stay put. When two dots land in the same cell they merge, and from then on they move together for ever: a robot’s future depends only on where it is now, not on how it got there. The number on a dot says how many starting cells have merged into it.

So the cloud can only shrink. Dots that walk out through the exit are gone. Your aim is to make every dot leave.

A plan that always works

Here is a method that can never fail.

1. Pick one dot, say the one farthest from the exit.
2. Pretend the robot is there and send it out by a shortest route. All the other dots obey the same commands, wherever that takes them.
3. That dot is now outside. Some others may have left too. If any dots remain, go back to step 1.

Each round removes at least the dot we chose, and there are only as many dots as cells, so after a few rounds every dot is out. Glue the rounds together and you have one program that works for every start.

Press Solve to watch it. In the maze that opens the scene, 36 cells:

• round 1: the farthest dot needs 13 moves; afterwards only 11 of the 36 dots are left, in 4 cells;
• round 2: 9 moves, and just one cell is left (two dots have merged in it);
• round 3: 4 moves, and the cloud is gone.

That is 26 moves in all. You can click any cell with a dot to send that dot out instead, or mix clicks and arrows, and try to beat 26.

How short can a program be?

The farthest cell in this maze is 13 moves from the exit, and no program can rescue a robot from there in fewer moves. So every program has at least 13 moves. The method above is not always the shortest, but it is never stuck, and it shows something surprising: a robot you know nothing about can still be rescued for certain.

Notice also that once the robot is out, you usually cannot say where it started. Many starting cells end with the same escape.

Try it yourself

1. A corridor

The maze is a single row of five cells, with the exit in the outer wall at the right end. What is the shortest program that works from every cell?

Answer

Right, five times. A robot in the leftmost cell needs five moves to get out, so nothing shorter can work. Five rights are enough: robots that leave early are simply gone, and extra moves do not matter.

2. You do not have the map

Now you do not even know where the walls are. You only know that the maze is 100 × 100 cells with one exit somewhere in its outer wall, and that the robot can get out. Is there still a program that surely rescues it?

Answer

Yes. There are only finitely many such mazes, so give each pair (maze, starting cell) its own round, just like the dots above. For each pair, work out where the robot would be now if that guess were true, and send it out from there. When the true pair's turn comes, the robot leaves. The program is unimaginably long, but it is finite.

3. Unknown size

What if you do not know the size of the maze either?

Answer

Go through the sizes one by one: all 1 × 1 mazes, then all 2 × 2 mazes, then 3 × 3, and so on, handling each finite batch with the method of puzzle 2. The program never ends, but the robot's true maze has some size, so after some finite number of commands it is out.

Go deeper

• A program that brings every possible position to the same result is called a synchronizing word. Such words are studied in automata theory, and they are used to put a machine into a known state when nobody knows its current state.
• The Černý conjecture, open since the 1960s, asks how long the shortest synchronizing word can need to be for a machine with a given number of states.