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.