Cat and Mouse

hard graph game theory bfs

Problem

A mouse and a cat play on an undirected graph. The mouse starts at node 1, the cat starts at node 2, and the hole is node 0. They alternate moves (mouse first), each stepping along an edge to a neighbor; the cat may not enter the hole. The mouse wins if it reaches the hole, the cat wins if it ever occupies the mouse's node, and the game is a draw if a position repeats. Assuming optimal play, return 1 if the mouse wins, 2 if the cat wins, or 0 for a draw.

Inputgraph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]

Output0

With optimal play neither side can force a win, so the game ends in a draw.

graph (adjacency list, JSON)

from collections import deque

DRAW, MOUSE, CAT = 0, 1, 2

def catMouseGame(graph):
    n = len(graph)
    # color[mouse][cat][turn]; turn 0 = mouse to move, 1 = cat to move
    color = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
    degree = [[[0] * 2 for _ in range(n)] for _ in range(n)]
    for m in range(n):
        for c in range(n):
            degree[m][c][0] = len(graph[m])
            degree[m][c][1] = len(graph[c]) - (1 if 0 in graph[c] else 0)

    q = deque()
    for c in range(1, n):           # cat cannot sit on the hole
        for t in range(2):
            color[0][c][t] = MOUSE  # mouse reached the hole
            q.append((0, c, t, MOUSE))
            color[c][c][t] = CAT    # cat caught the mouse
            q.append((c, c, t, CAT))

    while q:
        m, c, t, result = q.popleft()
        for pm, pc, pt in parents(graph, m, c, t):
            if color[pm][pc][pt] != DRAW:
                continue
            if pt == result - 1:                 # mover wins immediately
                color[pm][pc][pt] = result
                q.append((pm, pc, pt, result))
            else:
                degree[pm][pc][pt] -= 1           # one option ruled out
                if degree[pm][pc][pt] == 0:       # all options lose
                    color[pm][pc][pt] = result
                    q.append((pm, pc, pt, result))
    return color[1][2][0]

def parents(graph, m, c, t):
    pt = 1 - t
    if pt == 0:                       # mouse moved to reach (m,c)
        for pm in graph[m]:
            yield pm, c, pt
    else:                             # cat moved to reach (m,c)
        for pc in graph[c]:
            if pc != 0:
                yield m, pc, pt

function catMouseGame(graph) {
  const n = graph.length;
  const DRAW = 0, MOUSE = 1, CAT = 2;
  // color[m][c][t], t: 0 = mouse to move, 1 = cat to move
  const color = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => [DRAW, DRAW]));
  const degree = Array.from({ length: n }, (_, m) =>
    Array.from({ length: n }, (_, c) =>
      [graph[m].length, graph[c].length - (graph[c].includes(0) ? 1 : 0)]));

  const q = [];
  for (let c = 1; c < n; c++) {
    for (let t = 0; t < 2; t++) {
      color[0][c][t] = MOUSE; q.push([0, c, t, MOUSE]);
      color[c][c][t] = CAT;   q.push([c, c, t, CAT]);
    }
  }

  const parents = (m, c, t) => {
    const pt = 1 - t, res = [];
    if (pt === 0) for (const pm of graph[m]) res.push([pm, c, pt]);
    else for (const pc of graph[c]) if (pc !== 0) res.push([m, pc, pt]);
    return res;
  };

  let head = 0;
  while (head < q.length) {
    const [m, c, t, result] = q[head++];
    for (const [pm, pc, pt] of parents(m, c, t)) {
      if (color[pm][pc][pt] !== DRAW) continue;
      if (pt === result - 1) {
        color[pm][pc][pt] = result; q.push([pm, pc, pt, result]);
      } else if (--degree[pm][pc][pt] === 0) {
        color[pm][pc][pt] = result; q.push([pm, pc, pt, result]);
      }
    }
  }
  return color[1][2][0];
}

import java.util.*;

