Guide a mouse to find cheese with APIs

Problem Statement

You are tasked with helping a mouse navigate a 2D grid of unknown dimensions to find a piece of cheese. You do not have access to a grid map. Instead, you interact with the environment via an interface:

class GridEnvironment:
    def can_move(self, direction: str) -> bool:
        # direction: 'up', 'down', 'left', 'right'
        # returns True if the move is valid and not hitting a wall

    def move(self, direction: str) -> bool:
        # moves the mouse in the direction
        # returns True if successful, False otherwise

    def is_cheese(self) -> bool:
        # returns True if the mouse is currently on the cheese

Your goal is to implement a function find_cheese(env: GridEnvironment) -> bool that returns True once the mouse reaches the cheese.

Constraints

• The grid can contain cycles and walls.
• You must visit every reachable cell or find the cheese.
• The state space is finite but the boundaries of the grid are unknown.

Example

• Input: The mouse starts at (0,0). can_move('right') is True, can_move('up') is False.
• Output: A sequence of moves that terminates when is_cheese() returns True.

Edge Cases

• The cheese is unreachable (you should return False after exhausting all options).
• Dead ends or loops in the grid pathing.
• Starting position is already the cheese.