TCS -TR-A-13-69

TCS Technical Report

Efficient Top-Down ZDD Construction Techniques
Using Recursive Specifications
byHiroaki Iwashita and Shin-ichi Minato

Division of Computer Science
Report Series A
December 17, 2013

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Efficient Top-Down ZDD Construction Techniques
Using Recursive Specifications
Hiroaki Iwashita∗†‡

Shin-ichi Minato‡†

December 17, 2013

Abstract
Many important problems of graph enumeration and indexing can be solved by
frontier-based methods, which construct ZDDs in a breadth-first manner from the top
to the bottom. We present new techniques toward an efficient framework to deal withthe frontier-based methods. Ad hoc parts of the algorithm are encapsulated using therecursive specifications that represent properties to be compiled into a ZDD. In thisframework, we can apply the ZDD node deletion rule on the fly, while conventional
methods does not take it into account. Operations on the recursive specifications,which allow us to combine multiple properties without constructing ZDD structure
for each property, are also introduced. These techniques are applicable to existing
frontier-based methods and accelerates even Knuth’s sophisticated path enumeration
algorithm doubly.

1

Introduction

Ordered binary decision diagrams (BDDs) and zero-suppressed BDDs (ZDDs) are important data structures for representing Boolean functions and families of sets on computers[1][2][3]. They have originally become popular in problems of computer-aided design for
digital systems (CAD), such as logic synthesis and verification. Their range of applications are still expanding.
There are many open source and in-house BDD packages which have been used insuch traditional applications as CAD problems. They are general-purpose packages for
manipulating a collection of BDDs [4][5], allowing us to create primitive BDDs (variables and constants) and to construct complex BDDs by applying operations repeatedly
to existing ones. They usually traverse given BDDs in a depth-first manner and construct
the resulting BDD in a bottom-up way. Breadth-first BDD manipulation algorithms have
∗ iwashita@erato.ist.hokudai.ac.jp† ERATO MINATO Discrete Structure Manipulation System Project, Japan Science and Technology
Agency, Sapporo, Japan.
‡ Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan.

1

2

Hiroaki Iwashita and Shin-ichi Minato

been also proposed [6][7][8][9]. They are designed to have the same functionality withordinary BDD packages and to accelerate them by increasing memory access locality.
Graph enumeration and indexing problems are also important applications of BDDs
and ZDDs, which include enumeration/indexing of paths, cycles, connected components,
trees, forests, cut sets, partitioning, cliques, colorings, tilings, and matching. They aretightly related to various real-life problems, such as geographic information systems, dependency analysis, and demarcation problems. Each problem is solved implicitly by construction of a monolithic ZDD representing a family of all instances, where each instance(path, cycle, etc.) is represented by a set of graph edges or vertices. Some of them can beconstructed efficiently by conventional bottom-up ZDD operations; others are covered by
frontier-based methods, which construct result ZDDs directly from the root to the terminal
nodes.
Coudert introduced a ZDD based framework for solving graph and set related optimization problems [10]. It includes a bottom-up construction algorithm of the ZDD that
represents all maximal cliques of a given graph. Sekine et al. proposed top-down BDD
construction algorithms for computing Tutte polynomial and all spanning trees of a given
graph [11]. They also showed that the BDD for all spanning trees can be used to obtain a
BDD for all forests and a BDD for all paths between two vertices [12]. Knuth introduced
an algorithm to construct a ZDD representing all paths between two vertices in a top-down
way [3, exercise 225 in 7.1.4]. His algorithm is so efficient that a ZDD representing
227449714676812739631826459327989863387613323440
paths on a 15 × 15 grid graph is constructed within a few minutes. Cycles, Hamiltonian
paths, and path matching of a given graph can also be computed by similar algorithms[3][13].
We present new techniques toward an efficient ZDD framework to deal with frontierbased methods. Our approach applies the ZDD node deletion rule on the fly, while conventional methods does not take it into account. We also introduce top-down ZDD construction algorithms for a combination of multiple properties. They do not construct intermediate ZDDs for all the properties, which may blow up and become bottleneck inconventional methods.
This paper is organized as follows. Basics of BDDs and ZDDs, including top-down
construction methods and Knuth’s algorithm, are reviewed in Section 2. Our top-down
construction framework is introduced in Section 3, which contains a new method to speedup
the construction. Section 4 describes the operations and techniques on our framework thatcan be chosen for more efficient computation. Experimental results in Section 5 shows
practicality of our framework and techniques. We then conclude the paper in Section 6.

2

Preliminaries

2.1

BDDs and ZDDs

Binary decision diagrams (BDDs) [14][1] and zero-suppressed BDDs (ZDDs) [2] are labeled directed acyclic graphs derived by reducing binary decision tree graphs, which rep-Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications(a) Binary decision tree(b) BDD

3(c) ZDD

Figure 1: Diagrams for f (x1 , x2 , x3 ) = x1 x2 x3 + x1 x3
resent decision making processes through binary input variables. As illustrated in Figure 1, there are two kinds of terminal nodes, 0-terminal and 1-terminal, which represent
the output binary value. Every nonterminal node is labeled by an input variable and has
two outgoing edges, namely 0-edge and 1-edge, which are drawn as dotted and solid arrows respectively. The 0-edge (1-edge) points to the node called 0-child (1-child), which
represent a state after the decision that 0 (1) is assigned to the variable. When the root
node of a BDD/ZDD for Boolean function f is labeled by variable x, its 0-child and1-child represent fx=0 and fx=1 respectively; it corresponds to the Shannon expansion:f = x fx=0 + x fx=1 . In this paper, we also write it as f = (x ? fx=0 : fx=1 ), implying structure of the diagram.
We only deal with ordered BDDs/ZDDs in this paper, where input variables are indexed
as x1 , . . . , xn according to their total order. The index of the input variable of a nonterminal
node is just called the index of the node, and the index of a terminal node is assumed to ben + 1 for convenience. The index of any node is properly smaller than that of its children.
Figure 2 and Figure 3 show the reduction rules of BDDs and ZDDs respectively. Equivalent nodes, which have the same indices and the same 0- and 1-child nodes, can be sharedboth in BDDs and in ZDDs (Figure 2a and Figure 3a). A node with edges to the same destination can be deleted in BDDs (Figure 2b). In contrast, a node with a 1-edge directly
pointing to the 0-terminal node can be deleted in ZDDs (Figure 3b). If x has a smaller
index than the top variable of f , fx=0 = fx=1 = f in BDDs while fx=0 = f and fx=1 = 0 in
ZDDs. An entire BDD/ZDD can be reduced completely by applying the reduction rules
from the bottom (index n) to the top (index 1) as follows:
R EDUCE( f )1: for i = n to 1 do
2:
for all node p at index i in the diagram rooted by f do
3:
for all b ∈ {0, 1} do
4:apply reduction rules to the b-child of p;
5:
end for6:
end for4