class Solution {
    static final int DRAW = 0, MOUSE = 1, CAT = 2;
    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        int[][][] color = new int[n][n][2];
        int[][][] degree = new int[n][n][2];
        for (int m = 0; m < n; m++)
            for (int c = 0; c < n; c++) {
                degree[m][c][0] = graph[m].length;
                degree[m][c][1] = graph[c].length;
                for (int x : graph[c]) if (x == 0) degree[m][c][1]--;
            }

        Deque<int[]> q = new ArrayDeque<>();
        for (int c = 1; c < n; c++)
            for (int t = 0; t < 2; t++) {
                color[0][c][t] = MOUSE; q.add(new int[]{0, c, t, MOUSE});
                color[c][c][t] = CAT;   q.add(new int[]{c, c, t, CAT});
            }

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int m = cur[0], c = cur[1], t = cur[2], result = cur[3];
            int pt = 1 - t;
            int[] preds = pt == 0 ? graph[m] : graph[c];
            for (int p : preds) {
                int pm = pt == 0 ? p : m, pc = pt == 0 ? c : p;
                if (pt == 1 && p == 0) continue;
                if (color[pm][pc][pt] != DRAW) continue;
                if (pt == result - 1) {
                    color[pm][pc][pt] = result; q.add(new int[]{pm, pc, pt, result});
                } else if (--degree[pm][pc][pt] == 0) {
                    color[pm][pc][pt] = result; q.add(new int[]{pm, pc, pt, result});
                }
            }
        }
        return color[1][2][0];
    }
}

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int catMouseGame(vector<vector<int>>& graph) {
        int n = graph.size();
        const int DRAW = 0, MOUSE = 1, CAT = 2;
        vector<vector<array<int,2>>> color(n, vector<array<int,2>>(n, {0, 0}));
        vector<vector<array<int,2>>> degree(n, vector<array<int,2>>(n));
        for (int m = 0; m < n; m++)
            for (int c = 0; c < n; c++) {
                degree[m][c][0] = graph[m].size();
                degree[m][c][1] = graph[c].size();
                for (int x : graph[c]) if (x == 0) degree[m][c][1]--;
            }

        queue<array<int,4>> q;
        for (int c = 1; c < n; c++)
            for (int t = 0; t < 2; t++) {
                color[0][c][t] = MOUSE; q.push({0, c, t, MOUSE});
                color[c][c][t] = CAT;   q.push({c, c, t, CAT});
            }

        while (!q.empty()) {
            auto [m, c, t, result] = q.front(); q.pop();
            int pt = 1 - t;
            const vector<int>& preds = pt == 0 ? graph[m] : graph[c];
            for (int p : preds) {
                int pm = pt == 0 ? p : m, pc = pt == 0 ? c : p;
                if (pt == 1 && p == 0) continue;
                if (color[pm][pc][pt] != DRAW) continue;
                if (pt == result - 1) {
                    color[pm][pc][pt] = result; q.push({pm, pc, pt, result});
                } else if (--degree[pm][pc][pt] == 0) {
                    color[pm][pc][pt] = result; q.push({pm, pc, pt, result});
                }
            }
        }
        return color[1][2][0];
    }
};

Explanation

This is a two-player game, so we can't just search forward — we need to know who wins with optimal play from the start. The idea is to label every game state as a MOUSE win, CAT win, or DRAW, working backward from the states whose outcome is already obvious.

A state is (mouse position, cat position, whose turn). We seed a queue with the known terminal states: mouse at the hole 0 is a MOUSE win, and cat sitting on the mouse is a CAT win. From there we walk to parent states (the positions that could move into a decided state).

A parent is decided in two ways. If it is the mover's turn and they can step into a win for their side, that parent is immediately a win for them. Otherwise we decrement that parent's degree (its count of undecided moves); when degree hits 0, every option leads to the same loss, so the parent is forced into that result. This is BFS-style minimax with retrograde analysis.

The answer is the color of the start state color[1][2][0] (mouse at 1, cat at 2, mouse to move). For the sample graph, neither side can force a win, so that state stays DRAW and the answer is 0.

Time: O(n³) Space: O(n²)