Help Mouse Find the Cheese

Let's understand what we're being asked to do. We have a mouse placed somewhere in a grid (like a maze), and there's cheese located somewhere else in that grid. The grid may contain walls that block movement.

We can only interact with the mouse through two methods: move(direction) which attempts to move the mouse in a direction (returns true if successful, false if blocked by a wall or boundary), and isCheese() which tells us if the mouse is currently at the cheese location.

Important constraints: We cannot see the grid layout directly - we can only explore it by attempting moves. We don't know the mouse's starting position or the cheese's position. We can only move in four directions (up, down, left, right).

Key insight: Since we're told the cheese is always reachable, there must exist at least one valid path from the starting position to the cheese. We need to systematically explore the grid to find it.

Edge cases to consider: What if the mouse starts right at the cheese? What if the grid has dead ends? What if there are multiple paths to the cheese (we only need to find one)?

Since we can't see the entire grid, we need to explore systematically. Each time we move to a new cell, we discover what's adjacent to it by attempting moves in all four directions.

The key challenge is: how do we avoid getting stuck in loops? If we visit a cell, move away, and then come back to it later, we might explore the same paths repeatedly forever.

We need a way to remember which cells we've already visited. Once we've explored all paths from a cell without finding cheese, there's no point returning to it.

By marking cells as visited, we ensure we explore each cell at most once, guaranteeing we'll eventually find the cheese (since we're told it's always reachable).

Imagine you're in a real maze with a piece of chalk. Every time you enter a new room, you mark it with chalk. When you hit a dead end, you backtrack to the last room that had unexplored exits.

You keep exploring new rooms (unmarked ones) until you find the cheese. The chalk marks prevent you from wasting time re-exploring rooms you've already checked. This is exactly how we'll navigate the grid - systematically exploring unvisited cells until we reach the goal.

Use depth-first search (DFS) to systematically explore the grid. Start from the mouse's current position and recursively try moving in all four directions. Keep track of visited cells to avoid revisiting them. For each unvisited cell, check if it contains cheese using isCheese(). If not, recursively explore all valid adjacent cells. If we find the cheese, return true. If all paths are exhausted without finding cheese, backtrack. Since the cheese is guaranteed to be reachable, this exploration will eventually find it.

def find_cheese(mouse):
    """
    Use DFS to find cheese in a grid.
    Returns True when cheese is found.
    """
    # Track visited cells to avoid cycles
    visited = set()
    
    def dfs(position):
        # Check if current position has cheese
        if mouse.isCheese():
            return True
        
        # Mark current position as visited
        visited.add(position)
        
        # Try all four directions: up, down, left, right
        directions = ['up', 'down', 'left', 'right']
        
        for direction in directions:
            # Try to move in this direction
            if mouse.move(direction):
                # Get new position (conceptual - we track state)
                new_position = (position[0] + (1 if direction == 'down' else -1 if direction == 'up' else 0),
                               position[1] + (1 if direction == 'right' else -1 if direction == 'left' else 0))
                
                # Only explore if not visited
                if new_position not in visited:
                    # Recursively search from new position
                    if dfs(new_position):
                        return True
                    
                    # Backtrack: move back to previous position
                    opposite = {'up': 'down', 'down': 'up', 'left': 'right', 'right': 'left'}
                    mouse.move(opposite[direction])
        
        return False
    
    # Start DFS from initial position (0, 0)
    return dfs((0, 0))

• DFS/BFS with limited API: When you can't directly access a graph structure but have movement primitives (move, check state), use depth-first search with backtracking - explore each direction, mark visited positions, and backtrack when hitting dead ends to systematically cover all reachable cells.
• Visited state tracking without direct access: Since you can't see the grid, maintain a Set of visited coordinates by tracking your position through successful moves - this prevents infinite loops and ensures you don't revisit the same cell, which is critical when you can only interact through method calls.
• Directional exploration pattern: Systematically try all four directions (up, down, left, right) at each position using a recursive helper function - if move() succeeds, recurse; if it fails or returns false, try the next direction. Always backtrack by moving in the opposite direction after exploring.
• Coordinate tracking with relative movement: Without direct grid access, maintain current position (x, y) coordinates by updating them with each successful move() call - this allows you to track visited cells and implement backtracking by reversing your last move to return to previous positions.
• Early termination optimization: Check isCheese() immediately after each successful move before recursing deeper - this prevents unnecessary exploration once the goal is found and is crucial when working with opaque APIs where you can't pre-compute paths.
• Blind search applications: This pattern applies to robot navigation, maze solving, and API-constrained exploration problems in real systems where you control an agent through limited commands (IoT devices, game bots, automated testing) rather than having full state visibility.