Cat and Mouse: Game Theory on Graphs

A mouse and a cat play a game on an undirected graph. The mouse starts at node 1, the cat starts at node 2, and there is a hole at node 0. They take turns moving along edges, with the mouse going first. The mouse wins if it reaches the hole. The cat wins if it lands on the same node as the mouse. The cat is not allowed to enter the hole. If the game drags on for 2 * n moves without either win condition being met, the game is a draw.

Given the graph, determine the outcome if both players play optimally. This is LeetCode 913: Cat and Mouse.

The problem

You are given an adjacency list graph where graph[i] is the list of nodes that node i connects to. Node 0 is the hole. The mouse starts at 1, the cat starts at 2. On each turn, the current player moves to an adjacent node (or stays in place). The cat cannot move to node 0. Return 1 if the mouse wins, 2 if the cat wins, or 0 for a draw.

This is not a standard shortest-path or reachability problem. Both players are rational and pick the best move for themselves. The mouse tries to reach the hole, and the cat tries to catch the mouse. You need game theory to figure out who wins.

The brute force approach

A naive approach would be to simulate the game by exploring all possible move sequences. You could use DFS or BFS on the state space (mouse_pos, cat_pos, turn) starting from (1, 2, mouse_turn). At each state, the current player tries all possible moves. If the mouse is moving, it picks a move that leads to a mouse-win state if one exists. If the cat is moving, it picks a move that leads to a cat-win state if one exists.

The problem is cycles. Two smart players can loop forever, and naive DFS will recurse infinitely without a way to detect draws. You could add a depth limit (stop after 2 * n moves), but that turns this into a tree of depth 2n with branching factor up to n, making it far too slow.

The key insight

Instead of simulating forward from the starting position, work backwards from states where you already know the outcome. This technique is called backward induction, and it is the standard approach for two-player combinatorial games on graphs.

The terminal states are your base cases:

• If mouse_pos == 0, the mouse has reached the hole. Mouse wins (result = 1).
• If mouse_pos == cat_pos, the cat has caught the mouse. Cat wins (result = 2).

From these known outcomes, use a BFS-like process to determine the result of every other state. For each state (m, c, turn):

• If it is the mouse's turn and any neighbor state is a mouse-win, then this state is also a mouse-win (the mouse will pick that move).
• If it is the mouse's turn and all neighbor states are cat-wins, then this state is a cat-win (the mouse has no escape).
• If it is the cat's turn and any neighbor state is a cat-win, then this state is a cat-win.
• If it is the cat's turn and all neighbor states are mouse-wins, then this state is a mouse-win.

States that are never resolved remain draws.

Step-by-step walkthrough

The code

from collections import deque

def cat_mouse_game(graph: list[list[int]]) -> int:
    n = len(graph)
    DRAW, MOUSE, CAT = 0, 1, 2

    result = [[[DRAW] * 3 for _ in range(n)] for _ in range(n)]
    degree = [[[0] * 3 for _ in range(n)] for _ in range(n)]

    for m in range(n):
        for c in range(n):
            degree[m][c][1] = len(graph[m])
            degree[m][c][2] = len(graph[c]) - graph[c].count(0)

    queue = deque()

    for c in range(1, n):
        for t in (1, 2):
            result[0][c][t] = MOUSE
            queue.append((0, c, t, MOUSE))

    for x in range(1, n):
        for t in (1, 2):
            result[x][x][t] = CAT
            queue.append((x, x, t, CAT))

    while queue:
        m, c, turn, outcome = queue.popleft()

        if turn == 1:
            prev_turn = 2
            predecessors = [(m, pc, prev_turn) for pc in graph[c] if pc != 0]
        else:
            prev_turn = 1
            predecessors = [(pm, c, prev_turn) for pm in graph[m]]

        for pm, pc, pt in predecessors:
            if result[pm][pc][pt] != DRAW:
                continue
            if (pt == 1 and outcome == MOUSE) or (pt == 2 and outcome == CAT):
                result[pm][pc][pt] = outcome
                queue.append((pm, pc, pt, outcome))
            else:
                degree[pm][pc][pt] -= 1
                if degree[pm][pc][pt] == 0:
                    losing = CAT if pt == 1 else MOUSE
                    result[pm][pc][pt] = losing
                    queue.append((pm, pc, pt, losing))

    return result[1][2][1]

