## 6 Slitherlink Solver  
The goal of this section is to give a Slitherlink solver, which constructs a ZDD that represents all the solutions for a given instance \((G,h)\) of Slitherlink. Recall that a solution is a simple cycle that satisfies a property represented by the hint assignment \(h:2^{E}\rightharpoonup\mathbb{N}\). As a preparation, we present an algorithm that constructs a ZDD representing all the simple cycles on a given graph \(G\). Actually this algorithm is an answer to Exercise 226 of [13]. Based on the fact that any proper subgraph of a cycle is actually a path matching, it is easy to modify Algorithm 1 so that simple cycles shall be enumerated. We allow vertices to have degree \(1\) temporarily during the construction, but when we have determined which of the edges incident to a vertex \(v\) shall be used, the degree of \(v\) must be \(0\) or \(2\). In addition, we allow to add an edge \(e=\{u,v\}\) to a path matching \(E(\pi)\) if \(E(\pi)\) consists solely of a single \(u\)-\(v\) path: it completes a cycle. Both conditions are judged by observing the mate functions. We say that a mate function \(m\) and an edge \(e_{i}\)_form a cycle_ if for any \(v\) in the domain of \(m\),  
\[m(v)= \begin{cases}u&\text{ if }e_{i}=\{u,v\}\\ v\text{ or }0&\text{ if }v\
otin e_{i}\end{cases} \]  
If \(\operatorname{mate}_{n}\) and \(e_{i}\) form a cycle for \(n\in N_{i}\), the \(1\)-child of \(n\) should be \(\mathbf{1}\). We say that \((m,i)\)_has a fixed end_ if  
\[m(v)\
otin\{0,v\}\text{ for some }v\in e_{i}\setminus V^{\geq e_{i+1}}\]  
For a valid path \(\pi\) in \(Z_{G}\), if \((\operatorname{mate}_{n(\pi)},|\pi|)\) has a fixed end, \(E(\pi)\cup E^{\prime}\) has a vertex of degree \(1\) for any \(E^{\prime}\subseteq E^{\geq e_{i+1}}\). We say that \(m\)_declines_\(e_{i}\) if either \(m\) rejects \(e_{i}\) or \((\operatorname{MU}(m,e_{i}),i)\) has a fixed end. If \(\operatorname{mate}_{n}\) declines \(e_{i}\) for \(n\in N_{i}\), the \(1\)-child of \(n\) should be \(\mathbf{0}\). In addition, since the empty edge set is not a cycle, the corresponding path in our ZDD should end in \(\mathbf{0}\). Algorithm 4 constructs a ZDD for representing all the simple cycles on a graph \(G\). We prove the correctness of Algorithm 4 in Appendix D.  
```
Data: A graph \(G=(V,E)\) begin
1 create a root node and two terminal nodes \(\mathbf{0}\) and \(\mathbf{1}\);
2 let \(N_{1}\leftarrow\{n_{\mathrm{root}}\}\) and \(N_{i}\leftarrow\emptyset\) for \(i=2,\ldots,|E|\);
3 foreach\(i=1,\ldots,|E|\)do
4 foreach\(n\in N_{i}\)do
5 if\((\operatorname{mate}_{n},i)\) has a fixed end or \(i=|E|\)then let the \(0\)-child of \(n\) be \(\mathbf{0}\);
6 else let the \(0\)-child of \(n\) be \(\operatorname{GN}(i+1,\operatorname{mate}_{n}\big{|}_{V^{\geq e_{i+1}}})\);
7 if\(\operatorname{mate}_{n}\) and \(e_{i}\) form a cyclethen let the \(1\)-child of \(n\) be \(\mathbf{1}\);
8 elseif\(\operatorname{mate}_{n}\) declines \(e_{i}\)then let the \(1\)-child of \(n\) be \(\mathbf{0}\);
9 else let the \(1\)-child of \(n\) be \(\operatorname{GN}(i+1,\operatorname{MU}(\operatorname{mate}_{n},e_{i}) \big{|}_{V^{\geq e_{i+1}}})\);
10
11 end if
12
13 end for
14
15 end for
```  
**Algorithm 4**Enumeration of simple cycles  
We are now ready to give our Slitherlink solver, shown as Algorithm 5, based on Algorithm 4. Let \((G,h)\) be a Slitherlink instance. To ensure that the computed cycle is compatible with the hint assignment \(h\), we assign another function \(\mathrm{count}_{n}:\mathrm{dom}(h)\rightarrow\mathbb{N}\) to each node \(n\) in addition to \(\mathrm{mate}_{n}\). The function counts the number of picked edges in \(D\) in the domain of \(h\). That is, for a valid path \(\pi\), we shall have \(\mathrm{count}_{n(\pi)}(D)=|E(\pi)\cap D|\) for each \(D\in\mathrm{dom}(h)\). Especially \(\mathrm{count}_{n_{\mathrm{root}}}(D)=0\) for each \(D\in\mathrm{dom}(h)\). Updating the counter is very easy.