The Cleaning Robot Puzzle

One robot, rooms full of furniture, a 50,000-command budget — and one short depth-first search that cleans all of it.

This is Part 1, and it solves the original puzzle. Part 2 changes the rules: every floor field gets some dirt, the robot gets a bag that can fill up, and then a battery that runs out. It turns a textbook traversal into a real optimisation problem. Part 3 asks for the shortest route, takes away the map, adds a dock where the bag empties, and brings in a second robot. Parts 4 to 7 keep the square fields but stop the floor being flat: a room that wraps around, a strip with a twist, the walls of a box, and a floor with five squares at every corner. Parts 8 to 11 go back to the flat floor and take its optimisation problems to the tools of operations research, starting with a linear program that bounds the shortest route from below.

The problem

A cleaning robot stands in a room. The room is given as a list of strings, one string per row:

Rows are numbered 0 to R-1 from top to bottom, columns 0 to C-1 from left to right, so (0, 0) is the top-left corner. The room is always surrounded by walls: row 0, row R-1, column 0 and column C-1 are all #.

The robot understands four commands:

The rules:

• The robot cleans every field it visits, including the one it starts on.
• It must never step into a #.
• It may enter the same field many times.
• It may finish anywhere; it does not have to return to the start.

Write a function

def solution(room):

that returns a string of commands that makes the robot clean every floor field.

Constraints

• R and C are between 3 and 40.
• There is exactly one *.
• Every empty field can be reached from the start.
• The answer may contain at most 50,000 commands.

Examples

An empty room with the robot in the bottom-right corner:

An empty room with the robot in the middle, 25 floor fields in all:

And three rooms with furniture:

Two observations that make it simple

1. The budget is enormous

The largest room is 40×40, which leaves at most 38×38 = 1,444 floor fields. A walk that enters and leaves each field once uses at most 2 × 1,443 = 2,886 commands. The limit is 50,000, more than 17 times that. We don’t need the shortest route, only a complete one.

2. The room is a graph, and the robot has to walk

Think of each floor field as a node, with an edge between fields that share a side. “Clean everything” means “visit every node of a connected graph”.

Breadth-first search (BFS) visits nodes in order of distance, jumping around the frontier. A robot can’t teleport, so every jump would have to become a walk.

Depth-first search (DFS) fits a physical robot: keep stepping into a field you haven’t seen, and when you’re stuck, walk back the way you came. The moment a recursive call returns is exactly the moment the robot steps back.

The solution

import sys

