Finding an Algorithm for the HAPPY-CAT problem
I'm trying to develop an the algorithm for the problem:
The cat-and-mouse game is played by two players, “<PERSON>” and “<PERSON>,” on an arbitrary undirected graph. At a given point, each player occupies a node of the graph. The players take turns moving to a node adjacent to the one that they currently occupy. A special node of the graph is called “Hole.” <PERSON> wins if the two players ever occupy the same node. Mouse wins if it reaches the Hole before the preceding happens. The game is a draw if a situation repeats (i.e., the two players simultaneously occupy positions that they simultaneously occupied previously, and it is the same player’s turn to move).
In other words, we have to decide: HAPPY-CAT = { | G, c, m, h are respectively a graph, and positions of the Cat, Mouse, and Hole, such that <PERSON> has a winning strategy if <PERSON> moves first}.
I came across this algorithm:
1. Mark all nodes (a, a, x) where a is a node in G, and x is turn {cat, mouse} for whoever goes next.
2. 180
If for a node u = (a, b, cat), there is a node v = (c, b, mouse) which is marked and (u, v) is an edge then mark u.
3. If for a node u = (a, b, mouse), all nodes v = (a, c, cat) are marked and (u, v) is an edge then mark u.
4. Repeat steps 2 and 3 until no new nodes are marked.
5. Accept if start node s = (c, m, cat) is marked.
But I'm having difficulty envisioning the first step. For example, in the picture below (where cat starts at 1, mouse starts at 5, and the hole is at 10), cat wins at vertex 4 in two ways:
1. c -> 12, m -> 4, c -> 6, m -> 2, c -> 4, m -> 4
2. c -> 12, m -> 4, c -> 3, m -> 2, c -> 12, m -> 4, c -> 4
So then at step 1 of the algorithm, would node 4 in our new marked set contain (4, 4, cat) or (4, 4, mouse)? 835