We are searching for paths through a cave system, which can be
described as a simple graph. Our paths must connect the start and
end nodes, and they can contain some cycles; namely, “large caves”
(nodes labeled with upper-case names). Specifically, we want to know
the number of valid paths through the given cave.
This kind of puzzle is perfect for relational programming, but the
specific information we’re required to find is an immediate obstacle
to this approach. We can quickly sketch out a predicate
path(A, B, Path) (to use a generalized logic programming notation)
which succeeds if Path is a valid path from A to B, but we
want to know how many times this relation succeeds for a given
graph (cave system). This is “extra-logical”; presumably there’s some
weird Prolog technique for dealing with this, but we’ll try a different
approach.
(The embedded logic programming language miniKanren is nicely suited to this task, since it’s rather easy to pull a list of successes out of miniKanren into the host functional language. Here is a solver using this idea. Unfortunately, it is extremely slow.)