Hiroaki Iwashita and Shin-ichi Minato(a) Sharing(b) Deletion

Figure 2: BDD reduction rules(a) Sharing(b) Deletion

Figure 3: ZDD reduction rules
7: end for
8: return reduced node for f .

BDDs and ZDDs are efficient data structures for representing not only Boolean functions but also families of sets. A set of n items can be represented by input variables
x1 , . . . , xn , where xi ∈ {0, 1} indicates if the i-th item is contained in the set. The diagramsin Figure 1 can be considered as {{x1 , x2 }, {x2 , x3 }, {x3 }} in that sense. Paths from the rootto the 1-terminal in BDDs and ZDDs, called 1-paths, correspond to item sets included in
the family. ZDDs have the interesting property that every 1-path represents an individual
set, while a 1-path may represent multiple sets in BDDs, because of the difference of theirnode deletion rules. ZDDs are especially suitable for representing families of sparse item
sets. If the average appearance rate of each item is 1%, ZDDs are possibly up to 100 times
more compact than BDDs. Such situations often appear in real-life problems.

2.2

Operations on BDDs/ZDDs

We can build up complex BDDs/ZDDs for various functions and sets by combinations of
their rich algebraic operations such as Boolean operations and family algebra [3]. Theyuse divide-and-conquer scheme based on the Shannon expansion, which is accelerated

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

5by the memo cache that avoids recomputation of the same subproblems. The following
algorithm outlines a typical depth-first implementation of binary operations:
DF B INARYO PERATION(, f , g)
1: if f  g has a terminal value, return it;
2: if f  g = h is in the memo cache, return h;
3: x ← the top variable of f and g;
4: h0 ← DF B INARYO PERATION (op, f |x=0 , g|x=0 );5: h1 ← DF B INARYO PERATION (op, f |x=1 , g|x=1 );6: h ← (x ? h0 : h1 );7: apply reduction rules to h;
8: put f  g = h into the memo cache;
9: return h.
This algorithm constructs a reduced diagram recursively from the bottom to the top.
Binary operations on BDDs/ZDDs can be implemented also in a breadth-first manner.
We create a new node immediately after dividing the problem; the new node is incomplete
as its descendants are not determined yet. The algorithm is outlined as follows:
BF B INARYO PERATION(, f , g)
1: let i0 be the top index of f and g;
2: create a new node h and label it as hi0 , f , gi ;3: for i = i0 to n do
4:
for all node r labeled hi, p, qi do
5:
for all b ∈ {0, 1} do
6:p0 ← p|xi =b ; q0 ← q|xi =b ;7:
if p0  q0 has a terminal value then8:
set it to the b-child of r;
9:
else
10:
i0 ← the top index of p0 and q0 ;11:find or create node r0 labeled hi0 , p0 , q0 i;
12:
set r0 to the b-child of r;
13:
end if14:
end for15:
end for
16: end for
17: return R EDUCE(h).
This algorithm constructs a diagram from the top to the bottom. Incomplete nodes arelabeled by its index and two operands of the subproblems, in order to share nodes for thesame subproblems. The operand information of each node can be removed when its childnodes are fixed. Since the top-down phase does not fully reduce the diagram, the reduction
algorithm is applied as a post-process.

6

Hiroaki Iwashita and Shin-ichi Minato(a) G3,3(b) Paths between v1 and v9

Figure 4: Path enumeration on G3,3

2.3

Top-Down Construction

Single-pass BDD/ZDD construction from the root to the terminals, which we call topdown construction in this paper, is another way to build a complex BDD/ZDD structure. It
is known that some important graph problems can be solved efficiently using such methods[11][12][3].
Node sharing must be performed on the fly during top-down construction in order toavoid explosion of the diagram. Multiple nonterminal nodes with the same index can beshared if and only if they take the same output values for all combinations of the rest of
input values. Since this condition is not always easy to be determined on the fly, it ischecked in a false-negative way by comparing the labels generated at some reasonable
cost. They are so designed that multiple nonterminal nodes are equivalent if their labels
are equivalent; the converse is not necessarily true because unshared nodes can be left for
the final reduction phase.
Knuth introduced an interesting algorithm in his book, named S IMPATH, which constructs a ZDD representing a set of paths (ways to go from a point to another point without
visiting any point twice) in an undirected graph [3][15]. For example, a 3 × 3 grid graph(G3,3 ) in Figure 4a has 12 paths between v1 and v9 as shown in Figure 4b. The input tothe algorithm is an undirected graph G = (V, E) where V = {v1 , . . . , vm } is a set of vertices
and E = {e1 , . . . , en } is a set of edges. The output is a ZDD representing all the set ofedges that form paths between v1 and vm .
In the S IMPATH algorithm, edge selections from E = {e1 , . . . , en } are decided one by
one in the order of indices. At each step of the algorithm, a set of selected edges represents
path fragments and each vertex has one of the three states:• not included in any path fragment,• an endpoint of a path fragment,• an intermediate point of a path fragment.
The label for a nonterminal node is defined to be hi, matei where 1 ≤ i ≤ n and mate is a

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

7

