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.

 $$n$$ cycles in $$n \times n$$ lattice graph average cycle length standard deviation 2 2 2.000000 2.000000 3 14 5.714286 2.249717 4 214 10.710280 2.771717 5 9350 17.462246 3.152186 6 1222364 25.768157 3.724317 7 487150372 35.805114 4.284285 8 603841648932 47.479949 4.756736 9 2318527339461266 60.709770 5.221515 10 27359264067916806102 75.502314 5.707011 11 988808811046283595068100 91.876952 6.201849 12 109331355810135629946698361372 109.838303 6.697420

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.

Ben Lynn blynn@cs.stanford.edu 💡