Skip to content

Blind Robot in a Maze

Level: L4-L6 Topics: BFS, State Space Search, Maze Solving, Worst-Case Planning

Problem Statement

You have a maze represented as a 2D grid with the following cell types:

  • Wall (#): Impassable.
  • Free space (.): The robot can occupy this cell.
  • Exit (E): The goal cell.

A blind robot is placed somewhere in the maze but does not know its starting position. The robot cannot sense its surroundings — it cannot tell if it hit a wall or where it is. You can issue a sequence of commands: Up, Down, Left, Right. When a command is issued:

  • If the move would take the robot into a wall or outside the grid, the robot stays in place.
  • Otherwise, the robot moves one cell in that direction.

Find a fixed sequence of commands that guarantees the robot reaches the exit, regardless of which free cell it starts in.

Background & Constraints

  • The maze dimensions are small (typically up to 10x10 for this problem).
  • The robot has no sensors — it cannot observe walls, its position, or whether a move succeeded.
  • The same command sequence is executed for every possible starting position simultaneously.
  • The sequence must guide the robot to the exit from every valid starting position.
  • The exit is reachable from every free cell in the maze.

Examples

Example 1:

Maze (E at (0,2), wall # at (1,1)):
. . E
. # .
. . .

A working command sequence: [Left, Left, Up, Up, Right, Right]

Trace from each free starting cell (a "stay" means the robot was blocked
by a wall or the grid edge):

  (0,0): L stay, L stay, U stay, U stay, R->(0,1), R->(0,2)=E
  (0,1): L->(0,0), L stay, U stay, U stay, R->(0,1), R->(0,2)=E
  (1,0): L stay, L stay, U->(0,0), U stay, R->(0,1), R->(0,2)=E
  (1,2): L stay (wall at (1,1)), L stay, U->(0,2)=E, U stay, R stay, R stay
  (2,0): L stay, L stay, U->(1,0), U->(0,0), R->(0,1), R->(0,2)=E
  (2,1): L->(2,0), L stay, U->(1,0), U->(0,0), R->(0,1), R->(0,2)=E
  (2,2): L->(2,1), L->(2,0), U->(1,0), U->(0,0), R->(0,1), R->(0,2)=E

The intuition: pin the unknown position against the top-left corner with
LLUU, then walk RR to the exit.

Example 2:

Maze:
. E
. .

Command sequence: [Right, Up]

From (0,0): Right->(0,1)=E  -- exits
From (1,0): Right->(1,1), Up->(0,1)=E  -- exits
From (1,1): Right->(1,1) [wall], Up->(0,1)=E  -- exits

Hints & Common Pitfalls

  • Think in terms of the set of possible positions. Since the robot doesn't know where it starts, track the set of all cells the robot could currently be in. Initially, this set is all free cells. After each command, update every possible position in the set. The goal is to reduce this set so that every element is the exit.
  • BFS on the power set of positions. The state is the set of cells the robot might occupy. Each command transitions to a new set of positions. Use BFS to find the shortest command sequence that leads to all positions collapsing to the exit.
  • State space can be large. With F free cells, the power set has 2^F states. For small mazes this is tractable.
  • Common mistake: Assuming the robot can sense whether it moved. It cannot — if a move fails due to a wall, the robot doesn't know.
  • Common mistake: Testing the command sequence from only one starting position. It must work from all starting positions simultaneously.

Follow-Up Questions

  1. What if the robot must stop at the exit (not just pass through it)? In other words, once the robot reaches the exit, it stays there regardless of further commands.
  2. What if the robot can sense whether its last move succeeded (i.e., it gets a 1-bit signal: "moved" or "stayed")? How does this change the problem?
  3. What if the maze is unknown — you don't have the maze layout in advance? Can you still design a strategy?
  4. What is the maximum length command sequence needed for an NxN maze in the worst case?
  5. Can this problem be solved with a polynomial-time algorithm, or is it inherently exponential?