partial map from V to V ∪ {0}:
v if vertex v is untouched so far,mate[v] = u if vertices u and v are endpoints,
0 if vertex v is an intermediate point.
For simplicity of the algorithm, mate is maintained as if there were a built-in path between
v1 and vm and we were enumerating all the virtual cycles that include it. The current setof selected edges is accepted when:• a virtual cycle is formed and no other path fragment remains,and it is rejected when:• a virtual cycle is formed and some other path fragment remains, or• an edge to an intermediate point is added, or• the final chance to attach an edge to some endpoint is not taken.
In order to check the above conditions, we need mate entries only for frontier, which isa set of vertices contiguous with both decided and undecided edges. When vertex v isentering the frontier, a table entry mate[v] = v is created except for mate[v1 ] = vm andmate[vm ] = v1 . The entry for mate[v] is deleted after v has left the frontier.
Figure 5 illustrates the result of S IMPATH for G3,3 , where the 0-terminal node is omitted
and mate is drawn graphically on each node. Circles and lines represent vertices in thefrontier and path fragments among them respectively. An isolated open circle represents avertex not included in any path fragments (mate[v] = v). An isolated filled circle represents
an intermediate point of some path fragment (mate[v] = 0). Note that the ZDD nodedeletion rule is only used at edges to the 1-terminal node.

3

Top-Down ZDD Construction Framework

In this section, we introduce a framework of implementing top-down construction algorithms for ZDDs. The basic idea is to define a common interface to ad hoc parts of thealgorithms. Although we describe techniques for ZDDs hereafter, many of them are also
applicable to BDDs.

3.1

Recursive Specifications

We define that a configuration is a node label used in a top-down construction algorithm,
composed of a pair hi, si of node index i (1 ≤ i ≤ n) and other information s. We assume
that hn + 1, 0i and hn + 1, 1i are pre-defined configurations for the 0- and 1-terminals respectively.
A recursive specification of a ZDD is a definition of the following pair of functions:

8

Hiroaki Iwashita and Shin-ichi Minato

Figure 5: ZDD structure constructed by S IMPATH

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

9• ROOT() takes no argument and returns a root configuration, or a configuration of
the root node;• C HILD(hi, si , b) takes configuration hi, si of a node and branch b ∈ {0, 1} as arguments, and returns a new configuration for the b-child of the node.
A recursive specification can be viewed as a blueprint of a ZDD since it implicitly represents a unique diagram structure in a compact form. Many interesting top-down ZDD
construction algorithms, including S IMPATH, can be adapted in this framework.
For example, let us consider a ZDD representing a family of all combinations of k
items out of n items where node index i corresponds to the i-th item for 1 ≤ i ≤ n. We
define a set of configurations for nonterminal nodes as{ hi, si | 1 ≤ i ≤ n, 0 ≤ s ≤ k }where i is the item index for the next decision and s is the number of items included before
that node. The current item set is rejected immediately when s > k, and accepted whens = k and no more undecided item remains. Its recursive specification Combn,k is defined
as follows:
Combn,k .ROOT()
1: return h1, 0i;
Combn,k .C HILD(hi, si , b)
1: s ← s + b;
2: if i = n and s = k, return hn + 1, 1i;// 1
3: if i = n or s > k, return hn + 1, 0i;// 0
4: return hi + 1, si.
Figure 6 shows the ZDD specified by Comb5,2 before and after reduction. In this case, it is
not very difficult to define the recursive specification that directly represents the reduced
ZDD structure:
Comb0n,k .ROOT()
1: return h1, 0i;
Comb0n,k .C HILD(hi, si , b)
1: s ← s + b;
2: if s = k, return hn + 1, 1i;// 1
3: if s + n − i < k, return hn + 1, 0i;
4: return hi + 1, si.

// 0

The current item set is rejected as soon as we find that the remaining items are too few tomake the k-combination. It is accepted as soon as s = k is satisfied without taking all theremaining items.

10

Hiroaki Iwashita and Shin-ichi Minato(a) Before reduction(b) After reduction

Figure 6: ZDD structure for Comb5,2

3.2

General Top-Down ZDD Construction Algorithm

Provided that the recursive specifications are given, the top-down ZDD construction canbe processed by a common algorithm shown below; let S be a recursive specification and
n be the number of its input variables:
C ONSTRUCT(S)
1: hi0 , s0 i ← S.ROOT();
2: create a new node r and label it as hi0 , s0 i;
3: for i = i0 to n do
4:
for all node p labeled hi, si for some s do
5:
for all b ∈ {0, 1} do
hi0 , s0 i ← S.C HILD(hi, si , b);6:
7:
if hi0 , s0 i corresponds to a terminal node then8:
set it to the b-child of p;
9:
else
10:
find or create node p0 labeled hi0 , s0 i;
11:
set p0 to the b-child of p;
12:
end if13:
end for14:
end for
15: end for
16: return R EDUCE(r).
This algorithm searches all reachable configurations of S from the root to the terminals
in a breadth-first manner. Hash tables can be used to ensure one-to-one correspondenceEfficient Top-Down ZDD Construction Techniques Using Recursive Specifications

11

between configurations and ZDD nodes. Their entries should be disposed properly because memory size for a configuration might be much larger than that for a ZDD node.
Assuming that the hash table operations and evaluations of the recursive specification are
constant time operations, this algorithm runs in linear time against the number of reachable configurations.

3.3

Parallelizing the Construction Algorithm

We can parallelize the loop at lines 4–14 of C ONSTRUCT based on the fact that the tasks
are independent except for the hash table operations at line 10. One can use thread-safe
hash table for this purpose; or can divide the hash table into the multiple ones that manage
disjoint subsets of possible configurations. The following algorithm makes use of thelatter idea:
PAR C ONSTRUCT(S)
1: hi0 , s0 i ← S.ROOT();
2: let d be a dummy node;
3: insert hs0 , d, 0i to bucket[i0 ][1];
4: for i = i0 to n do
5:
for all k ∈ {1, . . . , m} do // in parallel
6:
for all s, p̂, b̂ ∈ bucket[i][k] do
7:find or create node p labeled hi, si;
8:
set p to the b̂-child of p̂;9:
if p is newly created then10:
for all b ∈ {0, 1} do
hi0 , s0 i ← S.C HILD(hi, si , b);11:
12:
if hi0 , s0 i corresponds to a terminal node then13:
set it to the b-child of p;
14:
else
15:
k0 ← bucket number for hi0 , s0 i;
16:insert hs0 , p, bi to bucket[i0 ][k0 ];17:
end if18:
end for19:
end if
20:
end for21:
end for
22: end for
23: let r be the 0-child of d;
24: return R EDUCE(r).
In the above algorithm, configurations are grouped into m buckets; bucket[i][k] works as
a task queue for node index i ∈ {1, . . . , n} and bucket number k ∈ {1, . . . , m}. Since tasks
for the same configurations are always stored in the same bucket, different buckets can beprocessed in parallel without caring about thread-safeness of the hash tables. The number

