Possibly all the ways to get loop-finding in graphs wrong

submited by

Style Pass

2024-09-09 21:30:06

In my puzzle collection, there are many games in which you have to connect points together by edges, making a graph, and the puzzle rules say you must avoid making any loop in the graph. Examples are Net, Slant, and some configurations of Bridges (although not the default one). Loopy and Pearl also care about whether there’s a loop in a graph, although those two are more subtle: your aim is to make a loop, and only wrong loops must be rejected.

Therefore, those puzzle programs need to be able to check whether a graph has a loop in it, in order to decide whether the puzzle solution is correct. If there is a loop, they also have to identify the edges that make up the loop, in order to point out to the player why their solution hasn’t been accepted.

Over the years I’ve been developing these puzzles, I’ve gone through an amazing number of algorithms for doing that job. Each one was unsatisfactory for some reason, and I threw it away, and moved on to the next.