Robot Room Cleaner

Robot Room Cleaner is a backtracking classic with a twist: you cannot see the grid. You only have a robot that can move, turn, and clean. The trick is to run a normal depth-first search while carefully undoing every move so the robot always ends up where it started.

The slow way first

There is no array to scan, so brute force here means wandering blindly — turning and moving at random and hoping to hit every cell. Without remembering where you have been, you clean the same cells forever and never know when to stop. The core difficulty is that the robot has no global map and no coordinates.

The question to ask: how do I avoid revisiting cells when the API gives me nothing to identify a cell? The answer is to invent my own coordinates. I track an (r, c) position and a facing direction myself, updating them every time I move or turn.

The idea: DFS with virtual coordinates and backtracking

Start at (0,0) facing up. Clean the cell and store (0,0) in a visited set. Then try all four directions: for each, compute the neighbour cell from my tracked facing. If that neighbour is unvisited and move() succeeds, recurse into it. When the recursion returns, I must put the robot back exactly where it was — so I turn 180°, move one step back, then turn 180° again. After each direction I turnLeft() once to face the next one.

The key insight: because the robot is physical, recursion alone is not enough — you must physically undo each move so the robot's real position matches the position your code thinks it is at.

Walk through it

Step through the animation. The robot cleans (0,0), moves down to (1,0), then right to (1,1). At (1,1) every direction is blocked or visited, so it backtracks: 180°, move back, 180° again — sliding back to (1,0), then back to (0,0). The visited set fills as cells are cleaned, and each finished cell turns green.

Pseudocode

visited = empty set
dfs(r, c, facing):
    clean current cell
    add (r, c) to visited
    repeat 4 times:
        (nr, nc) = the cell in front given facing
        if (nr, nc) not visited and move() succeeds:
            dfs(nr, nc, facing)
            turn around (180), move back, turn around (180)   # restore position
        turnLeft()                # face the next of the 4 directions
        facing = new facing after a left turn
start dfs(0, 0, UP)

The Python solution

def clean_room(robot):
    visited = set()
    def dfs(r, c, facing):
        robot.clean()
        visited.add((r, c))
        for _ in range(4):
            nr, nc = step(r, c, facing)
            if (nr, nc) not in visited and robot.move():
                dfs(nr, nc, facing)
                robot.turnRight(); robot.turnRight()
                robot.move()
                robot.turnRight(); robot.turnRight()
            robot.turnLeft(); facing = turn(facing)
    dfs(0, 0, UP)

• visited is a set of absolute coordinates — our invented map of where the robot has cleaned.
• dfs(r, c, facing) runs only when the robot is physically standing on (r, c) looking at facing.
• We clean() and record (r, c) first, so the cell is never cleaned twice.
• step(r, c, facing) computes the neighbour in front; range(4) tries all four directions.
• The lookup (nr, nc) not in visited and robot.move() only steps forward when the target is new and actually open.
• The two turnRight() calls form a 180° turn; we move() back and turn 180° again — this restores both position and facing after the recursive call.
• The trailing turnLeft() rotates to the next direction so all four are eventually tried.

Complexity

Let n be the number of open cells. We clean each cell once and try a constant 4 directions from it, so time is O(n). The visited set and the recursion stack are both O(n).

When this pattern shows up

Practice