12

Hiroaki Iwashita and Shin-ichi Minatoof buckets m should be larger enough than the number of parallel threads for better loadbalancing, and should be smaller enough than the average number of nodes for each index
for less overhead costs. The reduction algorithm in 2.1 also can be parallelized in similar
ways.

4

Operations on Recursive Specifications

4.1

LookaheadIn general, any reduced/unreduced ZDD can be represented by a recursive specification;
the index might be increased by more than one in the C HILD function when we takethe zero-suppress rule aggressively into account. It improves the performance of ZDD
construction, while it may worsen simplicity of the recursive specification. It would bepleased if an optimized specification can be generated automatically from an easy-tounderstand description for humans.
The lookahead operation wraps a given recursive specification and makes the one that
represents a smaller and logically equivalent ZDD. It skips redundant configurations of
the original specification in terms of the zero-suppress rule.
L OOKAHEAD(S).ROOT()
1: return S.ROOT();L OOKAHEAD(S).C HILD(hi, si , b)
1: hi0 , s0 i ← S.C HILD(hi, si , b);
2: while i0 ≤ n and S.C HILD(hi0 , s0 i , 1) = hn + 1, 0i do
hi0 , s0 i ← S.C HILD(hi0 , s0 i , 0);
3:
4: end while
5: return hi0 , s0 i.
Figure 7 shows the result of S IMPATH for G3,3 combined with the lookahead. In comparison with the original result (Figure 5), the number of nonterminal nodes is reduced
from 52 to 29. This example also shows that the lookahead operation do not always remove all redundant nodes, because they do not care the node sharing and do not backtrack
for the node deletion.

4.2

Composition

Let us suppose that there are two properties represented by recursive specifications and wewant to compute the ZDD that represents the intersection of the properties. It is achieved
easily by constructing two ZDDs from the specifications and by applying the intersection
operation on ZDDs.
In this section, we present an alternative to this approach, in which we first composite
the two specifications and then construct a ZDD. It has the advantage of robustness when
an intermediate ZDD may blow up while the final ZDD should be compact.

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

Figure 7: ZDD constructed by S IMPATH with the lookahead

13

14

Hiroaki Iwashita and Shin-ichi Minato

Let S and T be recursive specifications and “” be some binary operator such as “∨”
or “∧”. Here we consider a binary operation on S and T , namely S  T , such thatC ONSTRUCT(S  T ) = C ONSTRUCT(S)  C ONSTRUCT(T ) .
It can be defined as follows:(S  T ).ROOT()
1: hi, si ← S.ROOT();
2: h j,ti ← T.ROOT();hn + 1, s  ti
if i = j = n + 1,
3: returnhmin(i, j), hi, s, j,tii otherwise.
(S  T ).C HILD
(hk, hi, s, j,tii , b) // k = min(i, j)
if k < i and b = 0,hi, si
if k < i and b = 1,
1: hi, si ← hn + 1, 0i
S.C HILD(hi, si , b) otherwise;
if k < j and b = 0,h j,ti
if k < j and b = 1,
2: h j,ti ← hn + 1, 0i
S.C HILD(h j,ti , b) otherwise;
hn + 1, s  ti
if i = j = n + 1,
3: returnhmin(i, j), hi, s, j,tii otherwise.
In case the operation is set intersection, or logical AND when the ZDDs are interpreted
as Boolean functions, we can optimize it by taking more advantage of the zero-suppressrule:(S ∩ T ).ROOT()
1: return (S ∩ T ).S YNC (S.ROOT(), T.ROOT()).
(S ∩ T ).C HILD(hi, hs,tii , b)
1: return (S ∩ T ).S YNC (S.C HILD(hi, si , b), T.C HILD(hi,ti , b)).
(S ∩ T ).S YNC(hi, si , h j,ti)
1: while i 6= j do
2:
if i < j, hi, si ← S.C HILD(hi, si , 0);3:
if j < i, h j,ti ← T.C HILD(h j,ti , 0);
4: end while
5: if i = n + 1, return hn + 1, s ∧ ti;
6: return hi, hs,tii.
Lines 1–4 of the S YNC subroutine skips the nodes that would have 1-edges to the 0terminal. It can be decided easily by checking if configurations derived from S and T
have different index numbers. We can go down through 0-edges until the indices aresynchronized. It is an interesting property of the combination of intersection operationand zero-suppress rule.

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

4.3

15

Wrapping and subsetting

We can wrap an existing ZDD structure in a recursive specification. The wrapper of ZDD
f is given as follows:
W RAP( f ).ROOT()
1: i ← the top index of f ;2: return hi, f i;
W RAP( f ).C HILD(hi, f i , b)
1: f 0 ← the b-child of f ;2: i0 ← the top index of f 0 ;3: return hi0 , f 0 i.
The same ZDD structure as f can be derived from W RAP( f ), that is:
C ONSTRUCT(W RAP( f )) = f .
The wrapping technique extends the usefulness of the operations on recursive specifications. Let us suppose the situation where we have some ZDD f and want to restrict it bya property represented by specification S. It can be computed as usual by the intersection
operation on ZDDs:
f ∩ C ONSTRUCT(S) .
Using the wrapping technique, we can also compute it as the intersection on specifications:C ONSTRUCT(W RAP( f ) ∩ S) .
We call it subsetting technique on top-down ZDD construction, which is an alternativethat is worth trying when Construct(S) becomes the bottleneck in the usual method.

5

Experimental Results

Our top-down ZDD construction framework is implemented in C++. We measured singlethreaded performance of the algorithms on 2.67GHz Intel Xeon E7-8837 CPU with 1.5TB
memory running 64-bit SUSE Linux Enterprise Server 11.

5.1

Path Enumeration

First, we evaluated the efficiency of our framework in comparison with the original S IM PATH implementation [15], and measured improvements achieved by the lookahead andsubsetting techniques.
We experimented with graph examples listed in Table 1, where m is the number ofvertices, n is the number of edges, and #path is the number of paths to be enumerated(paths between v1 and vm ). We used complete graphs (Km ), triangular grid graphs (Tα,β ),16Hiroaki Iwashita and Shin-ichi Minato

