## Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs
The opposite approached has been proposed by [PERSON] _et al_. [10] and [PERSON] [11]. Their algorithm takes a cycle, which is a predetermined solution, as input and starts from a grid whose cells are all fulfilled by the numbers compatible with the solution. The algorithm then repeatedly removes the number in a random cell one by one until the obtained instance admits an unexpected solution. The algorithm outputs the instance obtained just before removing the last number. Our contribution is located in this line of research. We propose solution and instance enumeration algorithms for Numberlink and Slitherlink. Unlike existing algorithms, ours output all the qualified solutions/instances at once in the form of a _zero-suppressed binary decision diagram (ZDD)_. A ZDD is a compressed data structure for representing and manipulating families of sets [12]. Recently, [PERSON] [13, exercise 225] has proposed an algorithm, called Simpath, that constructs a ZDD representing all \(s\)-\(t\) paths on a given graph and two vertices \(s\) and \(t\), where a path is identified with the set of edges constituting the path. If an instance of Numberlink has only one pair of numbers in a grid, Simpath gives all solutions to it. [PERSON] has also proposed a modification of Simpath that enumerates all single cycles on an input graph in the form of a ZDD. Recall that to be a cycle is a necessary condition to be a solution for Slitherlink. Our solvers for the link puzzles construct a ZDD representing solutions in the manner of Simpath with taking the constraints from the problem instance into account. By the nature of enumeration, one can immediately decide whether an instance admits exactly one solution. ZDDs can represent families of sets in a small space, yet an even more important and widely appreciated virtue of ZDDs is that one can quite efficiently perform fundamental mathematical operations on families of sets over ZDDs, like union, intersection, _etc_. Our algorithms for generating instances of the link puzzles apply the virtue of ZDDs. Our method based on ZDDs offers users flexible means to design puzzle instances. For example, puzzle designers can extract some specific kind of instances from the whole which they think \"interesting\" by those set operations over ZDDs. This paper is organized as follows. Formal definitions of ZDDs, Numberlink and Slitherlink are given in Section 2. Section 3 introduces a variant of Simpath that enumerates all path matchings over a graph, on which other algorithms of ours are based. Our Numberlink solver is presented in Section 4 and Numberlink instance enumeration algorithm is proposed in Section 5. On the other hand, our Slitherlink solver and instance enumeration algorithm are presented in Sections 6 and 7, respectively. We also show experimental results on these algorithms in Section 8, where we compare the performance of known solving algorithms and ours. Moreover, we demonstrate how our method may help puzzle designers through presenting visually attractive instances of Slitherlink obtained by our algorithm. We then conclude the paper in Section 9.