## 8 Experiments
### Slitherlink Generator  
For the Slitherlink generator, we tried to generate some interesting examples of Slitherlink instances in order to confirm the usefulness of our tool. Our tool generates Slitherlink instances based on three kinds of input: a graph, a solution cycle, and the maximum domain of hint assignments. In usual cases where instances are made with grid graphs, a domain of hint assignments is represented by a set of rectangular cells.  
Figure 8 shows an example of Slitherlink generation. We drew a solution cycle on a \(5\times 7\) grid of cells and marked all 35 cells as the maximum set of hint cells. When they were given as the input, our tool successfully constructed a ZDD for a family of sets of hint cells in 8 s, from which we can obtain all the 2,912,556,380 good Slitherlink instances that have the given solution cycle. The tool can optionally restrict generated instances to minimal ones (instances such that any hint cannot be removed without making the solution not unique). It took 0.1 s for this example and the number of instances was reduced to 32,639. The output example shown in Figure 8 is the one selected automatically by our tool as the most difficult instance among them in our criteria, in which the difficulty is evaluated by smallness of the number of cells with hint values \"4\", \"0\", \"3\", \"1\", and \"2\" in this order of precedence. Another output example was shown already in Figure 2, which is one of the 81 good instances that consist of minimum hints.  
\begin{table}
\begin{tabular}{l c r r r} \hline \hline
**Graph** & \(\boldsymbol{\ell}\) & **Time** & **Good instances** & \(\boldsymbol{|W_{n,\ell}|}\) \\ \hline \(G_{6,6}\) & \(0\) & \(39.63\) & \(0\) & \(1\) \\ \(G_{6,6}\) & \(1\) & \(141.13\) & \(0\) & \(1\) \\ \(G_{6,6}\) & \(2\) & \(1,329.35\) & \(0\) & \(1\) \\ \(G_{6,6}\) & \(3\) & \(12,161.5\) & \(304\) & \(472\) \\ \(G_{6,6}\) & \(4\) & \(>\)\(1,000,000\) & – & – \\ \(G_{7,7}\) & \(0\) & \(2,732.86\) & \(0\) & \(1\) \\ \(G_{7,7}\) & \(1\) & \(14,226\) & \(0\) & \(1\) \\ \(G_{7,7}\) & \(2\) & \(>\)\(1,000,000\) & – & – \\ \hline \hline \end{tabular}
\end{table}
Table 7: Running time, the number of good instances with at most \(\ell\) pairs of numbers, and that of ZDD nodes of \(W_{\boldsymbol{1}}=S_{\boldsymbol{1}}\setminus B_{\boldsymbol{1}}\).  
Figure 8: Input and output of Slitherlink generation; example #1.  
Figure 9 shows another input example, in which the solution cycle is drawn on a 8 \(\times\) 8 grid of cells. Unfortunately, the computation could not be finished even in a day when all 64 cells are marked as candidates of hint locations. Our tool, however, was still able to assist making instances of the Slitherlink problem according to the designer's intent. We reduced the candidate locations to 36 cells (the right picture of Figure 9) and got 1,669,424 instances, 1,850 minimal instances, and 4 minimum instances (Figure 10) in 2 s. It is also interesting that the same mechanism can be used to modify existing instances. We found that hand-made instances often include many redundant hints (e.g., 12 out of 40) and our tool can be used to make them more difficult to solve.  
Finally, we introduce an enjoyable application of our tool, which can make a puzzle containing a secret message. Unlike the original Slitherlink, we allow multiple cycles as its solution in order to embed multiple letters into the puzzle. The algorithm of Slitherlink instance generation is modified by replacing computation of \"all cycles on \(G\)\" with \"all combinations of disjoint cycles on \(G\)\", which is actually not difficult to be computed by using conditions on degree of the graph vertices. Figure 11 is our message to readers.  
Figure 11: An example of message puzzle instance.  
Figure 9: Input of Slitherlink generation; example #2.