Table 1: Characteristics of graph examples
S IMPATH (sec.)
Graph
m
n
#path
Main
Reduce12K17
17
136 3.55 × 10
16.45
18.27
13
K18
18
153 5.69 × 10
57.45
59.70
K19
19
171 9.67 × 1014
183.98194.77641.52662.34K20
20
190 1.74 × 1016
17
2106.68 2344.67
K21
21
210 3.31 × 10
18
K22
22
231 6.61 × 10
7201.05 7939.68
39
5.58
7.20
T11,11
121
320 4.35 × 10
T12,12
144
385 6.81 × 1047
27.39
30.48
T13,13169
456 6.33 × 1056
115.19124.8966
T14,14196
533 3.50 × 10
504.95522.68772168.47 2260.38
T15,15225
616 1.15 × 10
88
T16,16256705 2.24 × 10
8868.41 9218.46
G13,13169
312 6.45 × 1034
12.42
14.94
40
G14,14196
364 6.95 × 10
46.23
50.40
47
152.77161.76
G15,15225
420 2.27 × 10
54
G16,16256
480 2.27 × 10
503.63534.77
61
G17,17289
544 6.87 × 10
1644.86 1826.86
G18,18324
612 6.34 × 1069
5598.11 5912.85
61
H22,23506
726 2.20 × 10
10.91
11.90
73
H24,25600
864 4.90 × 10
37.77
39.70
87
136.18129.32
H26,27702 1014 1.50 × 10
101
H28,29812 1176 6.28 × 10452.25434.77
H30,31930 1350 3.61 × 10117 1531.62 1486.30
H32,33 1056 1536 2.85 × 10134 4935.35 4864.38

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications(a) Tα,β(b) Gα,β(c) Hα,βFigure 8: Grid graphs and their vertex order

17

18

Hiroaki Iwashita and Shin-ichi Minato

Figure 9: Sets of graph edges represented by Degree(G3,3 , 1, 9)
square grid graphs (Gα,β ), and hexagonal grid graphs (Hα,β ) as benchmark examples. The
grid graphs and their vertex ordering rules are shown in Figure 8. The edge order (ZDD
variable order) is defined lexicographically with the vertex order: {vi , v j } ≤ {vi0 , v j0 } if andonly if vi < vi0 or (vi = vi0 and v j ≤ v j0 ) where vi ≤ v j and vi0 ≤ v j0 . We have tested some
simple vertex ordering rules and have chosen the one that makes final ZDDs compact.
Table 1 also includes CPU time for the original S IMPATH implementation,1 which iscomposed of the main program and the ZDD reduction program. The columns “Main” and“Reduce” show their CPU time in seconds. Note that they hand over an unreduced ZDD
via text file, while our implementation performs both ZDD construction and reduction on
memory.
We wrote the recursive specification Path(G, v1 , vm ) that corresponds to the S IMPATH
algorithm. The parameter G = (V, E) is a target graph where V = {v1 , . . . , vm } is a set ofvertices and E = {e1 , . . . , en } is a set of edges. We also wrote the recursive specification
Degree(G, v1 , vm ) that represents constraints on vertex degrees (number of edges incident
to a vertex). If E 0 ⊆ E forms a path between vertices v1 and vm , vertices in graph G0 =(V, E 0 ) must have a degree of 0 or 2 except that v1 and vm must have a degree of 1. That
condition is necessary but not sufficient for the set of edges to form a path. For example,
Figure 9 shows the 14 instances represented by Degree(G3,3 , 1, 9), which include the 2
instances that do not actually form paths.
We compared a basic one-pass method (1P), that with lookahead (1P+L), a two-pass
subsetting method (2P), and that with lookahead (2P+L). The four methods are defined asfollows:
1P

f ← C ONSTRUCT(Path(G, v1 , vm ));1P+L

f ← C ONSTRUCT(L OOKAHEAD(Path(G, v1 , vm )));

2P

g ← C ONSTRUCT(Degree(G, v1 , vm ));f ← C ONSTRUCT(W RAP(g) ∩ Path(G, v1 , vm ));2P+L

g ← C ONSTRUCT(L OOKAHEAD(Degree(G, v1 , vm )));
f ← C ONSTRUCT(W RAP(g) ∩ L OOKAHEAD(Path(G, v1 , vm ))).

Table 2 shows CPU time of the four methods. In comparison with the original S IM PATH implementation (Table 1), our implementation 1P looks reasonably fast. It showsEfficient Top-Down ZDD Construction Techniques Using Recursive Specifications

Table 2: CPU time for path enumeration (sec.)
Graph
1P
1P+L
2P
2P+L
K17
18.68
13.86
11.06
11.09
K18
62.50
47.69
33.10
33.93
K19
210.82169.54103.84109.43K20
776.18586.84318.73322.96
K212573.39 2083.32 1096.70 1024.71
K229683.19 7068.47 3839.62 3856.21
5.32
3.44
4.66
4.86
T11,11
T12,12
26.78
17.11
21.04
21.27
T13,13115.23
78.26
84.69
85.66
555.83340.44372.78334.79
T14,142121.35 1610.42 1355.35 1357.32
T15,15
T16,16 11185.38 6587.02 5499.10 5644.78
G13,13
10.53
6.53
6.13
5.71
41.09
25.31
20.08
18.76
G14,14
G15,15159.97
91.54
64.80
60.34
G16,16501.28320.46211.42
193.67
G17,171693.46 1067.76
681.77636.42
G18,186398.75 3664.18 2296.25 2274.09
H22,23
6.07
3.63
3.94
3.47
H24,25
32.98
18.29
16.37
14.34
H26,27
124.76
70.37
55.55
47.81
H28,29454.18268.33183.16165.88
H30,311542.16953.21
610.25571.67
H32,335680.29 3275.21 2078.65 1934.34

19

20

Hiroaki Iwashita and Shin-ichi Minato

