## 8 Experiments
### Numberlink Generator  
In this subsection, we show experimental results for enumerating all Numberlink instances for grid graphs by a variant of Algorithm 3. Our actual implementation is purely top-down, which is different from Algorithm 3. By interweaving the idea of Algorithm 3 into Algorithm 1, we construct \(Z_{G}\) assigning nodes mate functions as well as pair matching families representing the ends of fixed paths simultaneously. In our algorithm, \(S_{n}\) and \(B_{n}\) are calculated by set operations such as union and intersection. We implemented these sets by ZDDs whose variables are unordered pairs \(\{v,v^{\prime}\}\) of vertices \(v,v^{\prime}\in V\). For efficiency, our implementation maintains \(\langle W_{n},B_{n}\rangle\) instead of \(\langle S_{n},B_{n}\rangle\) for each node \(n\) in \(Z_{G}\), where \(W_{n}=S_{n}\setminus B_{n}\).  
Tables 4, 5 and 6 show the running time of our algorithm, the number of good instances and that of nodes of \(S_{1}\setminus B_{1}\) for \(G_{\alpha,\beta}\).  
\begin{table}
\begin{tabular}{l l c c c c c} \hline \hline
**Instance** & **Graph** & **Time CPLEX** & **Time Sugar** & **Time slink** & \multicolumn{2}{c}{**Time**} & \multicolumn{2}{c}{**Memory**} \\  & & & & & **Algorithm 5** & **Algorithm 5 (MB)** \\ \hline BS43 & \(G_{19,11}\) & \(0.17\) & \(8.349\) & \(0.001\) & \(0.060\) & \(36\) \\ BS54 & \(G_{19,11}\) & \(0.40\) & \(7.380\) & \(0.008\) & \(0.304\) & \(37\) \\ BS68 & \(G_{25,15}\) & \(0.39\) & \(12.433\) & \(0.004\) & \(0.384\) & \(39\) \\ BS77 & \(G_{25,15}\) & \(0.90\) & \(13.281\) & \(0.004\) & \(0.376\) & \(42\) \\ BS89 & \(G_{37,21}\) & \(1.56\) & \(48.035\) & \(0.016\) & \(9.329\) & \(407\) \\ BS96 & \(G_{37,21}\) & \(3.07\) & \(186.612\) & \(0.104\) & \(26.286\) & \(904\) \\ S10 & \(G_{21,37}\) & \(41.43\) & \(1,411.944\) & \(0.036\) & \(4,569.330\) & \(138,053\) \\ C95 & \(G_{32,46}\) & \(95.93\) & \(1,076.839\) & \(0.088\) & – & – \\ \hline \hline \end{tabular}
\end{table}
Table 3: _Cont._  
Figure 7: An example of information used by a heuristic Slitherlink solver.  
For \(G_{6,6}\), the computation did not finish within one week. We tried to compute the number of instances with restricting the number of pairs to at most \(\ell\). Table 7 shows the result of this computation for \(G_{6,6}\) and \(G_{7,7}\). Let \(W_{n,i}=\{\,T\in W_{n}\mid|T|=i\,\}\) and \(B_{n,i}=\{\,T\in B_{n}\mid|T|=i\,\}\). We maintain \(\langle W_{n,0},\ldots,W_{n,\ell},B_{n,0},\ldots,B_{n,\ell}\rangle\) instead of \(\langle W_{n},B_{n}\rangle\) in each node \(n\). We omit the method of computing \(W_{n,i}\) and \(B_{n,i}\). Then, we obtain that the number of minimum pairs with which \(G_{6,6}\) gives a good instance is 3 from this result. We give the complete list of those instances on the graph \(G_{6,6}\) with 3 pairs of vertices in Appendix G.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(\boldsymbol{\alpha}\backslash\boldsymbol{\beta}\) & \(\boldsymbol{2}\) & \(\boldsymbol{3}\) & \(\boldsymbol{4}\) & \(\boldsymbol{5}\) & \(\boldsymbol{6}\) & \(\boldsymbol{7}\) \\ \hline \(2\) & \(4\) & \(18\) & \(50\) & \(117\) & \(235\) & \(419\) \\ \(3\) & – & \(99\) & \(491\) & \(1,686\) & \(4,918\) & \(12,255\) \\ \(4\) & – & – & \(3,499\) & \(22,599\) & \(108,954\) & \(439,506\) \\ \(5\) & – & – & – & \(226,800\) & \(1,977,335\) & Time Out \\ \(6\) & – & – & – & – & Time Out & Time Out \\ \(7\) & – & – & – & – & – & Time Out \\ \hline \hline \end{tabular}
\end{table}
Table 6: The number of ZDD nodes of \(W_{\boldsymbol{1}}\) in Numberlink generator for \(G_{\alpha,\beta}\).  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \(\boldsymbol{\alpha}\backslash\boldsymbol{\beta}\) & \(\boldsymbol{2}\) & \(\boldsymbol{3}\) & \(\boldsymbol{4}\) & \(\boldsymbol{5}\) & \(\boldsymbol{6}\) & \(\boldsymbol{7}\) \\ \hline \(2\) & \(<\)\(0.01\) & \(<\)\(0.01\) & \(<\)\(0.01\) & \(<\)\(0.01\) & \(0.01\) & \(0.02\) \\ \(3\) & – & \(<\)\(0.01\) & \(0.01\) & \(0.08\) & \(0.48\) & \(2.67\) \\ \(4\) & – & – & \(0.21\) & \(3.56\) & \(44.13\) & \(488.1