Long-haired programmer; loves cats and dogs but doesn't have any.
This is a silly game, but anyway.
We assume you have a graph (nodes and edges) explicitly on a piece of paper (printed out or something), and it’s small enough that you can comprehend it visually, and you don’t mind marking it up.
You will need blank index cards and a writing implement.
Decide on locations for four spots for index cards: the blank ones, the “TODO” stack, the “FOCUS” stack, and the “DONE” stack.
Create an index card for the starting node, put it in the FOCUS stack, and cross off the starting node in the graph.
Why does this game terminate? Let’s try to use Lex ordering to prove it.
Lex ordering is dictionary ordering, generalized to tuples of numbers. For example, in lex ordering (a, b, c) is bigger than another tuple (d, e, f) if a is bigger than d in the usual way, or if a is equal to d and b is bigger than e. If a equals d and b equals e then we fall back to comparing c to f.
Let’s use this 4-tuple: (unmarked non-neighbors, unmarked neighbors, number of items in TODO, number of items in FOCUS)
When we focus using rule 2, then we change the set of neighbors. In principle, switching focus could increase the number of unmarked non-neighbors, if we had some unmarked neighbors before the switch. However, because we always mark all of the neighbors before switching focus, Rule 2 never increases the number of unmarked non-neighbors, and sometimes unmarked non-neighbors become unmarked neighbors, decreasing the number of unmarked non-neighbors.
Also, when we focus using rule 2, we decrease the number of items in TODO. We increase the number of items in FOCUS, but we don’t mind that.
When we mark a neighbor with rule 3, we decrease the number of unmarked neighbors (and increase the number of items in TODO, but we don’t mind that), but we never increase the number of unmarked non-neighbors.
When we unfocus using rule 4, we decrease the number of items in FOCUS, and we don’t increase any other quality.
So in every case, we go downward in lex ordering.
Note: I am not certain that this argument is ironclad.
Opinions expressed are solely my own and do not express the views or opinions of my employer.