Figure 10: Speed ratio for path enumerationthat there is no noticeable overhead in our top-down construction framework. The lookahead and subsetting techniques accelerated top-down ZDD construction by a factor of 1.1
to 2.9. Figure 10 summarizes computation speed of methods 1P+L, 2P, and 2P+L relative
to the basic method 1P. While the fastest method is dependent on the example, we canread that the subsetting technique is relatively effective in large examples.
Construction of ZDD g dominates CPU time in 2P and 2P+L because g is much smaller
than f . Table 3 compares ZDD size (the number of nonterminal nodes) of g and f . The
larger the graph is, the larger the size difference between g and f becomes. “Peak size” isthe ZDD size just before the reduction phase, which indicates the number of iterations run
in both construction and reduction phases. The lookahead and subsetting techniques haveeffect to reduce 40 to 50 percent of the peak size. It is interesting that methods 1P+L and2P does not show much difference in the peak size of f , even though the node deletion rule
is not checked explicitly in 2P. It means that the zero-suppress information was effectively
inherited from g in the subsetting method.
The total memory usage in megabytes is shown in Table 4. It is confirmed that the
lookahead and subsetting techniques are also effective to reduce memory usage.

5.2

Numberlink and Slitherlink Puzzles

Secondly, we have improved the ZDD-based solvers of Numberlink and Slitherlink introduced in [13] using the lookahead and subsetting techniques. Examples of Numberlink
and Slitherlink are shown in Figure 11 and Figure 12 respectively. They are logic puzzles
that involve finding the paths or the cycle that satisfy given local and global properties
1 We have slightly modified the programs in order to process larger input graphs on a 64-bit machine.

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

21

Table 3: ZDD size in path enumerationgf

Peak size
Graph
K17
K18
K19
K20
K21
K22
T11,11
T12,12
T13,13
T14,14
T15,15
T16,16
G13,13
G14,14
G15,15
G16,16
G17,17
G18,18
H22,23
H24,25
H26,27
H28,29H30,31
H32,332P
3,383,182
7,803,921
17,916,021
40,960,634
93,303,788
211,843,795
3,454,359
11,445,656
37,584,679
122,497,140
396,720,695
1,277,849,872
1,952,762
4,599,802
10,702,842
24,641,530
56,213,498
127,205,370
1,895,414
4,548,598
10,751,990
25,092,086
57,917,430
132,415,478

Final size

2P+L
1,446,371
3,331,561
7,638,950
17,445,357
39,699,692
90,058,256
1,678,273
5,558,016
18,243,715
59,440,240
192,448,119
619,726,690
983,037
2,314,237
5,382,141
12,386,301
28,246,013
63,897,597
1,004,539
2,410,491
5,697,531
13,295,611
30,687,227
70,156,283

1,415,798
3,266,139
7,498,891
17,144,913
39,055,059
88,674,234
1,534,383
5,075,298
16,642,341
54,176,364
175,277,115
564,075,414
971,773
2,289,661
5,328,893
12,271,613
28,000,253
63,373,309
897,019
2,151,419
5,083,131
11,857,915
27,361,275
62,537,723

Peak size
1P
31,687,586
98,595,128
309,329,033
978,702,177
3,122,714,316
10,047,097,379
13,365,043
53,816,252
215,875,876
863,508,297
3,446,706,536
13,735,340,349
26,894,640
86,698,791
277,581,568
883,640,711
2,799,256,918
8,830,604,856
20,985,221
68,690,969
222,730,862
716,615,275
2,290,741,210
7,282,606,658

1P+L
16,776,941
52,894,116
168,011,957
537,803,391
1,734,809,580
5,639,089,096
6,909,231
27,977,245
112,786,898
453,159,395
1,816,007,604
7,262,868,868
15,032,057
48,641,299
156,253,978498,888,415
1,584,605,112
5,010,748,938
12,431,317
40,853,448
132,929,717
429,006,718
1,375,126,756
4,382,454,784

2P
17,913,664
56,302,697
178,326,054
569,319,129
1,832,020,786
5,941,791,248
7,648,691
30,916,232
124,439,778
499,288,002
1,998,415,097
7,983,662,545
16,178,631
52,307,691
167,908,407
535,749,877
1,700,699,101
5,375,051,545
13,117,268
43,081,787
140,105,957
451,953,721
1,448,070,796
4,613,178,936

Figure 11: Numberlink problem and its solution

Figure 12: Slitherlink problem and its solution

Final size
2P+L
16,685,440
52,644,447
167,320,943
535,863,645
1,729,287,871
5,623,154,813
6,909,231
27,977,245
112,786,898
453,159,395
1,816,007,604
7,262,868,868
15,032,057
48,641,299
156,253,978498,888,415
1,584,605,112
5,010,748,938
12,431,317
40,853,448
132,929,717
429,006,718
1,375,126,756
4,382,454,784

15,469,186
48,935,273
155,922,881
500,559,700
1,619,050,484
5,276,150,643
6,432,417
26,076,799
105,238,888
423,254,393
1,697,726,218
6,795,583,172
13,803,430
44,871,856
144,759,636
464,004,180
1,479,128,501
4,692,765,814
10,686,910
35,229,328
114,956,610
371,973,561
1,195,179,926
3,817,373,513

22

Hiroaki Iwashita and Shin-ichi Minato

Table 4: Memory usage for path enumeration (MB)
Graph
1P
1P+L
2P
2P+L
K17
891
806
986
951
K18
2,701
2,717
3,447
3,187
K19
8,204
8,293
10,831
10,250K20
26,173
26,27533,392
32,031K21
82,39584,297 112,346 108,139
K22
254,359 272,999 367,226 357,666
327
194
249
231
T11,11
T12,12
1,273
713
905
820
T13,13
5,059
2,770
3,616
3,121
20,075
10,855
13,202
12,086
T14,14
79,98743,862
53,101
49,570
T15,15
T16,16 318,664 184,504 224,682 205,607
G13,13
786
402
412
388
2,277
1,212
1,287
1,202
G14,14
G15,15
6,532
3,758
4,079
3,802
G16,16
20,721
11,92713,017
12,125
G17,1765,952
37,686
41,23538,419G18,18 206,430 118,760 129,699 120,904
H22,23
505
322
333
319
H24,25
1,652
990
1,045
986
H26,27
5,464
3,155
3,318
3,151
H28,2916,63910,422
10,64010,081
H30,3153,02832,01633,912
32,215
H32,33 168,351 101,819 107,812 102,273

Efficient Top-Down ZDD Construction Techniques Using Recursive Specifications

23

