Grid Traversal Strategies

Three approaches to navigating a grid and cleaning dirty cells -- comparing greedy nearest-neighbor, BFS, and DFS traversal strategies.

Problem

A cleaning robot sits on an n x n grid. Some cells are dirty (d), one cell holds the robot (B), and the rest are clean (-). The robot can move UP, DOWN, LEFT, RIGHT, or CLEAN its current cell. Find a sequence of commands that cleans all dirty cells.

Initial Grid:
-d--
-B--
---d
----

Approach

Three strategies, each with different trade-offs:

1. Greedy Nearest Neighbor

• Repeatedly find the closest dirty cell by Manhattan distance.
• Move to it (one axis at a time), clean it, repeat.
• Fast and simple but not globally optimal -- same limitation as greedy TSP.

2. BFS (Breadth-First Search)

• Explore the grid layer by layer from the robot's starting position.
• Clean any dirty cell encountered during traversal.
• Guarantees shortest path to each cell in terms of grid steps.

3. DFS (Depth-First Search)

• Explore as deep as possible along each branch before backtracking.
• Clean dirty cells as they are discovered.
• Uses less memory than BFS on sparse grids but does not guarantee shortest paths.

These traversal primitives show up everywhere -- pathfinding, game AI, reinforcement learning grid-worlds.

Implementation

import random
from collections import deque


def initialize_grid(size, dirt_probability=0.2):
    grid = [['-' for _ in range(size)] for _ in range(size)]
    for r in range(size):
        for c in range(size):
            if random.random() < dirt_probability:
                grid[r][c] = 'd'
    robot_r = random.randint(0, size - 1)
    robot_c = random.randint(0, size - 1)
    grid[robot_r][robot_c] = 'B'
    return grid, (robot_r, robot_c)


def print_grid(grid):
    for row in grid:
        print(''.join(row))
    print()


def find_dirty_cells(grid):
    rows = len(grid)
    return [(r, c) for r in range(rows) for c in range(rows) if grid[r][c] == 'd']


def greedy_search_move_clean(grid, robot, dirty_cells):
    """Greedy nearest-neighbor: always move to the closest dirty cell."""
    robot_r, robot_c = robot
    operations = []

    while dirty_cells:
        nearest = min(dirty_cells, key=lambda x: abs(x[0] - robot_r) + abs(x[1] - robot_c))
        dirty_r, dirty_c = nearest

        while robot_r < dirty_r:
            operations.append('DOWN')
            grid[robot_r][robot_c] = '-'
            robot_r += 1
            grid[robot_r][robot_c] = 'B'

        while robot_r > dirty_r:
            operations.append('UP')
            grid[robot_r][robot_c] = '-'
            robot_r -= 1
            grid[robot_r][robot_c] = 'B'

        while robot_c < dirty_c:
            operations.append('RIGHT')
            grid[robot_r][robot_c] = '-'
            robot_c += 1
            grid[robot_r][robot_c] = 'B'

        while robot_c > dirty_c:
            operations.append('LEFT')
            grid[robot_r][robot_c] = '-'
            robot_c -= 1
            grid[robot_r][robot_c] = 'B'

        operations.append('CLEAN')
        grid[dirty_r][dirty_c] = '-'
        dirty_cells.remove(nearest)

    return operations


def bfs_clean(grid, robot):
    """BFS traversal: explores layer by layer, cleans on discovery.
    Returns the list of (row, col) coordinates cleaned, in visit order."""
    rows, cols = len(grid), len(grid[0])
    queue = deque([(robot[0], robot[1])])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = {(robot[0], robot[1])}
    cleaned = []

    while queue:
        r, c = queue.popleft()
        if grid[r][c] == 'd':
            grid[r][c] = '-'
            cleaned.append((r, c))

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))

    return cleaned


def dfs_clean(grid, robot):
    """DFS traversal: explores depth-first, cleans on discovery.
    Returns the list of (row, col) coordinates cleaned, in visit order."""
    rows, cols = len(grid), len(grid[0])
    stack = [(robot[0], robot[1])]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited = {(robot[0], robot[1])}
    cleaned = []

    while stack:
        r, c = stack.pop()
        if grid[r][c] == 'd':
            grid[r][c] = '-'
            cleaned.append((r, c))

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                stack.append((nr, nc))

    return cleaned


# Demo
size = 4
grid, robot_pos = initialize_grid(size)
print("Initial Grid:")
print_grid(grid)

dirty = find_dirty_cells(grid)
cmds = greedy_search_move_clean([row[:] for row in grid], robot_pos, dirty)
print(f"Greedy Commands: {cmds}\n")

bfs_cleaned = bfs_clean([row[:] for row in grid], robot_pos)
print(f"BFS Cleaned cells: {bfs_cleaned}\n")

grid2, robot_pos2 = initialize_grid(size)
dfs_cleaned = dfs_clean([row[:] for row in grid2], robot_pos2)
print(f"DFS Cleaned cells: {dfs_cleaned}")

Complexity

Strategy	Time	Space
Greedy	O(d^2 * n) where d = dirty cells	O(d)
BFS	O(n^2) full grid traversal	O(n^2)
DFS	O(n^2) full grid traversal	O(n^2)

Takeaway

Greedy nearest-neighbor is a fast heuristic, BFS gives shortest unweighted paths, and DFS is the backbone of backtracking search. If you ever train an RL agent on a grid-world, these are the baselines you measure it against.

---

Back to Software Design