## Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs  
**[PERSON] 1, [PERSON] 2,3,*, [PERSON] 2,3, [PERSON] 2, [PERSON] 2,3 and [PERSON] 2,3**  
1 Graduate School of Informatics, Kyoto University, Kyoto, 606-8501, Japan;  
E-Mail: [EMAIL_ADDRESS]
2 ERATO MINATO Project, Japan Science and Technology Agency, Kitaku North 14, West 9, Sapporo, 060-0814, Hokkaido, Japan; E-Mails: [EMAIL_ADDRESS] (J.K.);  
[EMAIL_ADDRESS] (K.T. ); [EMAIL_ADDRESS] (H.I. );  
[EMAIL_ADDRESS] (S.M.) 3 Graduate School of Information Science and Technology, Hokkaido University, Kitaku North 14, West 9, Sapporo, 060-0814, Hokkaido, Japan  
\({}^{\star}\) Author to whom correspondence should be addressed; E-Mail: [EMAIL_ADDRESS];  
Tel. : +81-11-728-8280. _Received: 16 November 2011; in revised form: 29 February 2012 / Accepted: 19 March 2012 / Published: 5 April 2012_  
**Abstract:** Link puzzles involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper proposes algorithms that enumerate solutions and instances of two link puzzles, Slitherlink and Numberlink, by zero-suppressed binary decision diagrams (ZDDs). A ZDD is a compact data structure for a family of sets provided with a rich family of set operations, by which, for example, one can easily extract a subfamily satisfying a desired property. Thanks to the nature of ZDDs, our algorithms offer a tool to assist users to design instances of those link puzzles. **Keywords:** link puzzles; Slitherlink; Numberlink; solvers; instance generationsIntroduction  
_Link puzzles_, for example Slitherlink, Numberlink, Masyu, _etc._, are logic puzzles that involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper focuses on two simple link puzzles, _Numberlink_ and _Slitherlink_, amongst others. Numberlink is played on a grid where the rules are below [1]. 1. Connect pairs of the same numbers with a continuous line. 2. Lines go through the center of the cells, horizontally, vertically, or changing direction, and never twice through the same cell. 3. Lines cannot cross, branch off, or go through the cells with numbers. Figure 1 describes an instance of Numberlink. Numberlink is known to be NP-complete [2; 3; 4]. Numberlink is also studied as a model of VLSI layout design [5]. Slitherlink is played on a grid of lattice dots where we draw a loop satisfying below [1]. 1. Connect adjacent dots with vertical or horizontal lines. 2. A single loop is formed with no crossing or branches. 3. The numbers indicate how many lines surround it, while empty cells may be surrounded by any number of lines. We describe an instance of Slitherlink in Figure 2. Slitherlink is known to be NP-complete [6; 7]. Figure 1: An instance of Numberlink and its solution. Figure 2: An instance of Slitherlink and its solution. Link puzzles have been popularized by a Japanese publisher Nikoli and many puzzle designers are trying to produce good and interesting instances. The least common criterion on instances to be good is to admit exactly one solution, but what should be good and interesting is quite a subjective issue to respective designers. The complexity barrier suggests difficulties in the instance design. On the other hand, as is usually the case for logic puzzles, computer scientists and programmers have been proposed several automatic solvers targeting those link puzzles. _Sugar_[8] is a SAT based constraint solver which is provided with formulation of Numberlink and Slitherlink. While it is often the case that a solution for an instance of Numberlink is found just by inspiration, many local solution methods for Slitherlink are known. Most Slitherlink solvers employ such methods [9, 10, 11]. Moreover, there are some attempts to automatically generate instances of Slitherlink. [PERSON]'s algorithm [10] starts from a grid graph with no numbers, which admits many solutions, and repeatedly puts a random number into a random cell one by one until the obtained instance admits a unique solution.