Cat and Mouse II: Game Theory on a Grid

You are given a rows x cols grid of characters where 'C' is the cat's starting position, 'M' is the mouse's starting position, 'F' is the food, '#' is a wall, and '.' is open floor. The mouse moves first. On each turn, the current player can jump 1 to mouseJump (or catJump) steps in one of four cardinal directions, or stay in place. A jump stops early if it hits a wall. The mouse wins by reaching the food before the cat. The cat wins by landing on the mouse, reaching the food first, or if the game lasts 1000 turns without the mouse winning. Return true if the mouse can guarantee a win with optimal play from both sides.

This is LeetCode 1728: Cat and Mouse II, and it is one of the hardest game theory problems on the platform. It combines grid traversal with adversarial search, forcing you to reason about optimal play for two agents on a 2D board.

Why this problem matters

Game theory on grids is a rare pattern in interviews, but when it shows up, it separates candidates who truly understand adversarial search from those who only know single-agent DP. The core technique here, minimax with memoization, appears in problems involving two-player games, optimal strategies, and any scenario where one player maximizes while the other minimizes. Mastering this pattern means you can handle "Predict the Winner," "Stone Game," and similar adversarial problems.

The key insight

The game has a finite state space. At any moment, the full state is captured by four values: the mouse's position, the cat's position, whose turn it is, and how many turns have elapsed. Both players play optimally, so this is a classic minimax problem. The mouse (maximizer) looks for any move that leads to a winning state. The cat (minimizer) looks for any move that prevents the mouse from winning.

The turn count matters because the game can cycle. If the mouse and cat keep chasing each other in circles, the game never ends. The 1000-turn limit in the problem statement handles this, but in practice you can use a tighter bound: if the turn count exceeds rows * cols * 2, every reachable state has been visited at least once per player, so you are in a cycle and the cat wins by default.

The algorithm:

1. Parse the grid to find the starting positions of the mouse, cat, and food.
2. Define a recursive function canMouseWin(mouse_pos, cat_pos, turn) that returns True if the mouse can guarantee a win from this state.
3. On the mouse's turn, try every reachable cell (including staying put). If any move leads to a state where canMouseWin returns True, the mouse wins.
4. On the cat's turn, try every reachable cell. If any move leads to a state where canMouseWin returns False, the cat wins.
5. Memoize every state to avoid recomputation.

The solution

from functools import lru_cache

def can_mouse_win(grid, catJump, mouseJump):
    rows, cols = len(grid), len(grid[0])
    cat_start = mouse_start = food = (0, 0)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "C":
                cat_start = (r, c)
            elif grid[r][c] == "M":
                mouse_start = (r, c)
            elif grid[r][c] == "F":
                food = (r, c)

    max_turns = rows * cols * 2
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    @lru_cache(maxsize=None)
    def dp(mouse, cat, turn):
        if turn >= max_turns:
            return False
        if mouse == cat:
            return False
        if cat == food:
            return False
        if mouse == food:
            return True

        mouse_turn = turn % 2 == 0

        if mouse_turn:
            if dp(mouse, cat, turn + 1):
                return True
            for dr, dc in directions:
                for jump in range(1, mouseJump + 1):
                    nr, nc = mouse[0] + dr * jump, mouse[1] + dc * jump
                    if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                        break
                    if grid[nr][nc] == "#":
                        break
                    if dp((nr, nc), cat, turn + 1):
                        return True
            return False
        else:
            if not dp(mouse, cat, turn + 1):
                return False
            for dr, dc in directions:
                for jump in range(1, catJump + 1):
                    nr, nc = cat[0] + dr * jump, cat[1] + dc * jump
                    if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                        break
                    if grid[nr][nc] == "#":
                        break
                    if not dp(mouse, (nr, nc), turn + 1):
                        return False
            return True

    return dp(mouse_start, cat_start, 0)

Let's walk through what each piece does.

The first loop scans the grid to locate the cat, mouse, and food positions. These are the inputs to our recursive game state.

The dp function is the heart of the solution. It takes the current mouse position, cat position, and turn number. The base cases check: has the turn limit been reached (cat wins), has the cat caught the mouse (cat wins), has the cat reached food (cat wins), or has the mouse reached food (mouse wins)?

On the mouse's turn (turn % 2 == 0), the mouse tries staying in place first, then tries jumping 1 to mouseJump steps in each of the four directions. If any move produces a state where dp returns True, the mouse takes that move and wins. The inner loop breaks early when hitting a wall or going out of bounds, because a wall blocks all further jumps in that direction.

On the cat's turn, the logic is inverted. The cat tries staying in place, then jumping in each direction. If any move produces a state where dp returns False, the cat takes that move and the mouse loses. The cat only needs one winning response to defeat the mouse.

The lru_cache decorator memoizes results by (mouse, cat, turn). Without memoization, the branching factor (up to 4 directions times the jump limit, plus staying put) would make the recursion explode exponentially.