def solution(room):
    sys.setrecursionlimit(10000)
    R, C = len(room), len(room[0])
    start = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')

    seen = {start}
    moves = []
    dirs = [(-1, 0, '^', 'v'), (1, 0, 'v', '^'), (0, -1, '<', '>'), (0, 1, '>', '<')]

    def dfs(r, c):
        for dr, dc, go, back in dirs:
            nr, nc = r + dr, c + dc
            if room[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                moves.append(go)
                dfs(nr, nc)
                moves.append(back)   # step back to where we came from

    dfs(*start)
    return ''.join(moves)

How it works, line by line

Raising the recursion limit

sys.setrecursionlimit(10000)

dfs calls itself once for each step deeper into the room. In an empty 40×40 room the search can go 1,443 calls deep. Python stops at about 1,000 by default, so we raise the limit.

Room size

R, C = len(room), len(room[0])

R is the number of strings (rows); C is the length of one string (columns).

Finding the start with next

start = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')

The part inside the parentheses is a generator expression. It produces the (r, c) of every cell equal to '*', lazily, one at a time. The built-in next takes the first item and stops scanning. It is equivalent to:

for r in range(R):
    for c in range(C):
        if room[r][c] == '*':
            start = (r, c)
            break

State

seen = {start}
moves = []

• seen is a set of fields the robot has already visited. It starts with the starting field.
• moves is the list of commands, built up as the robot moves.

The direction table

dirs = [(-1, 0, '^', 'v'), (1, 0, 'v', '^'), (0, -1, '<', '>'), (0, 1, '>', '<')]

Each tuple is (row change, column change, command to go, command to come back):

Storing the reverse command next to each move means backtracking needs no extra logic.

The search

def dfs(r, c):
    for dr, dc, go, back in dirs:
        nr, nc = r + dr, c + dc                          # the neighbour
        if room[nr][nc] != '#' and (nr, nc) not in seen:  # floor, not visited
            seen.add((nr, nc))    # mark it now, so it's never entered twice
            moves.append(go)      # step into it
            dfs(nr, nc)           # clean everything reachable from there
            moves.append(back)    # step back to (r, c)

A few details:

• Mark before recursing. The field is added to seen before the call, so no other branch can enter it a second time.
• No bounds checks. The outer rows and columns are always walls, so a neighbour of a floor field is always inside the grid.
• A closure. dfs is defined inside solution, so it can read room and change seen and moves without passing them around. It never reassigns them, so no nonlocal is needed.

Starting the search: what *start means

dfs(*start)

start is a tuple such as (2, 3), but dfs takes two separate arguments. The * unpacks the tuple:

dfs(*start)              # is the same as
dfs(start[0], start[1])  # is the same as
dfs(2, 3)

Without the star, dfs(start) would pass the whole tuple as r and nothing as c, and Python would raise TypeError: dfs() missing 1 required positional argument: 'c'.

Building the answer

return ''.join(moves)

This glues the list into one string: ['v', '>', '^'] becomes 'v>^'.

A trace on a tiny room

The robot starts at (1, 1):

dfs(1,1)
  ^ (0,1) wall
  v (2,1) new        -> 'v'
    dfs(2,1)
      ^ (1,1) seen
      v (3,1) wall
      < (2,0) wall
      > (2,2) new    -> '>'
        dfs(2,2)
          ^ (1,2) new  -> '^'
            dfs(1,2): every neighbour is a wall or seen, return
          back         -> 'v'
          v, <, >: wall, seen, wall
      back           -> '<'
  back               -> '^'
  < (1,0) wall
  > (1,2) seen

The answer is v>^v<^. The robot walks (1,1) → (2,1) → (2,2) → (1,2) → (2,2) → (2,1) → (1,1), and all four floor fields are clean.

Why it is correct

The robot always knows where it is. Claim: dfs(r, c) starts and ends with the robot standing on (r, c). Each go moves it into a neighbour. By the same claim, the call on that neighbour ends with the robot back on the neighbour, and back returns it to (r, c). So the recorded commands always match the robot’s real position.

It never enters a wall. Every go targets a field that isn’t #. Every back returns to a field the robot was just standing on.

It cleans everything. Suppose some floor field were never visited. The floor is connected, so there is a path to it from the start. Take the first unvisited field on that path. The field just before it was visited, and dfs on that field checked all four neighbours, so it would have entered this one. That’s a contradiction.

It fits the budget. Every field except the start gets exactly one go and one back, so the answer has exactly 2 × (N − 1) commands for N floor fields. That is at most 2,886, against a limit of 50,000.

Complexity. Each field is visited once and checks 4 neighbours: O(R·C) time. seen, moves and the call stack are O(R·C) memory.

Checking it yourself

It’s easy to write a small simulator that replays the commands and reports any field left dirty:

STEP = {'^': (-1, 0), 'v': (1, 0), '<': (0, -1), '>': (0, 1)}

def missed(room, cmds):
    R, C = len(room), len(room[0])
    r, c = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')
    cleaned = {(r, c)}
    for ch in cmds:
        dr, dc = STEP[ch]
        r, c = r + dr, c + dc
        assert room[r][c] != '#', f"walked into a wall at {(r, c)}"
        cleaned.add((r, c))
    floor = {(r, c) for r in range(R) for c in range(C) if room[r][c] != '#'}
    return floor - cleaned

On the five example rooms the solution produces:

It also cleaned every field of 3,000 randomly generated rooms, each answer exactly 2 × (N − 1) commands long, and an empty 40×40 room from every corner and from the centre (2,886 commands each).

The simulator and every check are in test_cleaning_robot.py, and the solution, with both versions from the next section, in cleaning_robot.py.

Going further

Skip the walk home

Once the last new field is cleaned, the remaining back moves only walk the robot home, which the rules don’t require. Remember where the last useful command was and cut there:

    last = 0   # length of moves right after the robot last reached a new field

    def dfs(r, c):
        nonlocal last
        for dr, dc, go, back in dirs:
            nr, nc = r + dr, c + dc
            if room[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                moves.append(go)
                last = len(moves)
                dfs(nr, nc)
                moves.append(back)

    dfs(*start)
    return ''.join(moves[:last])

nonlocal is needed here because last is reassigned. On the tiny room the answer shrinks from v>^v<^ to v>^. In an empty 40×40 room starting from a corner, it drops from 2,886 to 1,443 commands.

No recursion at all

Keep your own trail of steps instead of using the call stack:

def solution(room):
    R, C = len(room), len(room[0])
    start = next((r, c) for r in range(R) for c in range(C) if room[r][c] == '*')
    dirs = [(-1, 0, '^', 'v'), (1, 0, 'v', '^'), (0, -1, '<', '>'), (0, 1, '>', '<')]

    seen = {start}
    moves = []
    trail = []   # (command that undoes the step, field we came from)
    r, c = start
    while True:
        for dr, dc, go, back in dirs:
            nr, nc = r + dr, c + dc
            if room[nr][nc] != '#' and (nr, nc) not in seen:
                seen.add((nr, nc))
                moves.append(go)
                trail.append((back, r, c))
                r, c = nr, nc
                break
        else:                 # no new neighbour: retrace one step
            if not trail:
                break
            back, r, c = trail.pop()
            moves.append(back)
    return ''.join(moves)

The for ... else runs the else block only when the loop finishes without break, meaning no new neighbour was found. This version needs no recursion limit and produces exactly the same commands as the recursive one.

The takeaway

The hard part of this puzzle isn’t the code. It’s reading the rules as permissions. “May enter the same field multiple times”, “may finish anywhere” and “50,000 commands” together say: any complete walk will do. Once you see that, the whole puzzle is one textbook depth-first search, and stepping back through the recursion is the robot walking home.