Here is how this works.

The state space has three dimensions: the mouse position, the cat position, and whose turn it is. result[m][c][t] stores the outcome for state (m, c, t). The degree[m][c][t] array counts how many moves the current player has from that state. For the cat, we subtract moves to node 0 since the cat cannot enter the hole.

The BFS starts from all terminal states. For each resolved state, we look at its predecessor states (the states that could have transitioned into it). If a predecessor's current player can win by moving to this state, we mark it immediately. Otherwise, we decrement its degree. When a state's degree hits zero, every move leads to a loss for the current player, so the other player wins.

States that are never reached by the BFS remain DRAW. The answer is result[1][2][1], the outcome from the starting position with the mouse's turn.

Complexity analysis

Time: There are O(n^2) possible states (n positions for mouse times n positions for cat times 2 turns). For each state, we look at its predecessors, which is bounded by the degree of the graph. In the worst case, the graph is complete, so processing all predecessors across all states takes O(n^3).

Space: The result and degree arrays are both n * n * 2, which is O(n^2). The BFS queue holds at most O(n^2) states.

The building blocks

This problem combines two fundamental techniques that appear across many graph and DP problems.

1. Game state modeling

The core idea is representing a two-player game as a graph of states. Each state encodes everything you need to know: both player positions and whose turn it is. This same modeling applies to any combinatorial game. Once you have the state graph, the game becomes a graph traversal problem.

result = [[[DRAW] * 3 for _ in range(n)] for _ in range(n)]

The trick is choosing the right state representation. Too much information and the state space explodes. Too little and you lose track of the game. Here, (mouse_pos, cat_pos, turn) is exactly what you need.

2. Backward induction with degree counting

Instead of exploring forward from the start, you begin from terminal states and propagate backward. The degree array tracks how many unresolved moves each state has. When a state's degree reaches zero, all of its moves lead to the opponent winning, so the current player loses.

degree[pm][pc][pt] -= 1
if degree[pm][pc][pt] == 0:
    losing = CAT if pt == 1 else MOUSE
    result[pm][pc][pt] = losing

This pattern is the game-theoretic analog of topological sort. It naturally handles draws: states that can loop forever never get their degree reduced to zero and remain unresolved.

Edge cases

• Mouse starts at the hole: if graph allows mouse to start at 0, the mouse wins immediately. The standard problem guarantees mouse starts at 1, but the algorithm handles it correctly.
• Cat starts adjacent to mouse: the cat might win on its first move, but the mouse moves first, so the mouse might escape.
• Fully connected graph: every node connects to every other node. The state space is large, but the algorithm still runs in O(n^3).
• Linear graph (path): nodes form a line. If the hole is at one end and the mouse is between the cat and the hole, the mouse escapes easily.
• Small graph (n = 3): the minimum interesting case. Only a handful of states to resolve, useful for tracing through the algorithm by hand.

From understanding to recall

Game theory on graphs feels abstract until you internalize the pattern. Backward induction is the key: start from states where you know the answer, and propagate results to their predecessors. The degree-counting mechanism is what makes this work for adversarial games rather than simple reachability.

The pieces you need to reconstruct this solution are: state representation as a 3D array, terminal state identification, predecessor enumeration, and the degree-based propagation loop. Each piece is small on its own. The challenge is wiring them together correctly, especially the predecessor logic where you reverse the direction (from current state back to the state that preceded it).

Spaced repetition helps you lock in these details. After a few practice rounds, you stop second-guessing whether predecessors for a mouse-turn state involve cat moves or mouse moves. You just know. That is the difference between understanding the solution and being able to write it under interview pressure.

Related posts

• Course Schedule - Topological sort and cycle detection in directed graphs, the simpler cousin of backward induction on game state graphs
• Clone Graph - Deep graph traversal with state tracking, teaching the BFS and DFS patterns that underpin game state exploration
• Longest Increasing Path in a Matrix - Memoized DFS on a state graph with topological ordering, showing how DAG structure enables backward propagation