Visual walkthrough

Let's trace through the minimax logic on our example grid. At each step, the current player explores all reachable positions and picks the optimal move.

The recursion explores the entire game tree depth-first, but memoization ensures each unique state is only computed once. The mouse systematically checks whether any sequence of moves guarantees reaching the food, while the cat checks whether it can always prevent that.

Complexity analysis

Time is O(m^2 * n^2 * T * (J_m + J_c)) where m and n are the grid dimensions, T is the turn limit (m * n * 2), and J_m and J_c are the mouse and cat jump limits. There are O(m * n) possible mouse positions, O(m * n) possible cat positions, and O(T) possible turn values, giving O(m^2 * n^2 * T) unique states. For each state, the current player explores up to 4 * (jump_limit) + 1 moves.

Space is O(m^2 * n^2 * T) for the memoization cache, storing the result of every unique game state.

Since the grid is at most 8x8 and jump limits are at most 8, the total number of states is manageable: 64 * 64 * 128 = roughly 500,000 states. Each state does at most about 33 transitions (4 directions * 8 jumps + stay), so the total work is around 16 million operations, which runs within the time limit.

The building blocks

1. Game state representation

@lru_cache(maxsize=None)
def dp(mouse, cat, turn):
    if turn >= max_turns:
        return False
    if mouse == cat:
        return False
    if cat == food:
        return False
    if mouse == food:
        return True

The state tuple (mouse_pos, cat_pos, turn) captures everything about the current game. The base cases encode the win/loss conditions. This pattern of defining game states as tuples and checking terminal conditions first applies to any two-player game: Stone Game, Nim, or any adversarial search problem.

2. Minimax with memoization

if mouse_turn:
    for move in mouse_moves:
        if dp(move, cat, turn + 1):
            return True
    return False
else:
    for move in cat_moves:
        if not dp(mouse, move, turn + 1):
            return False
    return True

The maximizer (mouse) returns True if any child state is True. The minimizer (cat) returns True only if all child states are True. This is the classic minimax pattern. The lru_cache turns the exponential game tree into a polynomial-time computation by ensuring each state is evaluated at most once.

3. Grid jump enumeration with wall blocking

for dr, dc in directions:
    for jump in range(1, jumpLimit + 1):
        nr, nc = pos[0] + dr * jump, pos[1] + dc * jump
        if out_of_bounds(nr, nc) or grid[nr][nc] == "#":
            break
        process(nr, nc)

The inner loop tries every jump distance from 1 to the limit. When it hits a wall or goes out of bounds, it breaks immediately because the player cannot jump through obstacles. This "cast a ray until blocked" pattern also appears in problems like "Queen's Attack" and bishop/rook movement in chess-related problems.

Edge cases

• Mouse starts adjacent to food: mouse wins in one move regardless of cat's position (unless cat is also on the food, which is not a valid input).
• Cat starts on the food: cat wins immediately. Mouse can never reach food because the cat is already there.
• Mouse is completely walled off from food: the mouse has no path to food. The cat wins by default after the turn limit.
• Cat is completely walled off from mouse: the cat cannot interfere. The mouse wins if it can reach food within the turn limit.
• 1x1 grid with just mouse and food at the same cell: not a valid input per the constraints, but if it were, the mouse wins immediately.
• Large jump values on a small grid: the player can reach any non-walled cell in one jump. The game resolves quickly, but the memoization handles it efficiently regardless.
• Both players far from food with many walls: the turn limit becomes the deciding factor. If neither player can force a result within rows * cols * 2 turns, the cat wins.

From understanding to recall

You have seen how minimax with memoization transforms an adversarial game into a solvable state-space search. The state is (mouse_pos, cat_pos, turn), the mouse tries to find any winning path, the cat tries to block all of them, and memoization ensures polynomial time. But knowing the approach is not the same as producing it under pressure.

In an interview, you need to quickly identify the game state, write the base cases, implement the minimax branching (mouse returns True on any win, cat returns False on any loss), add the turn limit for cycle detection, and handle the jump-with-wall-blocking loop. Each of these is a small piece, but getting all of them right simultaneously requires practice.

Spaced repetition builds that fluency. You revisit the minimax template, the state definition, and the jump enumeration at increasing intervals. After a few rounds, when you see a two-player game on a grid, the pattern clicks into place automatically. You define the state, write the base cases, structure the minimax, add memoization, and handle the grid movement without second-guessing yourself.

Related posts

• Dungeon Game - Grid DP with survivability constraints, teaching backward reasoning on 2D boards
• Unique Paths - Foundational grid state exploration with dynamic programming
• Word Search - Grid DFS with backtracking, a building block for any grid search problem

CodeBricks breaks Cat and Mouse II into its game state definition, minimax recursion, and grid jump enumeration building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When an adversarial search problem shows up in your interview, you do not fumble with the minimax structure. You just write it.