Slither Link

In an exercise, Knuth describes how to quickly compute the ZDD representing the family of simple cycles in a lattice graph. Here, the universe is the set of all edges, so each member of the family is a set of edges that form a simple cycle.

Imagine you know nothing about ZDDs and are asked to count the number of simple cycles in a grid graph. Perhaps you might turn to dynamic programming, But what are reasonable subproblems? A natural approach is to examine simple cycles given that certain edges must be included, and certain others must be absent.

Constructing the ZDD is essentially the same procedure. We build ZDDs from the bottom up; smaller ZDDs represent smaller subgraphs.

We can immediately construct the ZDD for the sets of edges containing exactly \(n\) out of 4 particular edges. Thus, constructing such a ZDD for each clue and intersecting them with the ZDD of simple cycles yields the solutions.

However, we can solve puzzles faster if we first construct the ZDD \(Z\) representing sets that satisfy all the clues, and then follow the algorithm for constructing the simple cycle ZDD, except we respect constraints represented in \(Z\). Indeed, computing the simple cycle ZDD for larger puzzles is too expensive, while this approach can sometimes solve them cheaply.