Table 5: Characteristics of Numberlink problems
Name Graph mnDescription
BN64 G10,10 100
180 64th problem in [17]BN79 G10,10 100
180 79th problem in [17]BN85 G20,15 300
565 85th problem in [17]BN99 G20,15 300
565 99th problem in [17]C108 G36,20 720 1384 Vol. 108 in [18][16]. These experiments show case studies of designing efficient ZDD construction procedures on our framework.
5.2.1

Numberlink Solver

Numberlink is played on a grid with the following rules.
1. Connect pairs of the same hint 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 hint numbers.
4. Lines must cover all the cells.
It can be viewed as a problem of finding a path matching on grid graph G under hint h
where each cell corresponds to a vertex of G. It can be solved by an algorithm derived
from S IMPATH [13]. The output is the ZDD that represents the set of all solutions, whichmust be a singleton if the problem is designed correctly.
We have experimented on Numberlink problems listed in Table 5. In the same way
as experiments in the previous section, we wrote the main algorithm as recursive specification Numlin(G, h), which gives the exact solutions, and also wrote the constraints onvertex degrees (1 for vertices with hint numbers and 2 for others) as another recursive
specification Degree(G, h), which gives a superset of the solutions. We compared a basic
one-pass method (1P), that with lookahead (1P+L), a two-pass subsetting method (2P),
and that with lookahead (2P+L). The four methods are defined as follows:
1P

f ← C ONSTRUCT(Numlin(G, h));

1P+L

f ← C ONSTRUCT(L OOKAHEAD(Numlin(G, h)));2P

g ← C ONSTRUCT(Degree(G, h));f ← C ONSTRUCT(W RAP(g) ∩ Numlin(G, h));2P+Lg ← C ONSTRUCT(L OOKAHEAD(Degree(G, h)));f ← C ONSTRUCT(W RAP(g) ∩ L OOKAHEAD(Numlin(G, h))).

24

Hiroaki Iwashita and Shin-ichi Minato

Table 6: CPU time for solving Numberlink puzzles (sec.)
Name
1P
1P+L
2P
2P+L
BN64
0.02
0.01
0.02
0.02
BN79
0.03
0.02
0.03
0.03
BN85
72.69
42.19
32.93
27.14
BN99
79.95
42.47
38.72
28.97
C108 10092.48 5546.26 4653.71 3309.26
Table 7: Memory usage for solving Numberlink puzzles (MB)
Name
1P
1P+L
2P
2P+L
BN64
4
3
10
9
BN79
9
6
20
14
8,010
4,741
6,118
4,561
BN85
BN99
8,907
5,073
6,965
5,013
C108 817,969 467,968 644,967 474,646
In the methods 2P and 2P+L, g is used as a search space for the solutions.
Table 6 and Table 7 show CPU time in seconds and memory usage in megabytes respectively. The lookahead and subsetting techniques were effective for the Numberlink
solvers to reduce CPU time and memory usage. Method 2P+L was the fastest and wasabout three times as fast as the basic method 1L.
5.2.2

Slitherlink Solver

Slitherlink is played on a grid of dots with the following rules.
1. Connect adjacent dots with vertical or horizontal lines.
2. A single loop is formed with no crossing or branch.
3. Each hint cell indicates the number of lines surrounding it, while empty cells may
be surrounded by any number of lines.
It can be viewed as a problem of finding a cycle on grid graph G under hint h where each
dot corresponds to a vertex of G. It can be solved by an algorithm also derived fromS IMPATH [13]. The output is the ZDD that represents the set of all solutions, which must
be a singleton if the problem is designed correctly.
We have experimented on Slitherlink problems listed in Table 8. We made three recursive specifications: Cycle(G) for enumerating all cycles in G, Hint(G, h) for the constraints defined by the hints, and Degree(G) for the constraints on vertex degrees (0 or 2 forall vertices). Intersection of Cycle(G) and Hint(G, h) gives the solution, while Degree(G)is expected to be an extra guide to get the solution. ZDD for ACycle (G) could not beEfficient Top-Down ZDD Construction Techniques Using Recursive Specifications

25

Table 8: Characteristics of Slitherlink problems
Name GraphmnDescription
BS68 G25,15
375
710 68th problem in [19]
BS77 G25,15
375
710 77th problem in [19]
BS89 G37,21
777 1496 89th problem in [19]
BS96 G37,21
777 1496 96th problem in [19]S10G37,21777 1496 10th problem in [20]
C95 G46,32 1472 2866 Vol. 95 in [18]C103 G46,32 1472 2866 Vol. 103 in [18]C113 G46,32 1472 2866 Vol. 113 in [18]constructed because G is fairly large in the Slitherlink problems. We compared a basic
one-pass method (1P), that with lookahead (1P+L), a two-pass subsetting method (2P),
that with lookahead (2P+L), a three-pass subsetting method (3P), and that with lookahead(3P+L), using Hint(G, h) as the start points of the subsetting methods. The six methods
are defined as follows:
1P

f ← C ONSTRUCT(Hint(G, h) ∩ Cycle(G));

1P+L

f ← C ONSTRUCT(L OOKAHEAD(Hint(G, h) ∩ Cycle(G)));

2P

g ← C ONSTRUCT(Hint(G, h));f ← C ONSTRUCT(W RAP(g) ∩ Cycle(G));

2P+Lg ← C ONSTRUCT(L OOKAHEAD(Hint(G, h)));f ← C ONSTRUCT(W RAP(g) ∩ L OOKAHEAD(Cycle(G)));

3P

g ← C ONSTRUCT(Hint(G, h));g0 ← C ONSTRUCT(W RAP(g) ∩ Degree(G));
f ← C ONSTRUCT(W RAP(g0 ) ∩ Cycle(G));

3P+Lg ← C ONSTRUCT(L OOKAHEAD(Hint(G, h)));g0 ← C ONSTRUCT(W RAP(g) ∩ L OOKAHEAD(Degree(G)));f ← C ONSTRUCT(W RAP(g0 ) ∩ L OOKAHEAD(Cycle(G)));

Table 9 and Table 10 describe CPU time in seconds and memory usage in megabytes
respectively. Method 2P+L was the fastest for most examples, while 3P+L was very efficient for C95. The results show that the lookahead and subsetting techniques were effective also in Slitherlink solvers and that it is not easy to find the best subsetting strategy
before trial.

