Solution
Approach 1: Minimax / Percolate from Resolved States
Intuition
The state of the game can be represented as (m, c, t)
where m
is the location of the mouse, c
is the location of the cat, and t
is 1
if it is the mouse's move, else 2
. Let's call these states nodes. These states form a directed graph: the player whose turn it is has various moves which can be considered as outgoing edges from this node to other nodes.
Some of these nodes are already resolved: if the mouse is at the hole (m = 0)
, then the mouse wins; if the cat is where the mouse is (c = m)
, then the cat wins. Let's say that nodes will either be colored , , or depending on which player is assured victory.
As in a standard minimax algorithm, the Mouse player will prefer nodes first, nodes second, and nodes last, and the Cat player prefers these nodes in the opposite order.
Algorithm
We will color each node
marked according to the following rule. (We'll suppose the node
has node.turn = Mouse
: the other case is similar.)

("Immediate coloring"): If there is a child that is colored , then this node will also be colored .

("Eventual coloring"): If all children are colored , then this node will also be colored .
We will repeatedly do this kind of coloring until no node
satisfies the above conditions. To perform this coloring efficiently, we will use a queue and perform a bottomup percolation:

Enqueue any node initially colored (because the Mouse is at the Hole, or the Cat is at the Mouse.)

For every
node
in the queue, for eachparent
of thatnode
: 
Do an immediate coloring of
parent
if you can. 
If you can't, then decrement the sidecount of the number of children marked . If it becomes zero, then do an "eventual coloring" of this parent.

All
parents
that were colored in this manner get enqueued to the queue.
Proof of Correctness
Our proof is similar to a proof that minimax works.
Say we cannot color any nodes any more, and say from any node colored or we need at most moves to win. If say, some node marked is actually a win for Mouse, it must have been with moves. Then, a path along optimal play (that tries to prolong the loss as long as possible) must arrive at a node colored (as eventually the Mouse reaches the Hole.) Thus, there must have been some transition along this path.
If this transition occurred at a node
with node.turn = Mouse
, then it breaks our immediate coloring rule. If it occured with node.turn = Cat
, and all children of node
have color , then it breaks our eventual coloring rule. If some child has color , then it breaks our immediate coloring rule. Thus, in this case node
will have some child with , which breaks our optimal play assumption, as moving to this child ends the game in moves, whereas moving to the colored neighbor ends the game in moves.
Complexity Analysis

Time Complexity: , where is the number of nodes in the graph. There are states, and each state has an outdegree of , as there are at most different moves.

Space Complexity: .
Analysis written by: @awice.