6

Conclusion

First, we proposed an efficient top-down ZDD construction framework for solving graphenumeration and indexing problems, in which the property is specified as a recursive spec-

26

Hiroaki Iwashita and Shin-ichi Minato

Table 9: CPU time for solving Slitherlink puzzles (sec.)
Name
1P
1P+L
2P
2P+L
3P
3P+L
BS68
0.02
0.02
0.02
0.02
0.02
0.02
BS77
0.04
0.04
0.02
0.02
0.02
0.01
1.92
1.11
0.85
0.52
1.79
1.16
BS89
BS96
6.60
3.43
2.34
1.43
12.21
7.59
S10
25.92
12.75
7.94
4.19
10.15
6.06
C95 12095.40 5209.64 2394.51 1284.40 1304.61 740.11
C103 6456.14 2400.81 1434.15 808.77 7830.46 4385.51
C113
713.80 341.19 285.49 155.98 393.05 243.67

Table 10: Memory usage for solving Slitherlink puzzles (MB)
Name
1P
1P+L
2P
2P+L
3P
3P+L
BS68
7
7
17
12
19
14
BS77
12
8
24
17
18
13
BS89
340
173
430
301
689
540
817
426
761
552
2,517
1,570
BS96
S10
2,247
1,113
1,382
936
2,025
1,273
C95 624,616 318,325 211,630 124,468 149,335 89,381
C103 364,887 178,929 139,410 84,036 739,841 441,777
C113 44,478 21,776 32,714 19,231 56,104 33,072

REFERENCES

27

ification.
The lookahead technique applies the zero-suppress rule on the fly, while conventional
methods does not take it into account during the top-down construction phase. Binary operations on recursive specifications, which allow us to combine multiple properties without
constructing ZDD structure for each property, can be a strong alternative to the conventional procedures that use operations on ZDDs. An improved algorithm for set intersection on recursive specifications also reduces CPU time and memory usage for constructing
ZDDs by skipping redundant states in the top-down construction phase. The subsetting
technique enables us to use an existing ZDD for restricting search space of top-down ZDD
construction.
The experimental results confirmed that our techniques actually improve time andspace for the top-down ZDD construction algorithms. The lookahead technique easily
fits for any application and produces good results in most cases. We can improve it further
by adding the subsetting technique especially for large examples, though it is not always
easy to find the best strategy of subsetting.

References[1]

R. E. Bryant. “Graph-based Algorithms for Boolean Function Manipulation”. In:
IEEE Transactions on Computers C-35.8 (1986), pp. 677–691.

[2]

S. Minato. “Zero-suppressed BDDs for Set Manipulation in Combinatorial Problems”. In: Proceedings of the 30th ACM/IEEE Design Automation Conference.
1993, pp. 272–277.

[3]

D. E. Knuth. The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1. 1st. Addison-Wesley Professional, 2011. ISBN: 0321751043.

[4]

K. S. Brace, R. L. Rudell, and R. E. Bryant. “Efficient Implementation of a BDD
Package”. In: Proceedings of the 27th ACM/IEEE Design Automation Conference.
1990, pp. 40–45.

[5]

S. Minato, N. Ishiura, and S. Yajima. “Shared Binary Decision Diagram with Attribute Edges for Efficient Boolean Function Manipulation”. In: Proceedings of the27th ACM/IEEE Design Automation Conference. 1990, pp. 52–57.

[6]

H. Ochi, K. Yasuoka, and S. Yajima. “Breadth-First Manipulation of Very Large
Binary-Decision Diagrams”. In: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 1993, pp. 48–55.

[7]

R. Ashar and M. Cheong. “Efficient Breadth-First Manipulation of Binary Decision Diagrams”. In: Proceedings of the IEEE/ACM International Conference on
Computer-Aided Design. 1994, pp. 622–627.

[8]

J. V. Sanghavi, R. K. Ranjan, R. K. Brayton, and A. Sangiovanni-Vincentelli. “High
Performance BDD Package by Exploiting Memory Hierarchy”. In: Proceedings ofthe 33rd Design Automation Conference. 1996, pp. 635–640.

28

REFERENCES[9]Y. Chen, B. Yang, and R. E. Bryant. Breadth-First with Depth-First BDD Construction: A Hybrid Approach. Tech. rep. CMU-CS-97-120. School of Computer
Science, Carnegie Mellon University, 1997.

[10]

O. Coudert. “Solving Graph Optimization Problems with ZBDDs”. In: Proceedingsof the ACM/IEEE European Design and Test Conference. 1997, pp. 224–228.

[11]

K. Sekine, H. Imai, and S. Tani. “Computing the Tutte Polynomial of a Graph ofModerate Size”. In: Proceedings of the 6th International Symposium on Algorithms
and Computation (ISAAC). 1995, pp. 224–233.

[12]

K. Sekine and H. Imai. “Counting the Number of Paths in a Graph via BDDs”. In:
IEICE Transactions on Fundamentals. Vol. E80-A. 4. 1997, pp. 682–688.

[13]

R. Yoshinaka, T. Saitoh, J. Kawahara, K. Tsuruma, H. Iwashita, and S. Minato.
“Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs”. In:
Algorithms 5.2 (2012), pp. 176–213. ISSN: 1999-4893. DOI: 10.3390/a5020176.
URL : http://www.mdpi.com/1999-4893/5/2/176/.

[14]

S. B. Akers. “Binary Decision Diagrams”. In: IEEE Transactions on Computers
C-27.6 (1978), pp. 509–516.

[15]

D. E. Knuth. Don Knuth’s Home Page. URL: http://www-cs-staff.stanford.
edu/~uno/.
[16] Nikoli. WEB Nikoli. URL: http://www.nikoli.co.jp/.
[17]

Nikoli. Numberlink 1. Nikoli, Tokyo, Japan, 1989. ISBN: 4890720103.

[18]

Nikoli. Nikoli.com Puzzle Championship. URL: http://www.nikoli.com/en/
event/puzzle_hayatoki.html.

[19]

Nikoli. Slitherlink 1. Nikoli, Tokyo, Japan, 1992. ISBN: 4890720243.

[20]

Nikoli. Sample Problems of Slitherlink Puzzle. URL: http://www.nikoli.com/
en/puzzles/slitherlink/.